Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
477643 | European Journal of Operational Research | 2008 | 10 Pages |
Abstract
In this article, we consider the single machine scheduling problem with one planned setup period, with the aim of minimizing the weighted sum of the completion times. We study the WSPT and MWSPT heuristics and we show that the worst-case performance ratio is 3 for the two heuristics in some cases and it is unbounded otherwise. We also show that these worst-case performance ratios are tight.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Imed Kacem, Chengbin Chu,