Optimization Online


A branch-and-price algorithm for multi-mode resource leveling

Eamonn T. Coughlan (coughlan***at***math.tu-berlin.de)
Marco E. Lübbecke (luebbecke***at***mathematik.tu-darmstadt.de)
Jens Schulz (jschulz***at***math.tu-berlin.de)

Abstract: Resource leveling is a variant of resource-constrained project scheduling in which a non-regular objective function, the resource availability cost, is to be minimized. We present a branch-and-price approach together with a new heuristic to solve the more general turnaround scheduling problem. Besides precedence and resource constraints, also availability periods and multiple modes per job have to be taken into account. Time-indexed mixed integer programming formulations for similar problems quite often fail already on instances with only 30 jobs, depending on the network complexity and the total freedom of arranging jobs. A reason is the typically very weak linear programming relaxation. In particular for larger instances, our approach gives tighter bounds, enabling us to optimally solve instances with 50 multi-mode jobs.

Keywords: integer programming, branch-and-price, scheduling

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

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Citation: TU Berlin, Institut für Mathematik, Preprint 2010/04

Download: [PDF]

Entry Submitted: 03/01/2010
Entry Accepted: 03/02/2010
Entry Last Modified: 04/13/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