On the Robust Single Machine Scheduling Problem

The single machine scheduling problem with sum of completion times crite-rion (SS) can be solved easily by the Shortest Processing Time (SPT) rule. In the case of significant uncertainty of the processing times, a robustness approach is appropriate. In this paper, we show that the robust version of the (SS) prob-lem is NP-complete even for very restricted cases. We present an algorithm for finding optimal solutions for the robust (SS) problem using dynamic program-ming. We also provide two polynomial time heuristics and demonstrate their effectiveness