A new hybrid heuristic algorithm for the Precedence Constrained Production Scheduling Problem: A mining application. (July 2020)

• Record Type: Journal Article
• Authors: Jélvez, Enrique; Morales, Nelson; Nancel-Penard, Pierre; Cornillier, Fabien
• Is Part Of: Omega. Volume 94(2020)
• Publication Date: 2020-07
• Subjects: Precedence constrained production scheduling -- Open-pit mine production planning -- Hybrid heuristic -- Mixed-integer linear programming; Management -- Periodicals; 658.4005
• DOI: 10.1016/j.omega.2019.03.004
• Languages: English
• ISSNs: 0305-0483

Abstract

Highlights: A new hybrid heuristic for the Precedence-Constrained Production Scheduling Problem is proposed based on a decomposition into subproblems on a rolling horizon basis. The LP relaxation is used in a preselection procedure to efficiently reduce the size of the subproblems. Near-optimal feasible solutions are reported, improving the best-known results for a series of instances of the literature. The first feasible solution is also reported for an extremely large instance. Abstract: 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.