Scheduling problems with repetitive projects: A comparison of a simulated annealing, a genetic and pair-wise swap algorithm

Scheduling problems with repetitive projects: A comparison of a simulated annealing, a genetic and pair-wise swap algorithm

0.00 Avg rating0 Votes
Article ID: iaor19982206
Country: Netherlands
Volume: 88
Issue: 1
Start Page Number: 124
End Page Number: 138
Publication Date: Jan 1996
Journal: European Journal of Operational Research
Authors: , ,
Keywords: optimization: simulated annealing
Abstract:

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. 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.

Reviews

Required fields are marked *. Your email address will not be published.