Resource constrained project scheduling models and algorithms applied to underground mining

[摘要] ENGLISH ABSTRACT: The resource constrained project scheduling problem (RCSP) involves the scheduling of a number of activities over time, where each activity consumes a unit of some resource per time period.For a feasible solution to exist, the total resource consumption per time period must be less thanor equal to the available resources. In addition, the order in which activities may be scheduled is determined by a precedence graph. The nodes of this directed graph represent the various activities and each directed edge a precedence relationship. A multitude of model formulations for the RCSP exist in the literature as do various solution approaches. Some of the frequentlyapplied objective functions include the minimisation of the makespan, the minimisation of a tardiness penalty cost, and the maximisation of net present value.The advent of practical computer technology during the late 1950s has meant that various industrial problems can now be solved by computer algorithms. It soon became clear, however, that certain types of problems are inherently difficult and in some cases even impossible to solve.Even today scheduling problems exist which have no more than 60 tasks to be scheduled, butwhich cannot be solved to optimality within reasonable time using the latest algorithmic and computer technology. In this dissertation, the challenges of underground mine planning are addressed by employingRCSP models and algorithms. Underground mine planning entails the scheduling of mining activities in a manner that the most economical value is derived, while satisfying constraints related to resource requirements and physical limitations due to the properties of the mine infrastructure.Modelling extensions that address mining-specific requirements are of specific interest. For instance, the modelling of transfer delay constraints are especially useful in a mechanised mining environment where the movement of large machinery from one point to another may cause significant delays in a mine production schedule. Other mining-specific requirements includethe modelling of uncertainty in resource requirements as well as the formulation of schedulingmodels that facilitate selective scheduling.Details of existing RCSP formulations in the literature are provided and results from empirical tests are presented to evaluate the suitability of adopting a resource flow-based RCSP formulation to solve the underground mine scheduling optimisation problem. Modifications to the resource flow formulation are proposed for the purpose of accommodating the maximisation ofnet present value. Due to the computational complexity of the underground mine scheduling problem, variable and constraint reduction approaches are suggested. In addition, a Benders decomposition approach is described which is capable of improving the computation of feasiblesolutions for large problem instances.Computational results presented in this dissertation are based on both randomly generated data and data from a real South African underground mine. Based on these results it is found that the best performing model reformulation involves the use of a resource ow-based model in conjunction with a constraint aggregation and graph reduction approach. The Benders decomposition approach, implemented within a branch-and-cut framework, scales well for problem instances with a large number of activities and resources. This is a significant contribution within the context of mining, especially considering the large number of resources that have to be accommodated when solving underground mine scheduling optimisation problems.

[发布机构] Stellenbosch University