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 production 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, spacecraft, 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 are characterized by two potentially conflicting considerations: 1) the need to complete each unit by its contractual due date, and 2) learning effects. Because of the first consideration, there is a tendency to use multiple crews for simultaneous production, so that meeting due dates is assured. However, the second consideration encourages assigning many units to a single crew so that learning effects are maximized. We study this scheduling problem with two different penalty cost structures and develop models for both versions. The models trade-off the penalty associated with late deliveries and the savings due to learning (and possibly incentive payments for early completion). We discuss different heuristic algorithms - simulated annealing, a genetic algorithm, 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 procedure for these models.