حل مسائل زمان‌بندی پروژه با محدودیت منابع (RCPSP) با استفاده از الگوریتم رقابت استعماری اصلاح‌شده (DICA)

نوع مقاله : مقاله علمی پژوهشی

نویسندگان

1 دانشیار، مدیریت صنعتی، دانشکدۀ مدیریت دانشگاه تهران، تهران، ایران

2 دانشجوی دکتری مدیریت گرایش تحقیق در عملیات، دانشکدۀ مدیریت، دانشگاه تهران، تهران، ایران

چکیده

مسئلۀ زمان‌بندی پروژه با محدودیت منابع (RCPSP) جزء مسائل غیرچندجمله‌ای سخت (NP-Hard) است که برای حل آن، روش‌های ابتکاری و فراابتکاری در مقایسه با راه‌حل‌های دقیق، کارایی بیشتری دارند. در این تحقیق از الگوریتم رقابت استعماری اصلاح‌شده برای حل مسئلۀ زمان‌بندی پروژه با محدودیت منابع در حالت تک‌حالته و همچنین از الگوریتم محاسبۀ جواب موجه ابتدایی برای افزایش سرعت الگوریتم رقابت استعماری اصلاح‌شده با استفاده از حذف فضای غیرموجه جست‌وجو، استفاده شده است. الگوریتم ارائه‌شده در این مقاله بر روی مجموعۀ مسائل استاندارد کتابخانۀ PSPLIB آزمایش و از نظر کارایی با تعدادی از روش‌های موجود مقایسه شده است. نتایج آزمایش‌ها، کارایی و امکان‌پذیری الگوریتم پیشنهادی را در حل مسائل استاندارد زمان‌بندی پروژه با محدودیت منابع نشان می‌دهد. به‌منظور بررسی عملکرد الگوریتم در حل مسائل با داده‌های واقعی، دو پروژۀ انجام‌گرفته توسط شرکت قدس نیرو در قالب مسئلۀ مدل‌سازی و با استفاده از الگوریتم پیشنهادی حل شد.

کلیدواژه‌ها

عنوان مقاله [English]

Solving the Resource-Constrained Project Scheduling Problems (RCPSP) Using Developed Imperialistic Competition Algorithm (DICA)

نویسندگان [English]

  • Hossein Safari 1
  • Alireza Faghih 2
1 Associate Prof., Faculty of management, Tehran University, Tehran, Iran
2 Ph.D. Student in Management in field of Operations research, Faculty of Management University of Tehran, Iran
چکیده [English]

The scheduling problems are the non-polynomial problems-hard (NP-Hard), is to solve it, and meta-heuristic innovative method compared with the exact method require less time and memory.In this research, developed imperialistic competitive algorithm used to solving the single-mode resource-constrained project scheduling problem.also the basic feasible solution algorithm used in order to increase the rate of developed imperialist competetive algorithm by remove the unfeasible search space. The proposed algorithm is tested on a set of standard problems PSPLIB Library and the performance is compared with some existing methods. Test results of the proposed algorithm show effectiveness and feasibility of algorithm to solve standard problems. To evaluate the performance of algorithms for solving problems in real field, two projects that carried out by the Quds Force (supplies petrochemicals project in Kermanshah, Kermanshah Petrochemical Project Setup Utility) are modeling in RCPSP and solved by using the proposed algorithm.

کلیدواژه‌ها [English]

  • Basic Feasible Solution Algorithm Developed
  • Imperialist Competetive Algorithm
  • Project management
  • Resource Constrained Project Scheduling Problems

مراجع

  1. Agarwal, A, Colak, S, Erenguc, S (2011). A Neurogenetic approach for the resource-constrained project scheduling problem. Computers & Operations Research, 38(1), 44–50.
  2. Alamtabriz, A; Zandiye, M., Mohammadrahimi, A.R (2011). Meta-heuristic algorithms in combinatorial optimization, neural networks, simulated annealing, genetic algorithms, eta. Tehran, Safar- eshraghi press, second edition (in persian).  
  3. 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 andScheduling, 40-43.
  4. Alvarez, VR, Tamarit, J. M. (1993). The project scheduling polyhedron: Dimension, facets and lifting theorems. Eur. J.Oper. Res. 67, 204–220.
  5. Artigues, Ch, Demassey, S, Néron, Em (2008). Resource-constrained project scheduling: models, algorithms, extensions and applications. ISTE Ltd and John Wiley & Sons, Inc.
  6. Atash‌paz gargari, I (2008). Development of Social optimization algorithm and evaluate the effectiveness of this algorithm. MS Thesis, Tehran, University of Tehran (in persian).  
  7. Bagher, M., Zandieh, M., Farsijani, H. (2010). Balancing of stochastic U-type assembly lines: an imperialist competitive algorithm. International Journalof Advanced Manufacturing Technology. Volume 54, Issue 1-4, 271-285.
  8. Bartschi, W.M. (1996). A Genetic Algorithm for Resource-Constrained Scheduling. Submitted to the Department of Mechanical Engineering in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Mechanical Engineering at the Massachusetts Institute of Technology, June.
  9. Behnamian, J., Zandieh, M. (2011(. A discrete colonial competitive algorithm for hybrid flowshop scheduling to minimize earliness and quadratic tardiness penalties. Expert Systems with Applications. Volume 38, Issue 12, 14490–14498.

10. Blazewicz, J, Lenstra, J.K, Kan, A.R (2005). Scheduling Subject to Resource Constraints: Classification and complexity. Discrete Applied Mathematics. 5, 11-24.

11. Blazewicz, J., Lenstra, J., and Kan, A. R. (1983). Scheduling subject to resource constraints: Classification and complexity. Discrete Applied Mathematics, 5, 11–24.

12. Bocewicz, G, Banaszak, Z.A, Muszynski, W (2009). Decision Support Tool for Resource Allocation Subject to Imprecise Data Constraints. Control and Automation. IEEE International Conference.

13. Bouleimen, K., Lecocq, H. (2003). A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode versions. Eur. J.Oper. Res. 149, 268–281.

14. Brucker, P, Drexl, A, Mohring, R, Neumann, K, Pesch, E (1999). Resource-constrained project scheduling: Notation, classification, models, and methods. Eur. J.Oper. Res. 112, 3-41.

15. Brucker, P, Knust, S, Schoo, A, Thiele, O (1998). A branch and bound algorithm for the resource-constrained project scheduling problem. Eur. J.Oper. Res. 107, 272-288.

16. Buddhakulsomsiri, J, Kim, D. S. (2006). Priority rule-based heuristic for multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting. Eur. J.Oper. Res. 178(2): 374-390.

17. Cervantes, M, Lova, A, Tormos, P, Barber, F (2008). A Dynamic Population Steady-State Genetic Algorithm for the Resource-Constrained Project Scheduling Problem. 21st international conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems: New Frontiers in Applied Artificial Intelligence, 611 – 620.

18. Chaharsooghi, S.K. and Meimand Kermani, A.H. (2007). An effective ant colony optimization algorithm (ACO) for multi-objective resource allocation problem (MORAP). Applied Mathematics and Computation, 200,167–177.

19. Chen, P.H and Shahandashti, S.M (2008). Hybrid of genetic algorithm and simulated annealing for multiple project scheduling with multiple resource constraints. Automation in Construction. 18, 434–443.

20. Chen, R.M (2011). Particle swarm optimization with justification and designed mechanisms for resource-constrained project scheduling problem. Expert Systems with Applications. 38, 7102-7111.

21. Chen, Y.L, Hsu, P.Y, Chang, Y.B (2008). A Petri Net Approach to Support Resource Assignment in Project Management. Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on.

22. Damghani, K; Tavakoli Moghadam, R., Shahalizadeh, M. (2011). Solving Project Scheduling with resources constrains using modified ant colony algorithm. Journal of Industrial Engineering, No. 45, 59-69 (in persian).  

23. Debels, D., De Reyck, B., Leus, R. and Vanhoucke, M. (2006). A hybrid scatter search electromagnetism meta-heuristic for project scheduling. Eur. J. Oper. Res. 169, 638-653.

24. Fatemi Ghomi, S.M.T. and Ashjari, B. (2001). A simulation model for multi-projct resource allocation. International Journal of Project Management. 20, 127–130.

25. Gholipour, Y, Shahbazi, M.M. (2011). Resource-Constrained Scheduling of Construction Projects Using the Harmony Search Algorithm. Journal of Industrial Engineering. University of Tehran, Special Issue, 51-60.

26. Golenko Ginzburg, D, Gonik, A (1998). A heuristic for network project scheduling with random activity durations depending on the resource allocation. International Journal of Production Economics. 55,149–162.

27. Gorczyca, M, Janiak, A (2009). Resource level minimization in the discrete–continuous scheduling. Eur. J.Oper. Res. 203, 32–41.

28. Hartmann, S, Briskorn, S (2010). A survey of variants and extensions of the resource constrained project scheduling problem. Eur. J.Oper. Res. 207, 1-14.

29. Hartmann, S. (1998). A competitive genetic algorithm for resource-constrained project scheduling.Nav. Res. Log. 45: 733-750.

30. Hartmann, S. (2002). A self-adapting genetic algorithm for project scheduling under resource constraints. Nav. Res. Log. 49, 433-448.

31. http://www.mpsplib.com

32. Huang, C.Y, Lyu, M.R. (2005). Optimal Testing Resource Allocation and Sensitivity Analysis in Software Development. Quantum Electronics, IEEE Journal.

33. Jarboui, B., Damak, N., Damak, P. and Rebai A. (2007). A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems. Applied Mathematics and Computation. 195, 299–308.

34. Kaplan, L. (1988). Resource-constrained project scheduling with pre-emption of jobs. Unpublished PhD Dissertation, Michigan, University of Michigan.

35. Katsavounis, S (2007). Scheduling Multiple Concurrent Projects Using Shared Resources with Allocation Costs and Technical Constraints. Information and Communication Technologies: From Theory to Applications, 3rd International Conference on.

36. Kemmoe T, Sylverin, M.G, Alain Q (2007). Solving Resource-Constrained Project Scheduling Problem with Particle Swarm Optimization. In: Proceeding of 3rd Multi-disciplinary Int. Scheduling Conference, 251-258.

37. Kerzner, H (2009). Project management: a systems approach to planning, scheduling, and controlling. 10edition, John Wiley & Sons, Inc.

38. Klein, R., A. Scholl. (1999). computing lower bound by destructive improvement: An application to resource-constrained project scheduling. Eur. J.Oper. Res. 112, 322–346.

39. Kochetov, Y., Stolyar, A. (2003). Evolutionary local search with variable neighborhood for the resource constrained project scheduling problem. In:Proceeding of the 3rd International Workshopof Computer Science and InformationTechnologies.

40. Kolisch R, Drexl A. (1996). Adaptative search for solving hard project scheduling problems. NavalResearch Logistics. 43, 23–43.

41. Kolisch R., Hartmann S. (1999). Heuristic Algorithms for Solving the Resource-Constrained Project Scheduling Problem: Classification and Computational Analysis. Project scheduling: Recent models, algorithms and applications. Kluwer, Amsterdam, the Netherlands, 147-178.

42. Krüger, D, Scholl, A. (2008). A heuristic solution framework for the resource constrained (multi-)project scheduling problem with sequence-dependent transfer times. Eur. J.Oper. Res. 197, 492–508.

43. Leon VJ, Ramamoorthy B. (1995), Strength and adaptability of problem-space based neighborhoods for resource constrained scheduling. Oper. Res. Spek. 17, 173–82.

44. Liu, J., Wu, B. (2010). A Multi-agent System for the Flexible Resource Constrained Project Scheduling. Intelligent Information Hiding and Multimedia Signal Processing, Third International Conference on.

45. Liu, Y, Zhao, S.L, Du, X.K, Li, S.Q (2005). Optimization of resource allocation in construction using genetic algorithms. Machine Learning and Cybernetics, Inter. Conf. on.

46. Lova, A., Maroto, C., Tormos, P. (2000). A multicriteria heuristic method to improve resource allocation in multiproject scheduling. Eur. J.Oper. Res. 127, 408-424.

47. Lova, A., Tormos, P., Cervantes, M., Barber, F. (2008). An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes. Inte. J. Pro. Econ. 117, 302–316.

48. Megiddot, N., Ichimor, T. (1985). A Two Resource Allocation Problem Solvable in Linear Time. Math. Oper. Res, 10, 7-16.

49. Mejía, G. and Montoya, C. (2008). Resource Assingment and Scheduling Using Petri Nets and Heuristic Search. 19th Inter. Conf. Prod. Res.

50. Merkle, D, Middendorf, M, Schmeck, H (2002) .Ant Colony Optimization for Resource-Constrained Project Scheduling. IEEE Transactions on EvolutionaryComputation, VOL. 6, NO. 4, August.

51. Ming, Y., Yuan, L., Hai Shang, Y. (2007). Optimizing Resource Allocation in Manufacturing Project Based on Adaptive Ant Colony Algorithm. Wireless Communications, Networking and Mobile Computing, International Conference on.

52. Mingozzi, A., V. Maniezzo, S. Ricciardelli, L. Bianco (1998). An exact algorithm for the multiple resource-constrained projects scheduling problem based on a new mathematical formulation.  Management Sci. 44, 714–729.

53. Mobinia, M., Mobinib, Z., Rabbania, M. (2011). An Artificial Immune Algorithm for the project scheduling problem under resource constraints. Applied Soft Computing. 11, 1975-1982.

54. Montoya, T, Jairo R., Gutierrez, F, Edgar, Pirachica M, Carolina (2009). Project scheduling with limited resources using a genetic algorithm. Inter. J .Project Management. 28, 619–628.

55. Nonobe K. and Ibaraki T. (2002), Formulation and tabu search algorithm for the resource constrained project scheduling problem (RCPSP). In: Ribeiro, C.C., Hansen, P. (Eds.), Essaysand Surveys in Metaheuristics, Kluwer Acad. Pub. 557-588.

56. Peteghem, V.V., Vanhoucke, M. (2009). A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem. Eur. J. Oper. Res. 201, 409–418.

57. Pourkazemi, MH, Fatahi, M., Mazaheri, S and Asadi, B. (2013). Portfolio optimization projects with interaction with the Imperialist competitive algorithm (ICA). Journal of Industrial Management, (5), 1-20 (in persian).  

58. Pritsker A., Watters, L., Wolfe, P. (1969). Multi-project scheduling with limited resources: A zero-one programming approach. Management Science. 16:93–108.

59. Ranjbar, M.R., Kianfar, F. (2007). Solving the discrete time/resource trade-off problem in project scheduling with genetic algorithms. Applied Mathematics and Computation. 191(2), 451–456.

60. Reddy, J. P, Kumanan, S., Chetty, O. V. K (2001). Application of Petri Nets and a Genetic Algorithm to Multi-Mode Multi-Resource Constrained Project Scheduling. The Inte. J. Adva. Manuf. Tech. 17(4), 305-314.

61. Rezaei, Z. (2009). Providing efficient meta-heuristic algorithm for solving multi-level inventory control model. MS Thesis, Tehran, Shahid Beheshti University (in persian).  

62. Roozbeh Niaa, A., Hemmati Farb, M, Akhavan Niakic, S.T (2015).A hybrid genetic and imperialist competitive algorithm for green vendor managed inventory of multi-item multi-constraint EOQ model under shortage. Appl. So.Com. Volume 30, 353–364.

63. Sadeghi, A, Safi, A, Barzin Poor, F. (2010). Solving the project scheduling problem under resource constraints using meta-heuristic algorithm bees. Sixth Inter. Conf. on Proj. Manag. (in persian)  

64. Schirmer A, Riesenberg S. (1998). Case-based reasoning and parameterized random sampling forproject scheduling. Technical Report. Germany, University of Kiel.

65. Shokrane Pour, E (2009). Scheduling two criteria two-stage workflow assembly system by using of meta-heuristic algorithm. MS Thesis, Tehran, Shahid Beheshti University. (in persian)  

66. Talebi, A. (2010). Selection and optimization portfolio using meta-heuristic methods and compare them with portfolio of experts and beginners in Tehran Stock Exchange. MS Thesis, Semnan, Technical University of Shahrod (in persian).  

67. Tormos P., Lova A. (2001). A Competitive Heuristic Solution Technique for Resource-Constrained Project Scheduling. Annals of Operations Research. 102, 65-81.

68. Valls V., Ballestin F., Quintanilla S. (2003). A hybrid genetic algorithm for the RCPSP. Technical Report, Department of Statistics and Operations Research, Spain, University of Valencia.

69. Valls V., Ballestin F., Quintanilla S. (2005). Justification and RCPSP: a technique that pays. Eur. J.Oper. Res. 165, 375–386.

70. Wang, Y, Perkins, J. R., Khurana, A (2002). Optimal resource allocation in new product development projects: a control-theoretic approach. Automatic Control. IEEE Transactions on. 47(8), 1267-1276.

71. Whitehouse, G. E., DePuy, G.W., Moraga Reinaldo, J. (2009). Meta-Raps approach for solving the resource allocation problem. Automation Congress, Proceedings of the 5th Biannual World.

72. Yousefli, A, Ghazanfari, M, Shahanaghi, K, Heydari, M (2008). A New Heuristic Model for Fully Fuzzy Project Scheduling. Journal of Uncertain Systems. 2(1), 75-80.

73. Zaniar, A, Karimi, S, Poursabzi, O, Naderi, B. (2015). A novel imperialist competitive algorithm for generalized traveling salesman problems. Applied Soft Computing. Volume 26, 546–555.

فایل ها

هم رسانی

ارجاع به این مقاله

آمار