AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / Proceedings of the International Conference on Automated Planning and Scheduling, 27 > Book One

An Investigation of Phase Transitions in Single-Machine Scheduling Problems

Authors

Zhihui Wang,Bryan O'Gorman,Tony Tran,Eleanor Rieffel,Jeremy Frank,Minh Do

NASA Ames Research Center,NASA Ames Research Center,University of Toronto,NASA Ames Research Center,NASA Ames Research Center,NASA Ames Research Center


Proceedings:

Book One

Volume

Issue:

Proceedings of the International Conference on Automated Planning and Scheduling, 27

Track:

Main Track

Downloads:

Download PDF

Abstract:

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.

DOI:

10.1609/icaps.v27i1.13829


ICAPS

Proceedings of the International Conference on Automated Planning and Scheduling, 27