Метод ветвей и границ для решения задачи минимизации платы за внешние ресурсы

Обложка

Цитировать

Полный текст

Аннотация

Рассматривается задача построения расписания работ, выполняемых на одном приборе. Заданы отношения предшествования между работами, а также подмножества работ, требующих дополнительные внешние ресурсы, за аренду которых взимается плата. Для каждого внешнего ресурса однозначно определены крайние (первая и последняя) работы, выполняемые с использованием этого ресурса. Необходимо упорядочить работы, не нарушив отношения предшествования и минимизируя суммарные арендные выплаты. Доказана теорема об NP-трудности данной задачи в сильном смысле даже при условии одинаковой продолжительности всех работ и одинаковых цен на все внешние ресурсы. На основе свойств целевой функции для решения поставленной задачи предлагаются нижние оценки и метод ветвей и границ, в котором перебор ведется по допустимым перестановкам крайних работ, использующих внешние ресурсы. Проведенный вычислительный эксперимент показал эффективность предлагаемых нижних оценок целевой функции, позволяющих отсекать бесперспективные ветви в дереве поиска. Определен тип входных данных задачи, для которого разработанный метод работает лучше других известных вариантов точных методов, в которых перебор происходит на множестве всех работ. В частности, на задачах большой размерности при количестве внешних ресурсов меньше 20 данный метод оказывается эффективнее решателя CP Optimizer на базе программирования в ограничениях.

Об авторах

Елена Геннадьевна Мусатова

ФГБУН Институт проблем управления им. В.А. Трапезникова РАН

Email: nekolyap@mail.ru
Moscow

Александр Алексеевич Лазарев

ФГБУН Институт проблем управления им. В.А. Трапезникова РАН

Email: jobmath@mail.com
Moscow

Список литературы

  1. 1. КИБЗУН А.И., РАССКАЗОВА В.А. Модель целочисленно-го линейного программирования как математическое обес-печение системы оптимального планирования потоковогопроизводства на этапе оперативного графикования // Ав-томатика и телемеханика. – 2023. – №5. – С. 113—132.
  2. 2. МУСАТОВА Е.Г., ЛАЗАРЕВ А.А. Задача минимизации сум-марной взвешенной длительности курсов для одного прибо-ра с ограничениями предшествования // Автоматика и теле-механика. – 2023. – №9. – С. 153–168.
  3. 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. 4. BRUCKER P. Scheduling algorithms. – Springer: Heidelberg,2007. – 371 p..
  5. 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. 6. CSEBFALVI A.B., CSEBFALVI G. Hammock activities inproject scheduling // Proc. of the Sixteenth Annual Conf. ofPOMS. – Chicago, IL, 2005.
  7. 7. ELIEZER O. A new bi–objective hybrid metaheuristicalgorithm for the resource-constrained hammock cost problem(RCHCP). – Doctoral Dissertation. – Pecs, 2011. – 111 p.
  8. 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. 9. HARHALAKIS G. Special features of precedence networkcharts // European Journal of Operational Research. – 1990. –Vol. 49, No. 1. – P. 50–59.
  10. 10. LAWLER E.L. Optimal sequencing of a single machine subjectto precedence constraints // Management Science. – 1973. –Vol. 19, No. 5. – P. 544–546.
  11. 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. 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. 13. LENSTRA J.K., RINNOOY KAN A.H.G. Complexityof scheduling under precedence constraints // OperationsResearch. – 1978. – Vol. 26, No. 1. – P. 22–35.
  14. 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. 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. 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. 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. 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. 19. VANHOUCKE M. Work continuity constraints in projectscheduling // Journal of Construction Engineering andManagement. – 2006. – Vol. 132, No. 1. – P. 14–25.
  20. 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. 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. 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. 23. https://www.ibm.com/docs/es/icos/22.1.0 (дата обращения:15.04.2025).

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать


Creative Commons License
Эта статья доступна по лицензии Creative Commons Attribution-NonCommercial 4.0 International License.

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).