| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1144303 | Systems Engineering - Theory & Practice | 2009 | 7 Pages |
Abstract
A single-machine scheduling problem with an unavailable period to minimize makespan is discussed in this article. The disrupted job is assumed to be semiresumable. It is shown that the relative worst-case error bound of the longest processing time (LPT) algorithm is α/2, where α is reprocess-ratio. Furthermore, an example is provided to show the tightness of this bound, and then a LPT-based heuristic is proposed. Computational results show that this heuristic is quite effective in finding an optimal or near-optimal solution. Effects of different parameters on this algorithm are also analyzed.
Related Topics
Physical Sciences and Engineering
Engineering
Control and Systems Engineering
