Worst-case analysis of the WSPT1 and MWSPT2 rules for single machine scheduling with one planned setup period
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.
worst-case analysis scheduling planned setup heuristic algorithms