Single-machine scheduling with periodic maintenance to minimize makespan |
| |
Authors: | Min Ji Yong He TCE Cheng |
| |
Affiliation: | 1. Department of Mathematics, and State Key Lab of CAD & CG, Zhejiang University, Hangzhou 310027, PR China;2. Department of Logistics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong |
| |
Abstract: | We consider a single-machine scheduling problem with periodic maintenance activities. Although the scheduling problem with maintenance has attracted researchers’ attention, most of past studies considered only one maintenance period. In this research several maintenance periods are considered where each maintenance activity is scheduled after a periodic time interval. The objective is to find a schedule that minimizes the makespan, subject to periodic maintenance and nonresumable jobs. We first prove that the worst-case ratio of the classical LPT algorithm is 2. Then we show that there is no polynomial time approximation algorithm with a worst-case ratio less than 2 unless P=NP, which implies that the LPT algorithm is the best possible. |
| |
Keywords: | Single-machine scheduling Periodic maintenance Nonresumable jobs Approximation algorithm Non-approximability |
本文献已被 ScienceDirect 等数据库收录! |
|