ROBUST SCHEDULING TO HEDGE AGAINST PROCESSING TIME UNCERTAINTY IN SINGLE-STAGE PRODUCTION

Schedulers confronted with significant processing time uncertainty oft en discover that a schedule which is optimal with respect to a determi nistic or stochastic scheduling model yields quite poor performance wh en evaluated relative to the actual processing times. In these environ ments, the notion of schedule robustness, i.e., determining the schedu le with the best worst-case performance compared to the corresponding optimal solution over all potential realizations of job processing tim es, is a more appropriate guide to schedule selection. In this paper, we formalize the robust scheduling concept for scheduling situations w ith uncertain or variable processing times. To illustrate the developm ent of solution approaches for a robust scheduling problem, we conside r a single-machine environment where the performance criterion of inte rest is the total flow time over all jobs. We define two measures of s chedule robustness, formulate the robust scheduling problem, establish its complexity, describe properties of the optimal schedule, and pres ent exact and heuristic solution procedures. Extensive computational r esults are reported to demonstrate the efficiency and effectiveness of the proposed solution procedures.