標題: 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-八月-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
顯示於類別:期刊論文