Minimizing maximum completion time in a proportionate flow shop with one machine of different speed

Minimizing maximum completion time in a proportionate flow shop with one machine of different speed

0.00 Avg rating0 Votes
Article ID: iaor20084377
Country: Netherlands
Volume: 176
Issue: 2
Start Page Number: 964
End Page Number: 974
Publication Date: Jan 2007
Journal: European Journal of Operational Research
Authors: , ,
Keywords: optimization
Abstract:

A flow shop with identical machines is called a proportionate flow shop. In this paper, we consider the variant of the n-job, m-machine proportionate flow shop scheduling problem in which only one machine is different and job processing times are inversely proportional to machine speeds. The objective is to minimize maximum completion time. We describe some optimality conditions and show that the problem is NP-complete. We provide two heuristic procedures whose worst-case performance ratio is less than two. Extensive experiments with various sizes are conducted to show the performance of the proposed heuristics.

Reviews

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