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

Edwin Tai Chiu Cheng, Guoqing Wang, Chelliah Sriskandarajah

Research output: Journal article publicationJournal articleAcademic researchpeer-review

34 Citations (Scopus)


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. Scope and purpose The one-worker-multiple-machine (OWMM) concept is widely applied in just-in-time (JIT) manufacturing systems. In an OWMM system, a worker tends several machines simultaneously where each of the machines performs a different operation, and the different machines make up a flow line. In this paper, we study a scheduling problem in the one-operator-two-machine system where the operator moves between two machines according to some cyclic pattern, and performs the setup and dismounting operations on both machines. Both separable and nonseparable setup and dismounting problems are considered.
Original languageEnglish
Pages (from-to)715-730
Number of pages16
JournalComputers and Operations Research
Issue number7
Publication statusPublished - 1 Jul 1999


  • Algorithms
  • Complexity
  • Flowshop scheduling
  • One-operator-two-machine

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research

Cite this