Browsing by Author "Terblanche, S. E."

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    A note on flow-based formulations for solving resource constrained scheduling problems
    (Operations Research Society of South Africa, 2017-02) Terblanche, S. E.; Van Vuuren, J. H.
    ENGLISH ABSTRACT: The resource constrained scheduling problem involves the scheduling of a number of activities over time, where each activity consumes one or more resources per time period. For a feasible solution to exist, the total resource consumption per time period must not exceed the available resources. In addition, the order in which activities may be scheduled is determined by a precedence graph. In this paper, valid inequalities proposed for the resource flow-based formulation in previous studies are investigated to determine what effect they may have on computing times. It is shown empirically that improved computing times may be obtained if these valid inequalities are, in fact, omitted from the resource flow-based formulation. In addition, a heuristic is proposed for the generation of initial starting solutions and for estimating the extent of the scheduling horizon which, in turn, is required to calculate the latest starting times of activities. The computational results are based on well-known problem test instances as well as new randomly generated problem instances.
  • Thumbnail Image
    Item
    A note on flow-based formulations for solving resource constrained scheduling problems
    (Operations Research Society of South Africa, 2017) Terblanche, S. E.; Van Vuuren, J. H.
    The resource constrained scheduling problem involves the scheduling of a number of activities over time, where each activity consumes one or more resources per time period. For a feasible solution to exist, the total resource consumption per time period must not exceed the available resources. In addition, the order in which activities may be scheduled is determined by a precedence graph. In this paper, valid inequalities proposed for the resource ow-based formulation in previous studies are investigated to determine what e ect they may have on computing times. It is shown empirically that improved computing times may be obtained if these valid inequalities are, in fact, omitted from the resource ow-based formulation. In addition, a heuristic is proposed for the generation of initial starting solutions and for estimating the extent of the scheduling horizon which, in turn, is required to calculate the latest starting times of activities. The computational results are based on well-known problem test instances as well as new randomly generated problem instances.
  • Thumbnail Image
    Item
    Resource constrained project scheduling models and algorithms applied to underground mining
    (Stellenbosch : Stellenbosch University, 2017-12) Terblanche, S. E.; Van Vuuren, J. H.; Stellenbosch University. Faculty of Engineering. Dept. of Industrial Engineering.
    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.