標題: | Preemptive Parallel-Machine Scheduling with a Common Server to Minimize Makespan |
作者: | Cheng, T. C. E. Kravchenko, Svetlana A. Lin, Bertrand M. T. 資訊管理與財務金融系 註:原資管所+財金所 Department of Information Management and Finance |
關鍵字: | scheduling;parallel machines;common server;makespan;preemption |
公開日期: | 1-Aug-2017 |
摘要: | 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. (C) 2017 Wiley Periodicals, Inc. |
URI: | http://dx.doi.org/10.1002/nav.21762 http://hdl.handle.net/11536/144026 |
ISSN: | 0894-069X |
DOI: | 10.1002/nav.21762 |
期刊: | NAVAL RESEARCH LOGISTICS |
Volume: | 64 |
起始頁: | 388 |
結束頁: | 398 |
Appears in Collections: | Articles |