Robust single machine scheduling for minimizing total flow time in the presence of uncertain processing times

• Address the single machine scheduling problem with interval processing times.
• Obtain robust schedule with minimum worst-case total flow time.
• Propose a mixed integer linear program for the problem.
• Develop a simple iterative improvement heuristic and a simulated annealing heuristic.
• Examine algorithmic performance, robustness price and hedge value.

This research deals with the single machine scheduling problem (SMSP) with uncertain job processing times. The single machine robust scheduling problem (SMRSP) aims to obtain robust job sequences with minimum worst-case total flow time. We describe uncertain processing times using intervals, and adopt an uncertainty set that incorporates a budget parameter to control the degree of conservatism. A revision of the uncertainty set is also proposed to address correlated uncertain processing times due to a number of common sources of uncertainty. A mixed integer linear program is developed for the SMRSP, where a linear program for determining the worst-case total flow time is integrated within the conventional integer program of the SMSP. To efficiently solve the SMRSP, a simple iterative improvement (SII) heuristic and a simulated annealing (SA) heuristic are developed. Experimental results demonstrate that the proposed SII and SA heuristics are effective and efficient in solving SMRSP with practical problem sizes.