Optimization Online


Symmetry in Scheduling Problems

James Ostrowski (jostrowski***at***anl.gov)
Miguel F. Anjos (anjos***at***stanfordalumni.org)
Anthony Vannelli (vannelli***at***uoguelph.ca)

Abstract: 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.

Keywords: Integer Programming, Scheduling, Symmetry

Category 1: Applications -- OR and Management Sciences (Scheduling )

Category 2: Integer Programming

Citation: Argonne National Laboratory 9700 S. Cass Avenue Argonne, IL 60439 Nov 2010

Download: [PDF]

Entry Submitted: 11/16/2010
Entry Accepted: 11/17/2010
Entry Last Modified: 11/17/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society