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

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

Journal of the Operational Research Society, 2021, vol. 72, issue 10, 2286-2289

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.

Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1080/01605682.2020.1779625 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tjorxx:v:72:y:2021:i:10:p:2286-2289

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjor20

DOI: 10.1080/01605682.2020.1779625

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().