Serial and Parallel Approaches to Resource Constrained Project Scheduling Problems

Document Type : مقالات

Authors

• Hamed. R Tareghian ¹
• Majid Salari ²

¹ ferdowsi

² Ferdowsi University of Mashhad

https://doi.org/10.22067/pmt.v1i1.2254

Abstract

Resource constrained project scheduling (RCPS) is a NP-hard optimization problem. One approach to solve this problem is to use priority rule based methods. In this paper we implement eleven most widely used priority rules in parallel and in serial. Using 120 standard test problems each containing from 30 to 120 activities, we compared the performance of serial and parallel implementations of priority rules in solving RCPS problems yielding shorter project make spans. The results showed that the parallel implementation of priority rules gives more efficient results. Furthermore, to benefit from the parallel implementation of priority rules, it is only necessary to combine up to three arbitrary priority rules.

Keywords

• Resource constrained project scheduling problem
• Heuristics

References

1. Alcaraz, J., Maroto, C. and Ruiz, R. (2004), Improving the performance of genetic algorithms for the RCPS problem. Proceedings of the Ninth International Workshop on Project Management and Scheduling, Nancy, 40–43.

2. Boctor, F. (1990), Some efficient multi-heuristic procedures for resource-constrained project scheduling. European Journal of O.R., 49, 3-13.

3. Brucker, P., Schoo, A. and Thiele, O. (1998), A branch and bound algorithm for the resource constrained project scheduling problem. European Journal of O.R., 17, 143-158.

4. Carruthers, J. A. and Battersby, A. Advances in critical path methods. Operational Research Quarterly, 17, 359-380.

5. Coelho, J. and Tavares, L. (2003), Comparative analysis of meta–heuristics for the resource constrained project scheduling problem. Technical report, Department of Civil Engineering, Instituto Superior Tecnico, Portugal.

6. Debels, D., De Reyck, B., Leus, R. and Vanhoucke, M. (2006), A hybrid scatter search Electromagnetism meta–heuristic for project scheduling. European Journal of Operational Research, 169(2), 638-653.

7. Deckro, R. F., Winkofsky, E. P., Hebert, J. E. and Gagnon, R., (1991), A decomposition approach to multi-project scheduling. European Journal of O.R., 51, 110-118.

8. Demeulemeester, E. and Herroelen, W. (1997), New benchmark results for the resource-constrained project scheduling problem. Management Science, 43, 1485-1492.

9. Drexl, A. and Grunewald, J. (1993), Nonpreemptive multi-mode resource constrained project scheduling. IIE Trans., 25, 74-81.

10. Fleszar, K. and Hindi, K. (2004), Solving the resource–constrained project scheduling problem by a variable neighbourhood search. Euro. J. Operational Research, 155, 402–413.

11. Hajdu, M. (1997), Network Scheduling Techniques for Construction Project Management. Kluwer Academic Publishers.

12. Herroelen, W., De Reyck, B. and Demeulemeester, E. (1998), Resource-constrained project scheduling: A survey of recent developments. Computers Ops Res., 25, 4, 279-302.

13. Icmeli, O. and Rom, W. O., (1996), solving the resource-constrained project scheduling problem with optimization subroutine library. Computers and O. R., 23, 801-817.

14. Kelly, J. E., Jr. The critical path method: Resource planning and scheduling. Ch. 21 in Industrial Scheduling, J.F. Muth and G.L. Thompson (eds.), Prentice-Hall, Englewood Cliffs, NJ, 347-365.

15. Kolisch, R., and Hartmann, S. (2006), Experimental Investigation of Heuristics for Resource-Constrained Project Scheduling: An Update. European Journal of Operations Research, 174, 23-37.

16. Kolisch, R. and Sprecher. A. (1996), PSPLIB – A project scheduling problem library. European Journal of O.R., 96, 205-216.

17. Kolisch, R., Sprecher, A. and Drexl, A. (1995), Characterization and generation of a general class of resource-constrained project scheduling problem. Mngmt Sci., 41, 10, 1693-1703.

18. Merkle, D., Middendorf, M. and Schmeck. H. (2002), Ant colony optimization for resourceconstrained project scheduling. IEEE Transactions on Evolutionary Computation, 6, 333–346.

19. Mohring, R., Schulz, A., Stork, F., and Uetz, M. (2003), Solving project scheduling problems by minimum cut computations. Management Science, 49, 3, 330-350.

20. Nonobe, K. and Ibaraki, T. (2002), Formulation and tabu search algorithm for the resource constrained project scheduling problem. In C. C. Ribeiro and P. Hansen, editors, Essays and Surveys in Metaheuristics,. Kluwer Academic Publishers, 557–588.

21. Petrovic, R. (1968), Optimisation of resource allocation in project planning. Operations Research, 16, 559-586.

22. Sprecher, A. (2002), Network decomposition techniques for resource-constrained project scheduling. Journal of the Operational Research Society, 53, 4, 405–414.

23. Tareghian, H. R., Farahi, M. H. and Moarrab, M. (2007), Solving Resource Constrained Scheduling Problem by Genetic Algorithm. Shahid Chamran Univ. Journal of Science, 16, 24-35.

24. Tormos P. and Lova, A. (2003), An efficient multi-pass heuristic for project scheduling with constrained resources. International J. of Production Research, 41, 5, 1071–1086.

25. Valls, V., Perez, M. A. and Quintanilla, M. S. (2004), Justification and RCPSP: A technique that pays. European Journal of Operations Research, 152, 134-149.

26. Wiest, J. D. (1963), The scheduling of large projects with limited resources. Ph.D.