A real-world mine excavators timetabling methodology in open-pit mining

In the literature of mining optimisation, most classical mine block sequencing or open-pit mine production scheduling problems are applied at strategic and tactical levels, because their objectives are to determine the optimal sequence of mineral blocks across a certain number of fixed time-length periods (measured in weeks, months or years) such that the total revenue is maximised. The application of continuous-time machine scheduling theory to mine equipment timetabling is challenging and rare in the current mining literature. In this study, inspired by microscopic scheduling requirements (measured in hours, minutes and seconds) in the iron ore open-pit mining industry, a new short-term Mine Excavators Timetabling (MET) problem is introduced and defined. The MET simultaneously assigns mine blocks to excavators and decides the sequencing of assigned blocks for each excavator so that the detailed scheduling of starting and completion time for excavation of each block is determined. Different from discrete periods in the classical mining optimisation problems, timing factors in the proposed MET are continuous and precise. The proposed MET aims at minimising the total weighted tardiness (delay cost) and the total weighted movement time (relocation cost) at the operational level. By analysing the key characteristics of excavating operations, the MET problem is transformed into a specific type of continuous-time machine scheduling problem, which is an innovative application to operational-level mining equipment management. Based on extensive computational experiments by mixed integer programming, a dominance-based constructive algorithm and a hybrid Tabu-Search Threshold-Accepting metaheuristic algorithm, theoretical insights and practical benefits are discussed in depth for real-world implementations. In comparison to the exact MIP solver (ILOG-CPLEX), computational experiments indicate that the proposed hybrid metaheuristic can obtain the same optimal solutions of small-size instances but with over 240 times less computational time. For solving medium-size instances, the proposed hybrid metaheuristic also outperforms ILOG-CPLEX in both solution quality and computational times (10.94 times better solution with 38.36 times less computational time on average). A sensitivity analysis under different scenarios is conducted to determine the saturation number of excavators with the best cost-effectiveness ratio in a demand-responsive scheduling horizon. The result analyses validate that the implementation of the optimised extraction timetable can significantly reduce the total relocation cost of excavators for large-size instances.