The presence of symmetry is common in certain types of scheduling problems. Symmetry can occur when one is scheduling a collection of jobs on multiple identical machines, or if one is determining production schedules for identical machines. General symmetry-breaking methods can be strengthened by taking advantage of the special structure of the symmetry group in scheduling problems. In this paper, we examine the effectiveness of symmetry-breaking methods for scheduling problems. We also present a modified version of orbital branching, a powerful symmetry-breaking procedure, and discuss when it should and should not be used in practice. Using operating room and power generator scheduling problems as sample problems, we will provide computational results comparing different methods of symmetry breaking.
Citation
Argonne National Laboratory 9700 S. Cass Avenue Argonne, IL 60439 Nov 2010