Complexity of server scheduling on parallel dedicated machines subject to fixed job sequences

T. C.E. Cheng, Svetlana A. Kravchenko, Bertrand M.T. Lin

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

We study server scheduling on parallel dedicated machines to minimize the makespan subject to given processing sequences. Before a job starts its processing on its designated machine, a loading operation must be performed, which is undertaken by a server shared by all the jobs. While the two-machine problem is polynomially solvable, we show that the problem becomes binary NP-hard when the number of machines is three, and propose a pseudo-polynomial algorithm to solve the problem with a constant number of machines.

Original languageEnglish
JournalJournal of the Operational Research Society
DOIs
Publication statusAccepted/In press - 2020

Keywords

  • complexity
  • dynamic programming
  • fixed job sequence
  • makespan
  • Parallel machines
  • single server

ASJC Scopus subject areas

  • Management Information Systems
  • Strategy and Management
  • Management Science and Operations Research
  • Marketing

Cite this