AAAI Publications, Twenty-Seventh International Conference on Automated Planning and Scheduling

Font Size: 
An Investigation of Phase Transitions in Single-Machine Scheduling Problems
Zhihui Wang, Bryan O'Gorman, Tony T. Tran, Eleanor G. Rieffel, Jeremy Frank, Minh Do

Last modified: 2017-06-05


We investigate solvable-unsolvable phase transitions in the single-machine scheduling (SMS) problem. SMS is at the core of practical problems such as telescope and satellite scheduling and manufacturing. To study the solvability phase transition, we construct a variety of instance families parameterized by the set of the processing times, the window size (deadline minus release time), and the horizon. We empirically establish the phase transition and look for an easy-hard-easy pattern for this family using several common solvers. While in many combinatorial problems a phase transition coincides with typically hard instances, whether or not that is the case with SMS remains an open question, and merits further study.

Full Text: PDF