Coupled-task scheduling on a single machine subject to a fixed-job-sequence

F. J. Hwang, Miao-Tsong Lin

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


This paper investigates single-machine coupled-task scheduling where each job has two tasks separated by an exact delay. The objective of this study is to schedule the tasks to minimize the makespan subject to a given job sequence. We introduce several intriguing properties of the fixed-job-sequence problem under study. While the complexity status of the studied problem remains open, an O(n2) algorithm is proposed to construct a feasible schedule attaining the minimum makespan for a given permutation of 2n tasks abiding by the fixed-job-sequence constraint. We investigate several polynomially solvable cases of the fixed-job-sequence problem and present a complexity graph of the problem.

Original languageEnglish
Pages (from-to)690-698
Number of pages9
JournalComputers and Industrial Engineering
Issue number4
StatePublished - May 2011


  • Coupled tasks
  • Exact delays
  • Fixed-job-sequence
  • Makespan

Fingerprint Dive into the research topics of 'Coupled-task scheduling on a single machine subject to a fixed-job-sequence'. Together they form a unique fingerprint.

Cite this