Server scheduling on parallel dedicated machines with fixed job sequences

T. C.E. Cheng, Svetlana A. Kravchenko, Miao-Tsong Lin*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


We consider server scheduling on parallel dedicated machines to minimize the makespan. Each job has a loading operation and a processing operation. The loading operation requires a server that serves all the jobs. Each machine has a given set of jobs to process, and the processing sequence is known and fixed. We design a polynomial-time algorithm to solve the two-machine case of the problem. When the number of machines is arbitrary, the problem becomes strongly NP-hard even if all the jobs have the same processing length or all the loading operations require a unit time. We design two heuristic algorithms to treat the case where all the loading times are unit and analyze their performance.

Original languageEnglish
Pages (from-to)321-332
Number of pages12
JournalNaval Research Logistics
Issue number4
StatePublished - Jun 2019


  • fixed job sequence
  • makespan
  • parallel dedicated machines
  • single server


Dive into the research topics of 'Server scheduling on parallel dedicated machines with fixed job sequences'. Together they form a unique fingerprint.

Cite this