ALCOMFT-TR-01-122

Sixiang Hou and Han Hoogeveen
The three-machine proportionate flow shop problem with unequal machine speeds
Utrecht. Work package 3. May 2001.

Abstract: In flow shop scheduling, it is usually assumed that the processing times of the operations belonging to the same job are unrelated. But when a job corresponds to producing a certain quantity of some good, then it is likely that the processing times are related to this quantity, and hence are constant except for some factor that depends on the speed of the machine. In this paper, we consider this special case of the flow shop problem, which we call the proportionate flow shop problem with unequal machine speeds. We study the problem with three machines, where we assume that the second machine is slowest, with the objective of minimizing the makespan. We show that then there exists an optimum schedule that is V-shaped. As a consequence, this problem can be solved in pseudopolynomial time, and we show that this is best possible by establishing NP-hardness in the ordinary sense. \medskip \newline \noindent 1980 Mathematics Subject Classification (Revision 1991): 90B35. \newline Keywords and Phrases: proportionate flow shop, machine speeds, V-shaped, makespan, dynamic programming, NP-hardness.

Postscript file: ALCOMFT-TR-01-122.ps.gz (101 kb).