New cutting planes for open-pit mine scheduling with multi-period block extraction
针对多周期块体开采的露天矿生产调度问题，提出包含两种调度变量的新MILP模型，并引入新割平面族，实验表明计算时间最多降低70.3%。
The open-pit mine production scheduling problem (OPMPSP) is a fundamental planning problem in mining engineering. Given a discretized ore body representation known as a block model, the OPMPSP consists in computing the schedule of block excavation (extraction time, quantity, and processing decisions) over a planning horizon while adhering to operational constraints and maximizing the net present value of the profit. This problem is typically modeled using a large-sized mixed-integer linear programming (MILP) formulation. In this paper, we focus on an OPMPSP involving blocks of varying sizes that can be extracted over multiple periods. For this problem, we propose a new MILP formulation that includes two types of scheduling variables, one indicating the starting period of the extraction of a block and the other its ending period. Considering these two variable types allows to introduce new versions of known cutting planes as well as new cut families that are defined for blocks requiring multiple periods to be extracted. All cuts are generated a priori and added to the MILP formulation which is then solved by a commercial MILP solver. Through extensive computational experiments on three real-life OPMPSP instances, we demonstrate that the proposed cuts significantly reduce computational times (by up to 70.3%), making a valuable contribution to large-scale mine planning optimization. This methodology is also integrated into a rolling-horizon heuristic, where the cutting planes can be updated at each iteration.