Scheduling two-machine flow shops with exact delays

Joseph Y.T. Leung, Haibing Li, Hairong Zhao

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

Abstract

We consider two-machine flow shop problems with exact delays. In this model, there are two machines, the upstream machine and the downstream machine. Each job j has two operations: the first operation has to be processed on the upstream machine and the second operation has to be processed on the downstream machine, subject to the constraint that the time interval between the completion time of the first operation and the start time of the second operation is exactly l̄j. We concentrate on the objectives of makespan and total completion time. For the makespan objective, we first show that the problem is strongly NP-hard even if there are only two possible delay values. We then show that some special cases of the problem are solvable in polynomial time. Finally, we design efficient approximation algorithms for the general case and some special cases. For the total completion time objective, we give optimal polynomial-time algorithm for a special case and an efficient approximation algorithm for another one.

Original languageEnglish (US)
Pages (from-to)341-359
Number of pages19
JournalInternational Journal of Foundations of Computer Science
Volume18
Issue number2
DOIs
StatePublished - Apr 2007

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)

Keywords

  • Approximation algorithm
  • Exact delay
  • Flow shop
  • Makespan
  • NP-hard
  • Total completion time

Fingerprint

Dive into the research topics of 'Scheduling two-machine flow shops with exact delays'. Together they form a unique fingerprint.

Cite this