Scheduling a single server in a two-machine flow shop

Edwin Tai Chiu Cheng, M. Y. Kovalyov

Research output: Journal article publicationJournal articleAcademic researchpeer-review

12 Citations (Scopus)

Abstract

We study the problem of scheduling a single server that processes n jobs in a two-machine flow shop environment. A machine dependent setup time is needed whenever the server switches from one machine to the other. The problem with a given job sequence is shown to be reducible to a single machine batching problem. This result enables several cases of the server scheduling problem to be solved in O(n log n) by known algorithms, namely, finding a schedule feasible with respect to a given set of deadlines, minimizing the maximum lateness and, if the job processing times are agreeable, minimizing the total completion time. Minimizing the total weighted completion time is shown to be NP-hard in the strong sense. Two pseudopolynomial dynamic programming algorithms are presented for minimizing the weighted number of late jobs. Minimizing the number of late jobs is proved to be NP-hard even if setup times are equal and there are two distinct due dates. This problem is solved in O(n3) time when all job processing times on the first machine are equal, and it is solved in O(n4) time when all processing times on the second machine are equal.
Original languageEnglish
Pages (from-to)167-180
Number of pages14
JournalComputing (Vienna/New York)
Volume70
Issue number2
DOIs
Publication statusPublished - 6 Aug 2003

Keywords

  • Algorithms
  • Batching
  • Dynamic programming
  • Scheduling

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Numerical Analysis
  • Computer Science Applications
  • Computational Theory and Mathematics
  • Computational Mathematics

Cite this