Server scheduling on parallel dedicated machines with fixed job sequences

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

2 Citations (Scopus)

Abstract

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
Volume66
Issue number4
DOIs
Publication statusPublished - Jun 2019

Keywords

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

ASJC Scopus subject areas

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

Cite this