One-operator-two-machine flowshop scheduling with setup and dismounting times

In this paper we study the problem of scheduling n jobs ina one-operator-tw o-machine flowshop. In such a flowshop, before a machine begins processing a job, the operator has to set up the machine, and then the machine can pro cess the job on its own. After a machine finishes processing a job, the ope rator needs to perform a dismounting operation before setting up the machin e for another job. The setup and dismounting operations are either separabl e or nonseparable. The objective is to minimize the makespan. Confining our study to cyclic-movement schedules which require the operator to move betw een the two machines according to some cyclic pattern, we show that both th e cyclic-movement separable and nonseparable setup and dismounting problems are NP-complete in the strong sense. We then propose some heuristics and a nalyze their worst-case error bounds. (C) 1999 Elsevier Science Ltd. All ri ghts reserved.