TY - JOUR

T1 - A recursive time aggregation-disaggregation heuristic for the multidimensional and multiperiod precedence-constrained knapsack problem

T2 - An application to the open-pit mine block sequencing problem

AU - Nancel-Penard, Pierre

AU - Morales, Nelson

AU - Cornillier, Fabien

N1 - Publisher Copyright:
© 2022 Elsevier B.V.

PY - 2022/12/16

Y1 - 2022/12/16

N2 - A recursive time aggregation-disaggregation (RAD) heuristic is proposed to solve large-scale multidimensional and multiperiod precedence-constrained knapsack problems (MMPKP) in which a profit is maximized by filling the knapsack in multiple periods while satisfying minimum and maximum resource consumption constraints per period as well as precedence constraints between items. An important strategic planning application of the MMPKP in the mining industry is the well-known open-pit mine block sequencing problem (BSP). In the BSP, a mine is modeled as a three-dimensional grid of blocks to determine a block extraction sequence that maximizes the net present value while satisfying constraints on the shape of the mine and resource consumption over time. Large real-life instances of this problem are difficult to solve, particularly with lower bounds on resource consumption. The advantage of the time aggregation-disaggregation heuristic over a rolling-horizon-based time decomposition is twofold: first, the entire horizon is considered for the resource consumption from the first aggregation; and second, only two-period subproblems have to be solved. This method is applied to a well-known integer programming model and a variant thereof in which blocks can be extracted in parts over multiple periods. Tests on benchmark instances show that near-optimal solutions for both of the models can be obtained for extremely large instances with up to 2,340,142 blocks and 10 periods.

AB - A recursive time aggregation-disaggregation (RAD) heuristic is proposed to solve large-scale multidimensional and multiperiod precedence-constrained knapsack problems (MMPKP) in which a profit is maximized by filling the knapsack in multiple periods while satisfying minimum and maximum resource consumption constraints per period as well as precedence constraints between items. An important strategic planning application of the MMPKP in the mining industry is the well-known open-pit mine block sequencing problem (BSP). In the BSP, a mine is modeled as a three-dimensional grid of blocks to determine a block extraction sequence that maximizes the net present value while satisfying constraints on the shape of the mine and resource consumption over time. Large real-life instances of this problem are difficult to solve, particularly with lower bounds on resource consumption. The advantage of the time aggregation-disaggregation heuristic over a rolling-horizon-based time decomposition is twofold: first, the entire horizon is considered for the resource consumption from the first aggregation; and second, only two-period subproblems have to be solved. This method is applied to a well-known integer programming model and a variant thereof in which blocks can be extracted in parts over multiple periods. Tests on benchmark instances show that near-optimal solutions for both of the models can be obtained for extremely large instances with up to 2,340,142 blocks and 10 periods.

KW - Heuristics

KW - Integer programming

KW - Multidimensional and multiperiod precedence-constrained knapsack problem

KW - Open pit mine scheduling

KW - Time decomposition

UR - http://www.scopus.com/inward/record.url?scp=85132668946&partnerID=8YFLogxK

U2 - 10.1016/j.ejor.2022.04.005

DO - 10.1016/j.ejor.2022.04.005

M3 - Article

AN - SCOPUS:85132668946

SN - 0377-2217

VL - 303

SP - 1088

EP - 1099

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 3

ER -