Robust single machine scheduling with uncertain processing times

Abstract

Single-machine scheduling is the process of determining the order of tasks to be performed in a single machine. Typically, process times are assumed to be deterministic in scheduling problems. However, in real life problems, processing times can be uncertain and in such cases, using deterministic model often gives solutions that are highly volatile in performance. In this study, method of obtaining robust solution which minimizes total tardiness under process time uncertainty is proposed. A solution is considered a robust solution when total tardiness of a schedule is within a given value although the processing times vary as specified in an uncertainty set. The problem is formulated as a mixed integer programming model. Computational experiments show that the solutions obtained through this method successfully provides robust schedules. We also propose methods to identify meaningful range of the parameter for robustness of the solu tions. Algorithms to obtain them are illustrated and computational experiments are conducted to test the algorithms.