Inhalt des Dokuments
Preprint 04-2010
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- A Branch-and-Price Algorithm for Multi-Mode Resource Leveling
- Authors
- Eamonn T. Coughlan, Marco E. Lübbecke, and Jens Schulz
- Classification
-
not available
- Keywords
-
branch-and-price, scheduling, multi-mode, resource leveling
- 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.
- Source
- Download as [PDF]
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe