Preemptive parallel‐machine scheduling with a common server to minimize makespan
研究了带公共服务器和作业抢占的并行机调度问题，证明其NP难性，给出双机伪多项式算法，分析启发式算法性能比，并给出若干可解特例。
Abstract 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. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 388–398, 2017