Single-machine scheduling with periodic maintenance to minimize makespan

Single-machine scheduling with periodic maintenance to minimize makespan

0.00 Avg rating0 Votes
Article ID: iaor20082409
Country: United Kingdom
Volume: 34
Issue: 6
Start Page Number: 1764
End Page Number: 1770
Publication Date: Jun 2007
Journal: Computers and Operations Research
Authors: , ,
Keywords: maintenance, repair & replacement, computational analysis
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.

Reviews

Required fields are marked *. Your email address will not be published.