Production scheduling of open-pit mines is an important problem arising in surface mine planning as it determines the raw materials to be produced yearly over the life of the mine, assesses the value of the mine, and contributes to the sustainable utilization of mineral resources. Finding the optimal schedule is a complex task, involving large data sets and multiple constraints. This paper introduces a two-phase hybrid solution method. The first phase relies on solving a series of linear programming problems to generate an initial solution. In the second phase, a variable neighborhood descent procedure is applied to improve the solution. Upper bounds provided by CPLEX are used to evaluate the efficiency of the proposed method. Its performance is also assessed by comparing it to recent solution methods proposed in the literature and to an alternate method implemented in commercial mine planning software commonly used by professional mine planners. The results of these computational experiments indicate the efficiency of the proposed method and its superiority over the other methods. It finds excellent solutions (within less than 3.2 % of optimality on average) for large instances of the problem in a few seconds up to a few minutes. It also provides new best-known solutions for benchmark instances from the literature, and it can solve instances recently-published algorithms have found intractable.
13 September 2011 in Computational Optimization and Applications
The cell formation problem is extensively studied in the literature, but very few authors have proposed exact methods. In this paper a linear binary programming formulation is introduced to generate a solution for the cell formation problem. To verify the behaviour of the proposed model, a set of 35 benchmark problems is solved using the branch and cut method implemented in the IBM ILOG CPLEX 10.11 Optimiser. Moreover, these results allow us to validate the quality of the solution generated with heuristic methods proposed in the literature. This experimentation indicates that, for the smaller problems, the best-known solutions are the same as those generated with CPLEX 10.11 Optimiser. These results indicate a fair confidence in the optimality of the best-known solutions generated by the heuristic methods. Furthermore, our approach is the first exact method providing results of this quality.
9 February 2014 in Mathematical Programming Computation