Отправить статью по E-mail 
Задача минимизации суммарной взвешенной длительности курсов для одного прибора с ограничениями предшествования
- Авторы: Мусатова Е.Г.1, Лазарев А.А.1
-
Учреждения:
- Институт проблем управления им. В.А. Трапезникова РАН
- Выпуск: № 9 (2023)
- Страницы: 153-168
- Раздел: Оптимизация, системный анализ и исследование операций
- URL: https://ruspoj.com/0005-2310/article/view/646739
- DOI: https://doi.org/10.31857/S000523102309009X
- EDN: https://elibrary.ru/JUNOUZ
- ID: 646739
Цитировать
Полный текст
Открытый доступ
Доступ предоставлен
Доступ платный или только для подписчиков
Аннотация
Рассматривается одноприборная задача теории расписаний с заданным частичным порядком выполнения работ. Имеются подмножества работ, именуемые курсами. Необходимо построить расписание работ, при котором суммарное взвешенное время обработки всех курсов минимально. Рассматривается случай, когда начальная и конечная работы каждого курса определены однозначно. Доказана NP-трудность рассматриваемой задачи. Предложен алгоритм решения задачи, трудоемкость которого полиномиально зависит от общего числа работ, но экспоненционально - от количества курсов, что позволяет эффективно его использовать при фиксированном небольшом количестве курсов и произвольном числе работ.
Ключевые слова
Об авторах
Е. Г. Мусатова
Институт проблем управления им. В.А. Трапезникова РАН
Email: nekolyap@mail.ru
Москва
А. А. Лазарев
Институт проблем управления им. В.А. Трапезникова РАН
Автор, ответственный за переписку.
Email: jobmath@mail.ru
Москва
Список литературы
- Brucker P. Scheduling algorithms. Springer: Heidelberg, 2007.
- Лазарев А.А. Теория расписаний. Методы и алгоритмы. М.: ИПУ РАН, 2019.
- Lazarev A., Khusnullin N., Musatova E., Yadrentsev D., Kharlamov M., Ponomarev K. Minimization of the weighted total sparsity of cosmonaut training courses // Optimization and Applications. OPTIMA 2018. Communications in Computer and Information Science. 2019. P. 202-215.
- Harhalakis G. Special features of precedence network charts // Eur. J. Oper. Res., Elsevier Publ. 1990. V. 49. No. 1. P. 50-59.
- Cs'ebfalvi A.B., Cs'ebfalvi G. Hammock activities in project scheduling // Proceedings of the Sixteenth Annual Conference of POMS. 2005.
- Eliezer O. A new bi-objective hybrid metaheuristic algorithm for the resourceconstrained hammock cost problem (RCHCP) / Doctoral Dissertation. P'ecs, 2011.
- El-Rayes K., Moselhi O. Resource-driven scheduling of repetitive activities // Construction Management and Economics. 1998. V. 16. No. 4. P. 433-446.
- Vanhoucke M. Work continuity constraints in project scheduling / Working Paper 04/265, Ghent University, Faculty of Economics and Business Administration, Belgium. 2004.
- Vanhoucke M., Van Osselaer K. Work continuity in a real-life schedule: the Westerschelde Tunne / Working Paper 04/271, Ghent University, Faculty of Economics and Business Administration, Belgium. 2005.
- Graham R.L., Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G. Optimization and approximation in deterministic sequencing and scheduling: a survey // Annals of Discrete Mathematics, Elsevier Publ. 1979. V. 5. P. 287-326.
- Lenstra J.K., Rinnooy Kan A.H.G. Complexity of scheduling under precedence constraints // Oper. Res. 1978. V. 26. No. 1. P. 22-35.
- Cormen T.H., Leiserson C.E., Rivest R.L., Stein C.Introduction to algorithms. MIT press, 2022.
- IBM ILOG CPLEX Optimization Studio // URL: https://www.ibm.com/products/ilog-cplex-optimization-studio.
- Potts C.N. An algorithm for the single machine sequencing problem with precedence constraint / Combinatorial Optimization II. Mathematical Programming Studies, Springer: Berlin, Heidelberg, 1980. V. 13. P. 78-87.
Дополнительные файлы
