TWO-MACHINE FLOW SHOP SCHEDULING WITH AN INTERSTAGE TRANSPORTER: TWO SHIPMENTS

We consider the two-machine flow shop scheduling problem to minimize the makespan, provided that the jobs have to be transported between the machines by a single transporter or carrier. The transporter may take an arbitrary number of jobs at a time. For this NP-hard problem, we describe a heuristic that behaves as a ***6/5–approximation algorithm, provided that there exists an optimal schedule with exactly two shipments. The obtained result should be viewed as a necessary step towards an algorithm with a better worst-case behaviour than a ***3/2–approximation algorithm by Lee and Strusevich (2005).