Scheduling a two-stage flowshop under makespan constraint

Scheduling a two-stage flowshop under makespan constraint

0.00 Avg rating0 Votes
Article ID: iaor2007672
Country: Netherlands
Volume: 44
Issue: 1/2
Start Page Number: 73
End Page Number: 84
Publication Date: Jul 2006
Journal: Mathematical and Computer Modelling
Authors: , ,
Keywords: heuristics
Abstract:

We consider selecting and sequencing jobs in a two stage flowshop so that the selected jobs are completed before a specified time limit (such as the end of a shift). The objective is to maximize the weighted (reward) sum of the selected jobs. We show that the problem is NP-hard, and present two procedures to find an optimum solution. The first procedure uses dynamic programming, and the second uses mixed integer programming. The integer programming formulation exploits special properties of the problem and solves large instances of the problem. We also develop heuristics and provide worst case performance guarantees. An improvement procedure is also developed. Extensive computational testing shows that our heuristics, when used jointly with the improvement procedure, yield excellent results (providing solutions within 3% of the optimum in an average sense) for both balanced and unbalanced shops.

Reviews

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