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

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

*此作品的通信作者

研究成果: Article同行評審

摘要

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 binaryNP-hard when the number of machines is three, and propose a pseudo-polynomial algorithm to solve the problem with a constant number of machines.

原文English
頁數4
期刊Journal of the Operational Research Society
DOIs
出版狀態Accepted/In press - 七月 2020

指紋

深入研究「Complexity of server scheduling on parallel dedicated machines subject to fixed job sequences」主題。共同形成了獨特的指紋。

引用此