Preemptive parallel-machine scheduling with a common server to minimize makespan

Edwin Tai Chiu Cheng, Svetlana A. Kravchenko, Bertrand M.T. Lin

Research output: Journal article publicationJournal articleAcademic researchpeer-review

7 Citations (Scopus)


We consider parallel-machine scheduling with a common server and job preemption to minimize the makespan. While the non-preemptive version of the problem is strongly NP-hard, the complexity status of the preemptive version has remained open. We show that the preemptive version is NP-hard even if there is a fixed number of machines. We give a pseudo-polynomial time algorithm to solve the case with two machines. We show that the case with an arbitrary number of machines is unary NP-hard, analyze the performance ratios of some natural heuristic algorithms, and present several solvable special cases. Naval Research Logistics 64: 388–398, 2017.
Original languageEnglish
Pages (from-to)388-398
Number of pages11
JournalNaval Research Logistics
Issue number5
Publication statusPublished - 1 Aug 2017


  • common server
  • makespan
  • parallel machines
  • preemption
  • scheduling

ASJC Scopus subject areas

  • Modelling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research


Dive into the research topics of 'Preemptive parallel-machine scheduling with a common server to minimize makespan'. Together they form a unique fingerprint.

Cite this