Resource constrained project scheduling with flexible resource usage profiles: Models, Methods, and Applications
Final Report Abstract
This research project addresses the resource-constrained project scheduling problem with flexible resource profiles (FRCPSP). Such a problem often arises in many real-world applications, in which the resource usage of each activity is not merely constant, but may vary from period to period. As such, the activity duration cannot be known a priori. The challenge of FRCPSP, thus, remains to simultaneously determine the schedule and resource profiles of each activity in order to minimize the makespan, subject to precedence relationships, resource requirements and availability, usage bounds and block lengths, and coordinated usages for each activity that requires multiple resources. Based on the applicability of naturally dividable resources, all resources are assumed continuous and renewable. The research is categorized into two time systems, namely the discrete-time (DT) and the continuous-time (CT). Under the DT system, each activity must start and end at these predetermined, discrete time points, often resulting in a suboptimal makespan and excessive resource usage. While the CT system is not new in scheduling of the continuous processes, it is rather novel in the project scheduling that has been limited to the DT system. Tasks in nowadays’ globalization are no longer limited to discrete periods. Rather, they may be immediately started or continued in another part of the world and executed in continuous time. This project studies the FRCPSP in both time systems and especially for the first time in the CT system. For each time system, mathematical model(s) and solution methods are examined. For the discrete-time FRCPSP, seven mixed-integer programming models are formulated and evaluated in terms of solution quality and computational times. The comparative results clearly show significant dominance of the variable intensity based model in all performance measures. Both hybrid and decomposition-based metaheuristic methods are further proposed to solve the FRCPSP more efficiently. The computational evaluations suggest these methods as promising and may be extended as further research to efficiently solve the continuous-time FRCPSP. For the continuous-time FRCPSP, one event-based, mixed-integer programming model is proposed, together with an event estimation method to map the time to the event parameters. The computational results reveal the potential of the continuous-time model to reduce the makespan from the discrete-time counterpart. Nevertheless, the model suffers significantly from the long computational time, mainly due to (1) the complex structure of the model and (2) the large number of symmetrical solutions that yield the same makespan. The inequalities and heuristic time conditions are subsequently applied as cuts to speed up the branch-and-cut procedure. Although effective in the small problem size, they are still inefficient to handle the larger problem size. Further attempts to apply the generalized flow cover inequalities so far have not yet brought satisfactory outcomes. This challenge awaits further research. Other further research may involve an application of column generation and/or branch-price-cut in solving the FRCPSP, possibly with perturbation of the objective coefficients, symmetry breaking inequalities, and orbital branching. Efforts to create a new instance generator and an extension of the PSPLIB library of standard test problems and industrial problems may also be continued.
Publications
- (2014). A genetic algorithm for the resource-constrained project scheduling problem with flexible resource profiles. Proceedings of the 14th International Conference on Project Management and Scheduling, March 30 – April 2, 2014, Technische Universität München, Munich, Germany
Tritschler, M., Naber, A., & Kolisch, R.
- (2014). MIP models for resource-constrained project scheduling with flexible resource profiles. European Journal of Operational Research, 239, 335-348
Naber, A. & Kolisch, R.
(See online at https://doi.org/10.1016/j.ejor.2014.05.036) - (2014). The Resource-Constrained Project Scheduling Model of Bianco and Caramia: Clarifications and an Alternative Model Formulation. Flexible Services and Manufacturing Journal, 26, 454-459
Naber, A., Kolisch, R., Bianco, L., & Caramia, M.
(See online at https://doi.org/10.1007/s10696-014-9197-8) - A hybrid metaheuristic for resource-constrained project scheduling with flexible resource profiles. European Journal of Operational Research, Volume 262, Issue 1, 1 October 2017, Pages 262-273
Tritschler, M., Naber, A., & Kolisch, R.
(See online at https://doi.org/10.1016/j.ejor.2017.03.006) - Resource-constrained project scheduling with flexible resource profiles in continuous time. Computers & Operations Research Volume 84, August 2017, Pages 33-45
Naber, A.
(See online at https://doi.org/10.1016/j.cor.2017.02.018)
