ЗАДАЧА СКЛАДАННЯ ПЛАНУ РЕМОНТУ ОБ’ЄКТІВ ЕЛЕКТРИЧНОЇ МЕРЕЖІ
DOI:
https://doi.org/10.31649/1997-9266-2025-179-2-104-110Ключові слова:
багатокритеріальна оптимізація, теорія розкладів, паралельні машини, множини, евристичний алгоритм, локальний пошук, компромісний розв’язокАнотація
Розглянуто задачу двокритеріального планування робіт з відновлення електропостачання після аварійного відключення в умовах обмежених ресурсів — ремонтних бригад, які працюють паралельно. Така ситуація є типовою для міських інфраструктурних систем у критичних умовах, коли необхідно швидко ухвалювати рішення з урахуванням кількох суперечливих цілей. Математична постановка задачі враховує два критерії: мінімізацію середнього зваженого часу перебування громадян без електропостачання та мінімізацію загального часу роботи ремонтних бригад (makespan). Запропонована модель належить до класу задач складання розкладу на паралельних машинах з роботами, що мають ваги, які відображають соціальну значущість кожної роботи. Для розв’язання цієї задачі розроблено три алгоритми: евристичний, алгоритм локального пошуку з переміщенням робіт (АЛП1) та алгоритм локального пошуку з обміном робіт (АЛП2). Евристичний алгоритм поєднує підходи до оптимального складання розкладу на одній машині (за критерієм середнього зваженого часу) та ідеї балансування навантаження на кількох машинах (LPT-алгоритм). АЛП1 базується на поступовому поліпшенні початкового розкладу шляхом переміщення робіт між бригадами з оцінкою компромісу між двома критеріями. АЛП2 реалізує випадкові обміни парами робіт між машинами з відбором поліпшень за принципом справедливого компромісу, що забезпечує нижчу обчислювальну складність зі збереженням високої якості розв’язків. Проведено обчислювальні експерименти, які підтвердили ефективність розроблених алгоритмів. Встановлено, що АЛП1 та АЛП2 забезпечують поліпшення результатів, отриманих евристичним алгоритмом, у середньому на 3,5…5 %. Експерименти з різними параметрами задачі продемонстрували закономірне зростання часу роботи алгоритмів з розмірністю задачі, а також перевагу АЛП2 у швидкодії порівняно з АЛП1 завдяки обмеженню кількості локальних змін. Запропонований підхід дозволяє ефективно розв’язувати задачі планування відновлення електропостачання, поєднуючи класичні методи теорії розкладів з урахуванням соціально важливих аспектів.
Посилання
Y. K. Lin, and T. Y. Yin, “Generating bicriteria schedules for correlated parallel machines involving tardy jobs and weighted completion time, ” Annals of Operations Research, vol. 319, pp. 1655-1688, 2022, https://doi.org/10.1007/s10479-021-04043-x.
X. Liu, Y. Feng, N. Ding, R. Li, and X. Chen, "Multi-criteria scheduling in parallel environment with learning effect," Foundations of Computing and Decision Sciences, vol. 49, no. 1, pp. 3-20, 2024, https://doi.org/10.2478/fcds-2024-0001 .
C. H. Liu, and W. N. Tsai, “Multi-objective parallel machine scheduling problems by considering controllable processing times,” Journal of the Operational Research Society, vol. 67, no. 4, pp. 654-663, 2016, https://doi.org/10.1057/jors.2015.82 .
J. Mar-Ortiz, A. J. Ruiz Torres, and B. Adenso-Díaz, “Scheduling in parallel machines with two objectives: Analysis of factors that influence the Pareto frontier,” Operational Research, vol. 22, pp. 4585-4605, 2022, https://doi.org/10.1007/s12351-021-00684-9 .
M. L. Pinedo, Scheduling: Theory, Algorithms, and Systems, 5th ed. New York, NY, USA: Springer, 2016, https://doi.org/10.1007/978-3-319-26580-3 .
J. Xu, and R. Nagi, “Identical parallel machine scheduling to minimise makespan and total weighted completion time: A column generation approach,” International Journal of Production Research, vol. 51, no. 23-24, pp. 7091-7104, 2013, https://doi.org/10.1080/00207543.2013.825379 .
P.-F. Dutot, L. Eyraud, G. Mounié, and D. Trystram, “Bi-criteria algorithm for scheduling jobs on cluster platforms,” arXiv:cs/0405006, 2004, https://doi.org/10.48550/arXiv.cs/0405006 .
X. Zhu, J. Xu, J. Ge, Y. Wang, and Z. Xie, “Multi-objective parallel machine scheduling with eligibility constraints for the kitting of metal structural parts,” Machines, vol. 10, no. 10, p. 836, 2022, https://doi.org/10.3390/machines10100836 .
W. Li, W. Zhai, and X. Chai, “Online bi-criteria scheduling on batch machines with machine costs,” Mathematics, vol. 7, no. 10, p. 960, 2019, https://doi.org/10.3390/math7100960 .
J. Rocholl, L. Mönch, and J. Fowler, “Bi-criteria parallel batch machine scheduling to minimize total weighted tardiness and electricity cost,” Journal of Business Economics, vol. 90, pp. 1345-1381, 2020, https://doi.org/10.1007/s11573-020-00970-6 .
A. Aalaei, V. Kayvanfar, and H. Davoudpour, “A multi-objective optimization for preemptive identical parallel machines scheduling problem,” Comput. and Applied Mathematics, vol. 36, pp. 1367-1387, 2017, https://doi.org/10.1007/s40314-015-0298-0 .
E.-G. Talbi, Metaheuristics: From Design to Implementation. Hoboken, NJ, USA: Wiley, 2009. https://doi.org/10.1002/9780470496916 .
##submission.downloads##
-
pdf
Завантажень: 16
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Автори, які публікуються у цьому журналі, згодні з такими умовами:
- Автори зберігають авторське право і надають журналу право першої публікації.
- Автори можуть укладати окремі, додаткові договірні угоди з неексклюзивного поширення опублікованої журналом версії статті (наприклад, розмістити її в інститутському репозиторії або опублікувати її в книзі), з визнанням її первісної публікації в цьому журналі.
- Авторам дозволяється і рекомендується розміщувати їхню роботу в Інтернеті (наприклад, в інституційних сховищах або на їхньому сайті) до і під час процесу подачі, оскільки це сприяє продуктивним обмінам, а також швидшому і ширшому цитуванню опублікованих робіт (див. вплив відкритого доступу).