On some implementations of solving the resource constrained project scheduling problems
DOI:
https://doi.org/10.2298/YJOR171115025GKeywords:
Project management, Resource constrained project scheduling problem, Renewable resources, Cumulative resources, Branch and bound algorithms, PCPLIBAbstract
We consider a resource-constrained project scheduling problem with respect to the makespan minimization criterion. The problem accounts for technological constraints of activities precedence together with resource constraints. Activities pre- emptions are not allowed. The problem with renewable resources is NP-hard in the strong sense. We propose an exact branch and bound algorithm for solving the problem with renewable resources. It uses our new branching scheme based on the representation of a schedule in form of the activity list. We use two approaches of constructing the lower bound. We present results of numerical experiments, illustrating the quality of the proposed lower bounds. The test instances are taken from the library of test instances PSPLIB.References
Baptiste, P., Demassey, S., Tight LP bounds for resource constrained project scheduling, OR Spectrum, 26 (2) (2004) 251-262.
Blazewicz, J., Lenstra, J.K., Rinnoy Kan, A.H.G., Scheduling Subject to Resource Constraints: Classification and Complexity, Discrete Applied Math., 5 (1) (1983) 11-24.
Brucker, P., Drexl, A., Mohring, R., et al., Resource-Constrained Project Scheduling: Notation, Classification, Models, and Methods, European Journal of Operational Research, 112 (1) (1999) 3-41.
Brucker, P., Knust, S., Schoo, A., Thiele, O., A branch and bound algorithm for the resource-constrained project scheduling problem, European Journal of Operational Research, 107 (1998) 272-288.
Chen, T., Zhou, G., Research on Project Scheduling Problem with Resource Constraints, Journal of Software, 8 (8) (2013) 2058-2063.
Demeulemeester, E., Herroelen, W., A branch and bound procedure for the multiple resource-constrained project scheduling problem, Management Science, 38 (1992) 1803-1818.
Gimadi, E. Kh., On Some Mathematical Models and Methods for Planning Large-Scale Projects, Models and Optimization Methods, in Proc. AN USSR Sib. Branch, Math. Inst., Novosibirsk: Nauka, 10 (1988) 89-115.
Gimadi, E.Kh., Zalyubovskii, V.V., Sevastyanov, S.V., Polynomial Solvability of Scheduling Problems with Storable Resources and Deadlines, Diskret. Anal. Issled. Oper., Ser. 2, 7 (1) (2000) 9-34.
Goncharov, E.N., Stochastic Greedy Algorithm for the Resource-Constrained Project Scheduling Problem, Diskret. Anal. Issled. Oper., 21 (3) (2014) 10-23.
Goncharov, E.N., Leonov, V.V., Genetic Algorithm for the Resource-Constrained Project Scheduling Problem, Automation and Remote Control, 78 (6) (2017) 1101-1114.
Herroelen, W., Demeulemeester, E., De Reyck, B., A Classification Scheme for Project Scheduling, in: J. Weglarz (ed.), Project Scheduling-Recent Models, Algorithms and Applications, International Series in Operations Research and Management Science, Kluwer Acad. Publish., Dordrecht, 14 (Chapter 1) (1998) 77-106.
Kolisch, R., Hartmann, S., Heuristic Algorithms for Solving the Resource-Constrained Project Scheduling Problem: Classification and Computational Analysis, in: Weglarz, J. (ed.), Project Scheduling: Recent Models, Algorithms and Applications, Kluwer Acad. Publish., (1999) 147-178.
Kolisch, R., Sprecher, A., PSPLIB-a Project Scheduling Problem Library, European Journal of Operational Research, 96 (1997) 205-216. (downloadable from http://www.om-db.wi.tum.de/psplib/)
Mingozzi, A., Maniezzo, V., Ricciardelli, S., Bianco, L., An exact algorithm for the resource-constrained project scheduling problem based on a new mathematical formulation, Management Science, 44 (1998) 715-729.
Servah, V.V., An effectively solvable case of a scheduling problem with renewable resources, Diskret. Anal. Issled. Oper., Ser. 2, 7 (1) (2000) 75-82.
Sprecher, A., Scheduling Resource-Constrained Projects Competitively at Modest Resource Requirements, Management Science, 46 (2000) 710-723.
Stinson, J.P., Davis, E.W., Khumawala, B.M., Multiple Resource-Constrained Scheduling Using Branch and Bound, AIIE Transactions, 10 (1978) 252-259.
Ullman, J.D., NP-complete scheduling problems, Journal of Computer and System Sciences, 10 (3) (1975) 284-393.
Downloads
Published
Issue
Section
License
Copyright (c) 2019 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
