Метод ветвей и границ для решения задачи минимизации платы за внешние ресурсы
- Авторы: Мусатова Е.Г.1, Лазарев А.А.1
-
Учреждения:
- ФГБУН Институт проблем управления им. В.А. Трапезникова РАН
- Выпуск: № 117 (2025)
- Страницы: 119-140
- Раздел: Математическая теория управления
- URL: https://journals.rcsi.science/1819-2440/article/view/360560
- DOI: https://doi.org/10.25728/ubs.2025.117.6
- ID: 360560
Цитировать
Полный текст
Аннотация
Рассматривается задача построения расписания работ, выполняемых на одном приборе. Заданы отношения предшествования между работами, а также подмножества работ, требующих дополнительные внешние ресурсы, за аренду которых взимается плата. Для каждого внешнего ресурса однозначно определены крайние (первая и последняя) работы, выполняемые с использованием этого ресурса. Необходимо упорядочить работы, не нарушив отношения предшествования и минимизируя суммарные арендные выплаты. Доказана теорема об NP-трудности данной задачи в сильном смысле даже при условии одинаковой продолжительности всех работ и одинаковых цен на все внешние ресурсы. На основе свойств целевой функции для решения поставленной задачи предлагаются нижние оценки и метод ветвей и границ, в котором перебор ведется по допустимым перестановкам крайних работ, использующих внешние ресурсы. Проведенный вычислительный эксперимент показал эффективность предлагаемых нижних оценок целевой функции, позволяющих отсекать бесперспективные ветви в дереве поиска. Определен тип входных данных задачи, для которого разработанный метод работает лучше других известных вариантов точных методов, в которых перебор происходит на множестве всех работ. В частности, на задачах большой размерности при количестве внешних ресурсов меньше 20 данный метод оказывается эффективнее решателя CP Optimizer на базе программирования в ограничениях.
Об авторах
Елена Геннадьевна Мусатова
ФГБУН Институт проблем управления им. В.А. Трапезникова РАН
Email: nekolyap@mail.ru
Moscow
Александр Алексеевич Лазарев
ФГБУН Институт проблем управления им. В.А. Трапезникова РАН
Email: jobmath@mail.com
Moscow
Список литературы
1. КИБЗУН А.И., РАССКАЗОВА В.А. Модель целочисленно-го линейного программирования как математическое обес-печение системы оптимального планирования потоковогопроизводства на этапе оперативного графикования // Ав-томатика и телемеханика. – 2023. – №5. – С. 113—132. 2. МУСАТОВА Е.Г., ЛАЗАРЕВ А.А. Задача минимизации сум-марной взвешенной длительности курсов для одного прибо-ра с ограничениями предшествования // Автоматика и теле-механика. – 2023. – №9. – С. 153–168. 3. BRISKORN D., DAVARI M., MATUSCHKE J. Single-machinescheduling with an external resource // European Journal ofOperational Research. – 2021. – Vol. 293, No. 2. – P. 457–468. 4. BRUCKER P. Scheduling algorithms. – Springer: Heidelberg,2007. – 371 p.. 5. CHEN B., POTTS C.N., WOEGINGER G.J. A reviewof machine scheduling: complexity, algorithms andapproximability // Handbook of Combinatorial Optimization. –Boston, MA: Springer US, 1998. – P. 1493–1641. 6. CSEBFALVI A.B., CSEBFALVI G. Hammock activities inproject scheduling // Proc. of the Sixteenth Annual Conf. ofPOMS. – Chicago, IL, 2005. 7. ELIEZER O. A new bi–objective hybrid metaheuristicalgorithm for the resource-constrained hammock cost problem(RCHCP). – Doctoral Dissertation. – Pecs, 2011. – 111 p. 8. GRAHAM R.L., LAWLER E.L., LENSTRA J.K., KAN A.R.Optimization and approximation in deterministic sequencingand scheduling: a survey // Annals of discrete mathematics. –1998. –Vol. 5 –P. 287–326. 9. HARHALAKIS G. Special features of precedence networkcharts // European Journal of Operational Research. – 1990. –Vol. 49, No. 1. – P. 50–59. 10. LAWLER E.L. Optimal sequencing of a single machine subjectto precedence constraints // Management Science. – 1973. –Vol. 19, No. 5. – P. 544–546. 11. LAWLER E.L. Sequencing jobs to minimize total weightedcompletion time subject to precedence constraints // Annals ofDiscrete Mathematics. – 1978. – Vol. 2 – P. 75-–90. 12. LAZAREV A., KHUSNULLIN N., MUSATOVA E. et al.Minimization of the weighted total sparsity of cosmonauttraining courses // Communications in Computer andInformation Science. – 2019. – Vol. 974. – P. 202–215. 13. LENSTRA J.K., RINNOOY KAN A.H.G. Complexityof scheduling under precedence constraints // OperationsResearch. – 1978. – Vol. 26, No. 1. – P. 22–35. 14. MOHRING R.H. Minimizing costs of resource requirements inproject networks subject to a fixed completion time // OperationsResearch. – 1984. – Vol. 32, No. 1. – P. 89—120. 15. NADERI B., RUIZ R., ROSHANAEI V. Mixed-integerprogramming vs. constraint programming for shop schedulingproblems: New results and outlook // INFORMS Journal onComputing. – 2023. – Vol. 35, No. 4. – P. 817–843. 16. RASSKAZOVA V.A. LIP model in solving RCPSP at theflow type production // Communications in Computer andInformation Science. – 2024. – Vol. 1913. – P. 75–88. 17. RODRIGUES S.B., YAMASHITA D.S. An exact algorithm forminimizing resource availability costs in project scheduling //European Journal of Operational Research. – 2010. – Vol. 206,No. 3. – P. 562–568. 18. TOMCZAK M., JASKOWSKI P. Scheduling repetitiveconstruction projects: Structured literature review // Journal ofCivil Engineering and Management. – 2022. – Vol. 28, No. 6. –P. 422–442. 19. VANHOUCKE M. Work continuity constraints in projectscheduling // Journal of Construction Engineering andManagement. – 2006. – Vol. 132, No. 1. – P. 14–25. 20. VANHOUCKE M. Work continuity optimization for theWesterscheldetunnel Project in the Netherlands // Tijdschriftvoor economie en management. – 2007. – Vol. 52, No. 3. –P. 435–449. 21. ZHANG A., ZHEN T., CHEN Y., CHEN G. An improvedalgorithm for parallel machine scheduling under additionalresource constraints // Optimization Letters. – 2023. – Vol. 17,No. 3. – P. 753–769. 22. ZOU X., WU G., ZHANG Q. Work continuity constraintsin repetitive project scheduling considering soft logic //Engineering, Construction and Architectural Management. –2021. – Vol. 28, No. 6. – P. 1713–1738. 23. https://www.ibm.com/docs/es/icos/22.1.0 (дата обращения:15.04.2025).
Дополнительные файлы
