Resource constrained project scheduling models and algorithms applied to underground mining
Date
2017-12
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
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 than
or 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 frequently
applied 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, but
which 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 employing
RCSP 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 include
the modelling of uncertainty in resource requirements as well as the formulation of scheduling
models 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 of
net 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 feasible
solutions 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.
AFRIKAANSE OPSOMMING: Die hulpbronbeperkte skeduleringsprobleem (HBSP) behels die skedulering van 'n aantal aktiwiteite oor verloop van tyd, waar elke aktiwiteit 'n eenheid van 'n sekere hulpbron per tydeenheid verbruik. Vir 'n haalbare oplossing om te bestaan, moet die totale hulpbron verbruik per tydeenheid hoogstens die beskikbare hulpbronne wees. Die volgorde waarin aktiwiteite geskeduleer kan word, word verder deur 'n voorrang-grafiek bepaal. Die punte van hierdie gerigte grafiek verteenwoordig die verskillende aktiwiteite en elke boog dui op 'n voorrang verhouding. Modelformulerings vir verskeie variasies op die HBSP kan in die literatuur gevind word, asook 'n verskeidenheid oplosmetodes. Van die mees gewilde doelfunksies behels die minimering van die totale projekduur, die minimering van 'n traagheids-strafkoste, en die maksimering van die netto teenswoordige waarde. Die ontwikkeling van praktiese rekenaartegnologie in die laat 1950s het beteken dat verskeie bedryfsprobleme nou ook deur middel van rekenaaralgoritmes opgelos kan word. Dit het egter gou duidelik geword dat sekere tipes probleme inherent moeilik is en dat dit in sommige gevalle selfsonmoontlik is om hierdie probleme op te los. Tot op hede bestaan daar selfs skeduleringsprobleme wat nie meer as 60 aktiwiteite het nie, en wat nie optimaal binne 'n redelike tydsverloop opgelos kan word nie, selfs al word daar van die nuutste rekenaartegnologie en algoritmes gebruik gemaak. In hierdie proefskrif word die uitdagings van ondergrondse mynboubeplanning aangespreek deur gebruik te maak van HBSP modelle en algoritmes. Ondergrondse mynboubeplanning behels die skedulering van mynboubedrywighede op s o 'n wyse dat die mees ekonomiese waarde daaruit geput kan word. Dit moet gedoen word in aggenome sekere vereistes ten opsigte van hulpbronbeperkings, asook beperkings wat daar gestel word deur die siese infrastruktuur van die myn. Van spesi eke belang is die uitbreiding van bestaande HBSP modelle om mynbou-spesi eke vereistes aan te spreek. 'n Voorbeeld hiervan is die modellering van toelaatbare vertragingstyd, vir wanneer groot masjinerie in 'n gemeganiseerde mynbou omgewing van een punt na 'n ander vervoer moet word. Besonderhede van reeds bestaande HBSP modelle word in hierdie proefskrif voorgehou. Empiriese toetse word gebruik om die toepaslikheid van hulpbron vloei-gebaseerde formulerings vir die oplos van die mynbouskeduleringsprobleem te staaf. Aanpassings word vir die hulpbron vloeigebaseerde formulering voorgestel om sodoende die maksimering van die netto huidige waarde te akkommodeer. Verskeie herformulerings word voorgestel as gevolg van die noemenswaardige berekeningskompleksiteit van die ondergrondse mynbouskeduleringsprobleem. Verder word 'n Benders ontbindingsbenadering beskryf wat in staat is om die berekeningstyd van oplossings vir groot probleemgevalle te verminder. Resultate wat in hierdie proefskrif gerapporteer word, is gebaseer op beide lukraak-gegenereerde data en data wat afkomstig is van 'n Suid-Afrikaanse ondergrondse myn. Die bevindings van hierdie studie is dat die model wat die beste vaar, gebruik maak van 'n hulpbron vloei-gebaseerde formulering, in samewerking met 'n formuleringsbenadering wat 'n verminderde aantal veranderlikes en beperkings tot gevolg het. Die resultate vir die Benders ontbindingsbenadering wys daarop dat die metode skaalbaar is vir probleemgevalle met 'n groot aantal aktiwiteite en hulpbronne. Dit is 'n belangrike bydrae in die konteks van mynbou, veral in ag geneem dat 'n groot aantal hulpbronne in die oplossing van ondergrondse mynbouskeduleringsprobleme beskou moet word.
AFRIKAANSE OPSOMMING: Die hulpbronbeperkte skeduleringsprobleem (HBSP) behels die skedulering van 'n aantal aktiwiteite oor verloop van tyd, waar elke aktiwiteit 'n eenheid van 'n sekere hulpbron per tydeenheid verbruik. Vir 'n haalbare oplossing om te bestaan, moet die totale hulpbron verbruik per tydeenheid hoogstens die beskikbare hulpbronne wees. Die volgorde waarin aktiwiteite geskeduleer kan word, word verder deur 'n voorrang-grafiek bepaal. Die punte van hierdie gerigte grafiek verteenwoordig die verskillende aktiwiteite en elke boog dui op 'n voorrang verhouding. Modelformulerings vir verskeie variasies op die HBSP kan in die literatuur gevind word, asook 'n verskeidenheid oplosmetodes. Van die mees gewilde doelfunksies behels die minimering van die totale projekduur, die minimering van 'n traagheids-strafkoste, en die maksimering van die netto teenswoordige waarde. Die ontwikkeling van praktiese rekenaartegnologie in die laat 1950s het beteken dat verskeie bedryfsprobleme nou ook deur middel van rekenaaralgoritmes opgelos kan word. Dit het egter gou duidelik geword dat sekere tipes probleme inherent moeilik is en dat dit in sommige gevalle selfsonmoontlik is om hierdie probleme op te los. Tot op hede bestaan daar selfs skeduleringsprobleme wat nie meer as 60 aktiwiteite het nie, en wat nie optimaal binne 'n redelike tydsverloop opgelos kan word nie, selfs al word daar van die nuutste rekenaartegnologie en algoritmes gebruik gemaak. In hierdie proefskrif word die uitdagings van ondergrondse mynboubeplanning aangespreek deur gebruik te maak van HBSP modelle en algoritmes. Ondergrondse mynboubeplanning behels die skedulering van mynboubedrywighede op s o 'n wyse dat die mees ekonomiese waarde daaruit geput kan word. Dit moet gedoen word in aggenome sekere vereistes ten opsigte van hulpbronbeperkings, asook beperkings wat daar gestel word deur die siese infrastruktuur van die myn. Van spesi eke belang is die uitbreiding van bestaande HBSP modelle om mynbou-spesi eke vereistes aan te spreek. 'n Voorbeeld hiervan is die modellering van toelaatbare vertragingstyd, vir wanneer groot masjinerie in 'n gemeganiseerde mynbou omgewing van een punt na 'n ander vervoer moet word. Besonderhede van reeds bestaande HBSP modelle word in hierdie proefskrif voorgehou. Empiriese toetse word gebruik om die toepaslikheid van hulpbron vloei-gebaseerde formulerings vir die oplos van die mynbouskeduleringsprobleem te staaf. Aanpassings word vir die hulpbron vloeigebaseerde formulering voorgestel om sodoende die maksimering van die netto huidige waarde te akkommodeer. Verskeie herformulerings word voorgestel as gevolg van die noemenswaardige berekeningskompleksiteit van die ondergrondse mynbouskeduleringsprobleem. Verder word 'n Benders ontbindingsbenadering beskryf wat in staat is om die berekeningstyd van oplossings vir groot probleemgevalle te verminder. Resultate wat in hierdie proefskrif gerapporteer word, is gebaseer op beide lukraak-gegenereerde data en data wat afkomstig is van 'n Suid-Afrikaanse ondergrondse myn. Die bevindings van hierdie studie is dat die model wat die beste vaar, gebruik maak van 'n hulpbron vloei-gebaseerde formulering, in samewerking met 'n formuleringsbenadering wat 'n verminderde aantal veranderlikes en beperkings tot gevolg het. Die resultate vir die Benders ontbindingsbenadering wys daarop dat die metode skaalbaar is vir probleemgevalle met 'n groot aantal aktiwiteite en hulpbronne. Dit is 'n belangrike bydrae in die konteks van mynbou, veral in ag geneem dat 'n groot aantal hulpbronne in die oplossing van ondergrondse mynbouskeduleringsprobleme beskou moet word.
Description
Thesis (PhD)--Stellenbosch University, 2017.
Keywords
Resource Constrained Project Scheduling Problem (RCSP), UCTD, Computer algorithms, Mineral industries -- Project scheduling (Production control), Mining engineering -- Mathematical models