In this paper we study the problem of scheduling n jobs in a one-operator–two-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 process the job on its own. After a machine finishes processing a job, the operator needs to perform a dismounting operation before setting up the machine for another job. The setup and dismounting operations are either separable or nonseparable. The objective is to minimize the makespan. Confining our study to cyclic-movement schedules which require the operator to move between the two machines according to some cyclic pattern, we show that both the cyclic-movement separable and nonseparable setup and dismounting problems are NP-complete in the strong sense. We then propose some heuristics and analyze their worst-case error bounds.
