Single-machine scheduling of multi-operation jobs without missing operations to minimize the total completion time

Research output: Journal article publicationJournal articleAcademic researchpeer-review

4 Citations (Scopus)


We consider the problem of scheduling multi-operation jobs on a singe machine to minimize the total completion time. Each job consists of several operations that belong to different families. In a schedule each family of job operations may be processed as batches with each batch incurring a set-up time. A job is completed when all of its operations have been processed. We first show that the problem is strongly NP-hard even when the set-up times are common and each operation is not missing. When the operations have identical processing times and either the maximum set-up time is sufficiently small or the minimum set-up time is sufficiently large, the problem can be solved in polynomial time. We then consider the problem under the job-batch restriction in which the operations of each batch is partitioned into operation batches according to a partition of the jobs. We show that this case of the problem can be solved in polynomial time under a certain condition.
Original languageEnglish
Pages (from-to)320-331
Number of pages12
JournalEuropean Journal of Operational Research
Issue number2
Publication statusPublished - 1 Dec 2008


  • Job-batch restriction
  • Multi-operation jobs
  • Scheduling
  • Single machine
  • SPT-agreeability

ASJC Scopus subject areas

  • Information Systems and Management
  • Management Science and Operations Research
  • Statistics, Probability and Uncertainty
  • Applied Mathematics
  • Modelling and Simulation
  • Transportation

Cite this