A new hybrid heuristic algorithm for the Precedence Constrained Production Scheduling Problem: A mining application

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.