A note on “scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan” |
| |
Authors: | Dehua Xu Yunqiang Yin Hongxing Li |
| |
Institution: | 1. School of Mathematical Sciences, Beijing Normal University, Beijing 100875, China;2. School of Electronic and Information Engineering, Dalian University of Technology, Dalian, Liaoning 116024, China |
| |
Abstract: | In a recent paper, Chen J.S. Chen, Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan, European Journal of Operational Research 190 (2008) 90–102] proposes a heuristic algorithm to deal with the problem Scheduling of Nonresumable Jobs and Flexible Maintenance Activities on A Single Machine to Minimize Makespan . Chen also provides computational results to demonstrate its effectiveness. In this note, we first show that the worst-case performance bound of this heuristic algorithm is 2. Then we show that there is no polynomial time approximation algorithm with a worst-case performance bound less than 2 unless P=NP, which implies that Chen’s heuristic algorithm is the best possible polynomial time approximation algorithm for the considered scheduling problem. |
| |
Keywords: | Scheduling Single machine Maintenance Heuristic algorithm Worst-case analysis |
本文献已被 ScienceDirect 等数据库收录! |
|