- Код статьи
- 10.31857/S000523102309009X-1
- DOI
- 10.31857/S000523102309009X
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том / Номер выпуска 9
- Страницы
- 153-168
- Аннотация
- Рассматривается одноприборная задача теории расписаний с заданным частичным порядком выполнения работ. Имеются подмножества работ, именуемые курсами. Необходимо построить расписание работ, при котором суммарное взвешенное время обработки всех курсов минимально. Рассматривается случай, когда начальная и конечная работы каждого курса определены однозначно. Доказана NP-трудность рассматриваемой задачи. Предложен алгоритм решения задачи, трудоемкость которого полиномиально зависит от общего числа работ, но экспоненционально - от количества курсов, что позволяет эффективно его использовать при фиксированном небольшом количестве курсов и произвольном числе работ.
- Ключевые слова
- теория расписаний задача одного прибора NP-трудные задачи минимизация простоя ресурсов
- Дата публикации
- 15.09.2023
- Год выхода
- 2023
- Всего подписок
- 0
- Всего просмотров
- 9
Библиография
- 1. Brucker P. Scheduling algorithms. Springer: Heidelberg, 2007.
- 2. Лазарев А.А. Теория расписаний. Методы и алгоритмы. М.: ИПУ РАН, 2019.
- 3. 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.
- 4. Harhalakis G. Special features of precedence network charts // Eur. J. Oper. Res., Elsevier Publ. 1990. V. 49. No. 1. P. 50-59.
- 5. Cs'ebfalvi A.B., Cs'ebfalvi G. Hammock activities in project scheduling // Proceedings of the Sixteenth Annual Conference of POMS. 2005.
- 6. Eliezer O. A new bi-objective hybrid metaheuristic algorithm for the resourceconstrained hammock cost problem (RCHCP) / Doctoral Dissertation. P'ecs, 2011.
- 7. El-Rayes K., Moselhi O. Resource-driven scheduling of repetitive activities // Construction Management and Economics. 1998. V. 16. No. 4. P. 433-446.
- 8. Vanhoucke M. Work continuity constraints in project scheduling / Working Paper 04/265, Ghent University, Faculty of Economics and Business Administration, Belgium. 2004.
- 9. 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.
- 10. 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.
- 11. Lenstra J.K., Rinnooy Kan A.H.G. Complexity of scheduling under precedence constraints // Oper. Res. 1978. V. 26. No. 1. P. 22-35.
- 12. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C.Introduction to algorithms. MIT press, 2022.
- 13. IBM ILOG CPLEX Optimization Studio // URL: https://www.ibm.com/products/ilog-cplex-optimization-studio.
- 14. 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.
