ITEM VIEW

Resource constrained project scheduling models and algorithms applied to underground mining

dc.contributor.advisorVan Vuuren, J. H.en_ZA
dc.contributor.authorTerblanche, S. E.en_ZA
dc.contributor.otherStellenbosch University. Faculty of Engineering. Dept. of Industrial Engineering.en_ZA
dc.date.accessioned2017-11-22T08:02:04Z
dc.date.accessioned2017-12-11T11:20:02Z
dc.date.available2017-11-22T08:02:04Z
dc.date.available2017-12-11T11:20:02Z
dc.date.issued2017-12
dc.identifier.urihttp://hdl.handle.net/10019.1/102979
dc.descriptionThesis (PhD)--Stellenbosch University, 2017.en_ZA
dc.description.abstractENGLISH 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.en_ZA
dc.description.abstractAFRIKAANSE 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.af_ZA
dc.format.extent139 pages : illustrationsen_ZA
dc.language.isoen_ZAen_ZA
dc.publisherStellenbosch : Stellenbosch Universityen_ZA
dc.subjectResource Constrained Project Scheduling Problem (RCSP)en_ZA
dc.subjectUCTDen_ZA
dc.subjectComputer algorithmsen_ZA
dc.subjectMineral industries -- Project scheduling (Production control)en_ZA
dc.subjectMining engineering -- Mathematical modelsen_ZA
dc.titleResource constrained project scheduling models and algorithms applied to underground miningen_ZA
dc.typeThesisen_ZA
dc.rights.holderStellenbosch Universityen_ZA


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

ITEM VIEW