TY - JOUR
T1 - A new hybrid heuristic algorithm for the Precedence Constrained Production Scheduling Problem
T2 - A mining application
AU - Jélvez, Enrique
AU - Morales, Nelson
AU - Nancel-Penard, Pierre
AU - Cornillier, Fabien
N1 - Publisher Copyright:
© 2019 Elsevier Ltd
PY - 2020/7
Y1 - 2020/7
N2 - In this work we address the Precedence Constrained Production Scheduling Problem (PCPSP), the problem of scheduling tasks in such a way that total profit is maximized, while satisfying conditions such as precedence constraints among tasks and side constraints. A motivation for addressing this problem comes from open-pit mining industry, where the PCPSP seeks to maximize the net present value of an ore deposit by selecting the blocks (tasks) to extract, their extraction periods and their processing options, while satisfying constraints as precedences among blocks, limited availability of operational resources and maximum and/or minimum allowable concentrations of ore-grade or pollutants. Since real-world models have millions of blocks and constraints, the monolithic problem is computationally intractable. This article presents a hybrid heuristic algorithm that combines a rolling horizon decomposition with a block preselection procedure, allowing near-optimal solutions to be quickly determined. The proposed heuristic was tested on all the PCPSP instances of the MineLib library and has shown a significant improvement over the previous reported results. Moreover, a good feasible solution has been found for the instance W23, for which no solution has been previously reported.
AB - In this work we address the Precedence Constrained Production Scheduling Problem (PCPSP), the problem of scheduling tasks in such a way that total profit is maximized, while satisfying conditions such as precedence constraints among tasks and side constraints. A motivation for addressing this problem comes from open-pit mining industry, where the PCPSP seeks to maximize the net present value of an ore deposit by selecting the blocks (tasks) to extract, their extraction periods and their processing options, while satisfying constraints as precedences among blocks, limited availability of operational resources and maximum and/or minimum allowable concentrations of ore-grade or pollutants. Since real-world models have millions of blocks and constraints, the monolithic problem is computationally intractable. This article presents a hybrid heuristic algorithm that combines a rolling horizon decomposition with a block preselection procedure, allowing near-optimal solutions to be quickly determined. The proposed heuristic was tested on all the PCPSP instances of the MineLib library and has shown a significant improvement over the previous reported results. Moreover, a good feasible solution has been found for the instance W23, for which no solution has been previously reported.
KW - Hybrid heuristic
KW - Mixed-integer linear programming
KW - Open-pit mine production planning
KW - Precedence constrained production scheduling
UR - http://www.scopus.com/inward/record.url?scp=85063951577&partnerID=8YFLogxK
U2 - 10.1016/j.omega.2019.03.004
DO - 10.1016/j.omega.2019.03.004
M3 - Article
AN - SCOPUS:85063951577
SN - 0305-0483
VL - 94
JO - Omega (United Kingdom)
JF - Omega (United Kingdom)
M1 - 102046
ER -