SCHEDULING PROGRAMS WITH REPETITIVE PROJECTS - A COMPARISON OF A SIMULATED ANNEALING, A GENETIC AND A PAIR-WISE SWAP ALGORITHM

We address the problem of scheduling in programs involving the product ion of multiple units of the same product. Our study was motivated by a construction program for fast naval patrol boats. Other applications of this problem include procurement of multiple copies of aircraft, s pacecraft, and weapon systems. In this problem we must decide how many units of the product to assign to each of a number of available crews (individuals, teams, subcontractors, etc.). These types of problems a re characterized by two potentially conflicting considerations: 1) the need to complete each unit by its contractual due date, and 2) learni ng effects. Because of the first consideration, there is a tendency to use multiple crews for simultaneous production, so that meeting due d ates is assured. However, the second consideration encourages assignin g many units to a single crew so that learning effects are maximized. We study this scheduling problem with two different penalty cost struc tures and develop models for both versions. The models trade-off the p enalty associated with late deliveries and the savings due to learning (and possibly incentive payments for early completion). We discuss di fferent heuristic algorithms - simulated annealing, a genetic algorith m, and a pair-wise swap heuristic - as well as an exhaustive search to determine a baseline for comparisons. Our computational results show that the pair-wise swap algorithm is the most efficient solution proce dure for these models.