A note on flow-based formulations for solving resource constrained scheduling problems
Date
2017
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Operations Research Society of South Africa
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
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.
Description
CITATION: Terblanche, S. E. & Van Vuuren, J. H. 2017. A note on ow-based formulations for solving resource constrained scheduling problems. ORiON, 33(1):21-34, doi:10.5784/33-1-555.
The original publication is available at http://orion.journals.ac.za
The original publication is available at http://orion.journals.ac.za
Keywords
Scheduling, Time management, Flow-based formulations, Integer programming, Inequalities (Mathematics), Linear progamming, Binary system (Mathematics) -- Decision
Citation
Terblanche, S. E. & Van Vuuren, J. H. 2017. A note on ow-based formulations for solving resource constrained scheduling problems. ORiON, 33(1):21-34, doi:10.5784/33-1-555