TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)2010

COGA 5-Wheel

Page Content

to Navigation

Preprints 2010

A Branch-and-Price Algorithm for Multi-Mode Resource Leveling
Citation key Report-004-2010
Author Eamonn T. Coughlan and Marco E. Lübbecke and Jens Schulz
Year 2010
Number 004
Month feb
Institution Technische Universität Berlin, Institut für Mathematik
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.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe