Алгоритм локального поиска для задачи календарного планирования с ограниченными ресурсами

Алгоритм локального поиска для задачи календарного планирования с ограниченными ресурсами

Гончаров Е. Н.
Дискретный анализ и исследование операций, 29, 4, 15-37 (2022)
Скачать статью

УДК 519.8+518.25 
DOI: 10.33048/daio.2022.29.734

Аннотация:

Рассматривается задача календарного планирования с ограниченными ресурсами по критерию минимизации длины расписания. Все ресурсы возобновимы, прерывания работ запрещены. Предложен алгоритм локального поиска, использующий список запретов и два типа окрестностей. Численный эксперимент на примерах из библиотеки PCPLIB показал конкурентоспособность предложенного алгоритма. Были получены одни из лучших средних отклонений найденных решений от величины критического пути, для нескольких примеров из серии тестовых примеров j120 найдены лучшие (ранее неизвестные) решения.
Табл. 4, библиогр. 47.

Литература:
  1. Brucker P., Drexl A., Möhring R., Neumann K., Pesch E. Resource-constrained project scheduling: Notation, classification, models, and methods // Eur. J. Oper. Res. 1999. V. 112, No. 1. P. 3–41.
     
  2. Blazewicz J., Lenstra J. K., Rinnoy Kan A. H. G. Scheduling subject to resource constraints: Classification and complexity // Discrete Appl. Math. 1983. V. 5, No. 1. P. 11–24.
     
  3. Гимади Э. Х. О некоторых математических моделях и методах планирования крупномасштабных проектов // Модели и методы оптимизации. Тр. Ин-та математики. Т. 10. Новосибирск: Наука, 1988. С. 89–115.
     
  4. Гимади Э. Х., Залюбовский В. В., Севастьянов С. В. Полиномиальная разрешимость задач календарного планирования со складируемыми ресурсами и директивными сроками // Дискрет. анализ и исслед. операций. Сер. 2. 2000. Т. 7, № 1. С. 9–34.
     
  5. Pellerin R., Perrier N., Berthaut F. LSSPER: A survey of hybrid metaheuristics for the resource-constrained project scheduling problem // Eur. J. Oper. Res. 2020. V. 280, No. 2. P. 395–416.
     
  6. Abdolshah M. A review of resource-constrained project scheduling problems (RCPSP) approaches and solutions // Int. Trans. J. Eng. Manage. Appl. Sci. Technol. 2014. V. 5, No. 4. P. 253–286.
     
  7. Vanhoucke M. Resource-constrained project scheduling // Project Management with Dynamic Scheduling. Heidelberg: Springer, 2012. P. 107–137.
     
  8. Hartmann S., Briskorn D. A survey of variants and extensions of the resource-constrained project scheduling problem // Eur. J. Oper. Res. 2010. V. 207, No. 1. P. 1–14.
     
  9. Kolisch R., Hartmann S. Experimental investigation of heuristics for resource-constrained project scheduling: An update // Eur. J. Oper. Res. 2006. V. 174, No. 1. P. 23–37.
     
  10. Palpant M., Artigues C., Michelon P. Solving the resource-constrained project scheduling problem with large neighborhood search // Ann. Oper. Res. 2004. V. 131. P. 237–257.
     
  11. Kochetov Yu. A., Stolyar A. A. Evolutionary local search with variable neighborhood for the resource constrained project scheduling problem // Proc. 5th Int. Workshop Comput. Sci. Inf. Technol. (Ufa, Russia, Sept. 16–18). Ufa: USATU, 2003. P. 96–99.
     
  12. Goncharov E. N. Variable neighborhood search for the resource constrained project scheduling problem // Mathematical Optimization Theory and Operations Research. Rev. Sel. Pap. 18th Int. Conf. (Yekaterinburg, Russia, July 8–12, 2019). Cham: Springer, 2021. P. 39–50. (Commun. Comput. Inf. Sci.; V. 1090).
     
  13. Kolisch R., Hartmann S. Heuristic algorithms for solving the resource-constrained project scheduling problem: Classification and computational analysis // Project Scheduling: Recent Models, Algorithms and Applications. Boston: Kluwer Acad. Publ., 1999. P. 147–178.
     
  14. Gimadi E. Kh., Goncharov E. N., Mishin D. V. On some implementations of solving the resource-constrained project scheduling problem // Yugoslav. J. Oper. Res. 2019. V. 29, No. 1. P. 31–42.
     
  15. Gagnon M., Boctor F. F., d’Avignon G. A tabu search algorithm for the resource-constrained project scheduling problem // Proc. 2004 Conf. Adm. Sci. Assoc. Canada. (Quebec, Canada, June 5–8, 2004). Waterloo, ON: ASAC, 2004.
     
  16. Proon S., Jin M. A genetic algorithm with neighborhood search for the resource-constrained project scheduling problem // Naval Res. Logist. 2011. V. 58. P. 73–82.
     
  17. Valls V., Ballestin F., Quintanilla S. A population-based approach to the resource-constrained project scheduling problem // Ann. Oper. Res. 2004. V. 131. P. 305–324.
     
  18. Kolisch R., Sprecher A. PSPLIB — a Project Scheduling Problem Library // Eur. J. Oper. Res. 1996. V. 96, No. 1. P. 205–216.
     
  19. Project scheduling: Recent models, algorithms and applications. Boston: Kluwer Acad. Publ., 1999.
     
  20. Kolisch R., Sprecher A., Drexl A. Characterization and generation of a general class of resource-constrained project scheduling problems // Manage. Sci. 1995. V. 41, No. 10. P. 1693–1703.
     
  21. Гончаров Е. Н., Леонов В. В. Генетический алгоритм для задачи календарного планирования с ограниченными ресурсами // Автоматика и телемеханика. 2017. № 6. С. 173–189.
     
  22. Berthaut F., Pellerin R., Hajji A., Perrier N. A path relinking-based scatter search for the resource-constrained project scheduling problem // Int. J. Proj. Organ. Manage. 2018. V. 10, No. 1. P. 1–36.
     
  23. Paraskevopoulos D. C., Tarantilis C. D., Ioannou G. Solving project scheduling problems with resource constraints via an event list-based evolutionary algorithm // Expert Syst. Appl. 2012. V. 39, No. 4. P. 3983–3994. 
     
  24. Mobini M., Mobini Z., Rabbani M. An artificial immune algorithm for the project scheduling problem under resource constraints // Appl. Soft Comput. 2011. V. 11, No. 2. P. 1975–1982.
     
  25. Mahdi Mobini M. D., Rabbani M., Amalnik M. S., Razmi J., Rahimi-Vahed A. R. Using an enhanced scatter search algorithm for a resource-constrained project scheduling problem // Soft Comput. 2009. V. 13. P. 597–610.
     
  26. Wang H., Li T., Lin T. Efficient genetic algorithm for resource-constrained project scheduling problem // Trans. Tianjin Univ. 2010. V. 16, No. 5. P. 376–382.
     
  27. Goncalves J., Resende M. G. C, Mendes J. A biased random key genetic algorithm with forward-backward improvement for resource-constrained project scheduling problem // J. Heuristics. 2011. V. 17. P. 467–486.
     
  28. Elsayed S., Sarker R., Ray T., Coello C. C. Consolidated optimization algorithm for resource-constrained project scheduling problems // Inf. Sci. 2017. V. 418–419. P. 346–362.
     
  29. Czogalla J., Fink A. Particle swarm topologies for resource constrained project scheduling // Nature Inspired Cooperative Strategies for Optimization (NICSO 2008). Heidelberg: Springer, 2009. P. 61–73.
     
  30. Lim A., Ma H., Rodrigues B., Tan S. T., Xiao F. New meta-heuristics for the resource-constrained project scheduling problem // Flex. Services Manuf. J. 2013. V. 25, No. 1–2. P. 48–73.
     
  31. Chen D., Liu S., Qin S. Memetic algorithm for the resource-constrained project scheduling problem // Proc. 11th World Congr. Intell. Control Autom. (WCICA 2014) (Shenyang, China, June 27–30, 2014). Piscataway: IEEE, 2014. P. 4991–4996.
     
  32. Zheng X., Wang L. A multi-agent optimization algorithm for resource constrained project scheduling problem // Expert Syst. Appl. 2015. V. 42, No. 15–16. P. 6039–6049.
     
  33. Zamani R. A competitive magnet-based genetic algorithm for solving the resource-constrained project scheduling problem // Eur. J. Oper. Res. 2013. V. 229, No. 2. P. 552–559.
     
  34. Zheng X., Wang L. An effective shuffled frog-leaping algorithm for resourceconstrained project scheduling problem // Comput. Oper. Res. 2012. V. 39, No. 5. P. 890–901.
     
  35. Ismail I. Y., Barghash M. A. Diversity guided genetic algorithm to solve the resource constrained project scheduling problem // Int. J. Plan. Sched. 2012. V. 1, No. 3. P. 147–170.
     
  36. Chen W., Shi Y., Teng H., Lan X., Hu L. An efficient hybrid algorithm for resource-constrained project scheduling // Inf. Sci. 2010. V. 180, No. 6. P. 1031–1039.
     
  37. Mendes J. J. M., Goncalves J. F., Resende M. G. C. A random key based genetic algorithm for the resource-constrained project scheduling problem // Comput. Oper. Res. 2009. V. 36. P. 92–109.
     
  38. Debels D., Vanhoucke M. Decomposition-based genetic algorithm for the resource-constrained project scheduling problem // Oper. Res. 2007. V. 55. P. 457–469.
     
  39. Koulinas G., Kotsikas L., Anagnostopoulos K. A particle swarm optimization based hyper-heuristic algorithm for the classic resource constrained project scheduling problem // Inf. Sci. 2014. V. 277. P. 680–693.
     
  40. Valls V., Ballestin F., Quintanilla S. A hybrid genetic algorithm for the resource-constrained project scheduling problem // Eur. J. Oper. Res. 2008. V. 185, No. 2. P. 495–508.
     
  41. Carlier J., Moukrim A., Xu H. A memetic algorithm for the resource constrained project scheduling problem // Proc. 2009 Int. Conf. Ind. Eng. Syst. Manage. (Montreal, Canada, May 13–15, 2009). Piscataway: IEEE, 2009.
     
  42. Debels D., De Reyck Leus B. R., Vanhoucke M. A hybrid scatter search electromagnetism meta-heuristic for project scheduling // Eur. J. Oper. Res. 2006. V. 169, No. 2. P. 638–653.
     
  43. Ranjbar M., Kianfar F. A hybrid scatter search for the RCPSP // Sci. Iran. 2009. V. 16, No. 1. P. 11–18.
     
  44. Jedrzejowicz P., Ratajczak E. Population learning algorithm for the resource-constrained project scheduling // Perspectives in Modern Project Scheduling. New York: Springer, 2006. P. 275–296.
     
  45. Ying K. C., Lin S. W., Lee Z. J. Hybrid-directional planning: Improving improvement heuristics for scheduling resource-constrained projects // Int. J. Adv. Manuf. Technol. 2009. V. 41, No. 3–4. P. 358–366.
     
  46. Alcaraz J., Maroto C. A hybrid genetic algorithm based on intelligent encoding for project scheduling // Perspectives in Modern Project Scheduling. New York: Springer, 2006. P. 249–274.
     
  47. Valls V., Ballestin F., Quintanilla M. S. Justification and RCPSP: A technique that pays // Eur. J. Oper. Res. 2005. V. 165, No. 2. P. 375–386.

Исследование выполнено в рамках государственного задания ИМ СО РАН (проект № FWNF–2022–0019).

Гончаров Евгений Николаевич
  1. Институт математики им. С. Л. Соболева,
    пр. Коптюга, 4, 630090 Новосибирск, Россия
  2. Новосибирский гос. университет,
    ул. Пирогова, 2, 630090 Новосибирск, Россия

E-mail: gon@math.nsc.ru

Статья поступила 21 апреля 2022 г. 
После доработки — 25 мая 2022 г. 
Принята к публикации 26 мая 2022 г.

Abstract:

We consider the resource-constrained project scheduling problem (RCPSP). The problem accounts for technological constraints of activities precedence together with resource constraints. All resources are renewable. Activities preemptions are not allowed. This problem is NP-hard in the strong sense. We present a new local search algorithm that uses a Tabu-list and two type of neighborhoods. The algorithm is evaluated using three data bases of instances of the problem: 480 instances of 60 activities, 480 of 90, and 600 of 120 activities respectively, taken from the PSPLIB library available online. Numerical experiments demonstrate that the proposed algorithm produces better results than existing algorithms in the literature for large-sized instances. For some instances from the dataset j120, the best known heuristic solutions were improved. 
Tab. 4, bibliogr. 47.

References:
  1. P. Brucker, A. Drexl, R. Möhring, K. Neumann, and E. Pesch, Resource-constrained project scheduling: Notation, classification, models, and methods, Eur. J. Oper. Res. 112 (1), 3–41 (1999).
     
  2. J. Blazewicz, J. K. Lenstra, and A. H. G. Rinnoy Kan, Scheduling subject to resource constraints: Classification and complexity, Discrete Appl. Math. 5 (1), 11–24 (1983).
     
  3. É. Kh. Gimadi, On some mathematical models and methods for planning large-scale projects, in Models and Optimization Methods (Tr. Inst. Mat., Vol. 10) (Nauka, Novosibirsk, 1988), pp. 89–115.
     
  4. É. Kh. Gimadi, V. V. Zalyubovskii, and S. V. Sevastyanov, Polynomial solvability of scheduling problems with storable resources and deadlines, Diskretn. Anal. Issled. Oper., Ser. 2, 7 (1), 9–34 (2000).
     
  5. R. Pellerin, N. Perrier, and F. Berthaut, LSSPER: A survey of hybrid metaheuristics for the resource-constrained project scheduling problem, Eur. J. Oper. Res. 280 (2), 395–416 (2020).
     
  6. M. Abdolshah, A review of resource-constrained project scheduling problems (RCPSP) approaches and solutions, Int. Trans. J. Eng. Manage. Appl. Sci. Technol. 5 (4), 253–286 (2014).
     
  7. M. Vanhoucke, Resource-constrained project scheduling, in Project Management with Dynamic Scheduling (Springer, Heidelberg, 2012), pp. 107–137.
     
  8. S. Hartmann and D. Briskorn, A survey of variants and extensions of the resource-constrained project scheduling problem, Eur. J. Oper. Res. 207 (1), 1–14 (2010).
     
  9. R. Kolisch and S. Hartmann, Experimental investigation of heuristics for resource-constrained project scheduling: An update, Eur. J. Oper. Res. 174 (1), 23–37 (2006).
     
  10. M. Palpant, C. Artigues, and P. Michelon, Solving the resource-constrained project scheduling problem with large neighborhood search, Ann. Oper. Res. 131, 237–257 (2004).
     
  11. Yu. A. Kochetov and A. A. Stolyar, Evolutionary local search with variable neighborhood for the resource constrained project scheduling problem, in Proc. 5th Int. Workshop Comput. Sci. Inf. Technol., Ufa, Russia, Sept. 16–18 (USATU, Ufa, 2003), pp. 96–99.
     
  12. E. N. Goncharov, Variable neighborhood search for the resource constrained project scheduling problem, in Mathematical Optimization Theory and Operations Research (Rev. Sel. Pap. 18th Int. Conf., Yekaterinburg, Russia, July 8–12, 2019) (Springer, Cham, 2021), pp. 39–50 (Commun. Comput. Inf. Sci., Vol. 1090).
     
  13. R. Kolisch and S. Hartmann, Heuristic algorithms for solving the resourceconstrained project scheduling problem: Classification and computational analysis, in Project Scheduling: Recent Models, Algorithms and Applications (Kluwer Acad. Publ., Boston, 1999), pp. 147–178.
     
  14. E. Kh. Gimadi, E. N. Goncharov, and D. V. Mishin, On some implementations of solving the resource-constrained project scheduling problem, Yugoslav. J. Oper. Res. 29 (1), 31–42 (2019).
     
  15. M. Gagnon, F. F. Boctor, and G. d’Avignon, A tabu search algorithm for the resource-constrained project scheduling problem, in Proc. 2004 Conf. Adm. Sci. Assoc. Canada, Quebec, Canada, June 5–8, 2004 (ASAC, Waterloo, 2004).
     
  16. S. Proon and M. Jin, A genetic algorithm with neighborhood search for the resource-constrained project scheduling problem, Naval Res. Logist. 58, 73–82 (2011).
     
  17. V. Valls, F. Ballestin, and S. Quintanilla, A population-based approach to the resource-constrained project scheduling problem, Ann. Oper. Res. 131, 305–324 (2004).
     
  18. R. Kolisch and A. Sprecher, PSPLIB — a Project Scheduling Problem Library, Eur. J. Oper. Res. 96 (1), 205–216 (1996).
     
  19. Project Scheduling: Recent Models, Algorithms and Applications (Kluwer Acad. Publ., Boston, 1999).
     
  20. R. Kolisch, A. Sprecher, and A. Drexl, Characterization and generation of a general class of resource-constrained project scheduling problems, Manage. Sci. 41 (10), 1693–1703 (1995).
     
  21. E. N. Goncharov and V. V. Leonov, Genetic algorithm for the resourceconstrained project scheduling problem Avtom. Telemekh., No. 6, 173–189 (2017) [Russian] [Autom. Remote Control. 78 (6), 1101–1114 (2017)].
     
  22. F. Berthaut, R. Pellerin, A. Hajji, and N. Perrier, A path relinkingbased scatter search for the resource-constrained project scheduling problem, Int. J. Proj. Organ. Manage. 10 (1), 1–36 (2018).
     
  23. D. C. Paraskevopoulos, C. D. Tarantilis, and G. Ioannou, Solving project scheduling problems with resource constraints via an event list-based evolutionary algorithm, Expert Syst. Appl. 39 (4), 3983–3994 (2012).
     
  24. M. Mobini, Z. Mobini, and M. Rabbani, An artificial immune algorithm for the project scheduling problem under resource constraints, Appl. Soft Comput. 11 (2), 1975–1982 (2011).
     
  25. M. D. Mahdi Mobini, M. Rabbani, M. S. Amalnik, J. Razmi, and A. R. Rahimi-Vahed, Using an enhanced scatter search algorithm for a resource-constrained project scheduling problem, Soft Comput. 13, 597–610 (2009).
     
  26. H. Wang, T. Li, and T. Lin, Efficient genetic algorithm for resource-constrained project scheduling problem, Trans. Tianjin Univ. 16 (5), 376–382 (2010).
     
  27. J. Goncalves, M. G. Resende, C, and J. Mendes, A biased random key genetic algorithm with forward-backward improvement for resource-constrained project scheduling problem, J. Heuristics 17, 467–486 (2011).
     
  28. S. Elsayed, R. Sarker, T. Ray, and C. C. Coello, Consolidated optimization algorithm for resource-constrained project scheduling problems, Inf. Sci. 418–419, 346–362 (2017).
     
  29. J. Czogalla and A. Fink, Particle swarm topologies for resource constrained project scheduling, in Nature Inspired Cooperative Strategies for Optimization (NICSO 2008) (Springer, Heidelberg, 2009), pp. 61–73.
     
  30. A. Lim, H. Ma, B. Rodrigues, S. T. Tan, and F. Xiao, New metaheuristics for the resource-constrained project scheduling problem, Flex. Services Manuf. J. 25 (1–2), 48–73 (2013).
     
  31. D. Chen, S. Liu, and S. Qin, Memetic algorithm for the resource-constrained project scheduling problem, in Proc. 11th World Congr. Intell. Control Autom. (WCICA 2014), Shenyang, China, June 27–30, 2014 (IEEE, Piscataway, 2014), pp. 4991–4996.
     
  32. X. Zheng and L. Wang, A multi-agent optimization algorithm for resource constrained project scheduling problem, Expert Syst. Appl. 42 (15–16), 6039–6049 (2015).
     
  33. R. Zamani, A competitive magnet-based genetic algorithm for solving the resource-constrained project scheduling problem, Eur. J. Oper. Res. 229 (2), 552–559 (2013).
     
  34. X. Zheng and L. Wang, An effective shuffled frog-leaping algorithm for resource-constrained project scheduling problem, Comput. Oper. Res. 39 (5), 890–901 (2012).
     
  35. I. Y. Ismail and M. A. Barghash, Diversity guided genetic algorithm to solve the resource constrained project scheduling problem, Int. J. Plan. Sched. 1 (3), 147–170 (2012).
     
  36. W. Chen, Y. Shi, H. Teng, X. Lan, and L. Hu, An efficient hybrid algorithm for resource-constrained project scheduling, Inf. Sci. 180 (6), 1031–1039 (2010).
     
  37. J. J. M. Mendes, J. F. Goncalves, and M. G. C. Resende, A random key based genetic algorithm for the resource-constrained project scheduling problem, Comput. Oper. Res. 36, 92–109 (2009).
     
  38. D. Debels and M. Vanhoucke, Decomposition-based genetic algorithm for the resource-constrained project scheduling problem, Oper. Res. 55, 457–469 (2007).
     
  39. G. Koulinas, L. Kotsikas, and K. Anagnostopoulos, A particle swarm optimization based hyper-heuristic algorithm for the classic resource constrained project scheduling problem, Inf. Sci. 277, 680–693 (2014).
     
  40. V. Valls, F. Ballestin, and S. Quintanilla, A hybrid genetic algorithm for the resource-constrained project scheduling problem, Eur. J. Oper. Res. 185 (2), 495–508 (2008).
     
  41. J. Carlier, A. Moukrim, and H. Xu, A memetic algorithm for the resource constrained project scheduling problem, in Proc. 2009 Int. Conf. Ind. Eng. Syst. Manage., Montreal, Canada, May 13–15, 2009 (IEEE, Piscataway, 2009).
     
  42. D. Debels, B. R. De Reyck Leus, and M. Vanhoucke, A hybrid scatter search electromagnetism meta-heuristic for project scheduling, Eur. J. Oper. Res. 169 (2), 638–653 (2006).
     
  43. M. Ranjbar and F. Kianfar, A hybrid scatter search for the RCPSP, Sci. Iran. 16 (1), 11–18 (2009).
     
  44. P. Jedrzejowicz and E. Ratajczak, Population learning algorithm for the resource-constrained project scheduling, in Perspectives in Modern Project Scheduling (Springer, New York, 2006), pp. 275–296.
     
  45. K. C. Ying, S. W. Lin, and Z. J. Lee, Hybrid-directional planning: Improving improvement heuristics for scheduling resource-constrained projects, Int. J. Adv. Manuf. Technol. 41 (3–4), 358–366 (2009).
     
  46. J. Alcaraz and C. Maroto, A hybrid genetic algorithm based on intelligent encoding for project scheduling, in Perspectives in Modern Project Scheduling (Springer, New York, 2006), pp. 249–274.
     
  47. V. Valls, F. Ballestin, and M. S. Quintanilla, Justification and RCPSP: A technique that pays, Eur. J. Oper. Res. 165 (2), 375–386 (2005).