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

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

*此作品的通信作者

研究成果: Article同行評審

6 引文 斯高帕斯(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.

原文English
頁(從 - 到)388-398
頁數11
期刊Naval Research Logistics
64
發行號5
DOIs
出版狀態Published - 八月 2017

指紋

深入研究「Preemptive parallel-machine scheduling with a common server to minimize makespan」主題。共同形成了獨特的指紋。

引用此