A study of the Bienstock-Zuckerberg algorithm, Applications in Mining and Resource Constrained Project Scheduling
Authors:
Preprint
Abstract
We study a Lagrangian decomposition algorithm recently proposed by Dan Bienstock and Mark Zuckerberg for solving the LP relaxation of a class of open pit mine project scheduling problems. In this study we show that the Bienstock Zuckergberg (BZ) algorithm can be used to solve LP relaxations corresponding to a much broader class of scheduling problems, including the well-known Resource Constrained Project Scheduling Problem (RCPSP), and multi-modal variants of the RCPSP that consider batch processing of jobs. We present a new, intuitive proof of correctness for the BZ algorithm that works by casting the BZ algorithm as a column generation algorithm. This analysis allows us to draw parallels with the well-known Dantzig-Wolfe (DW) algorithm. We discuss practical computational techniques for speeding up the performance of the BZ and DW algorithms on project scheduling problems. Finally, we present computational experiments independently testing the effectiveness of the BZ and DW algorithms on different sets of publicly available test instances. Our computational experiments confirm that the BZ algorithm significantly outperforms the DW algorithm for the problems considered. Our computational experiments also show that the proposed speed-up techniques can have a significant impact on solution time. We provide some insights on what might be explaining this significant difference in performance.Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Tailored Lagrangian Relaxation for the open pit block sequencing problemAnnals of Operations Research, 2013
- MineLib: a library of open pit mining problemsAnnals of Operations Research, 2012
- A solution approach for optimizing long- and short-term production scheduling at LKAB’s Kiruna mineEuropean Journal of Operational Research, 2011
- A survey of variants and extensions of the resource-constrained project scheduling problemEuropean Journal of Operational Research, 2010
- LP-based disaggregation approaches to solving the open pit mining production scheduling problem with block processing selectivityComputers & Operations Research, 2009
- Using aggregation to optimize long-term production planning at an underground mineEuropean Journal of Operational Research, 2007
- Resource-constrained project scheduling: Notation, classification, models, and methodsEuropean Journal of Operational Research, 1999
- PSPLIB - A project scheduling problem libraryEuropean Journal of Operational Research, 1997
- Project scheduling with resource constraints: A branch and bound approachEuropean Journal of Operational Research, 1987
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey1979