Preemptive parallel‐machine scheduling with a common server to minimize makespan |
| |
| Authors: | TCE Cheng Svetlana A Kravchenko Bertrand MT Lin |
| |
| Institution: | 1. Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong;2. United Institute of Informatics Problems, Minsk, Belarus;3. Institute of Information Management, National Chiao Tung University, Hsinchu, Taiwan |
| |
| 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 |
| |
| Keywords: | scheduling parallel machines common server makespan preemption |
|
|
