- Код статьи
- 10.31857/S0005231023080093-1
- DOI
- 10.31857/S0005231023080093
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том / Номер выпуска 8
- Страницы
- 138-152
- Аннотация
- Предложен алгоритм имитации отжига для построения многопроцессорных списочных расписаний минимальной длительности с дополнительным ограничением на количество передач между процессорами. Данное ограничение характерно для вычислительных систем с жесткими ограничениями на ресурсы межпроцессорной сети передачи данных. В целом задача минимизации длительности расписания возникает при разработке систем обработки данных в реальном масштабе времени, таких как бортовые и телекоммуникационные системы. Также задача актуальна для периферийных вычислений (edge computing). Экспериментальное исследование свойств алгоритма показало его высокую точность, стабильность и масштабируемость.
- Ключевые слова
- комбинаторная оптимизация списочные расписания алгоритм имитации отжига
- Дата публикации
- 15.08.2023
- Год выхода
- 2023
- Всего подписок
- 0
- Всего просмотров
- 4
Библиография
- 1. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000.
- 2. Теория расписаний и вычислительные машины / Под ред. Э.Г. Коффмана. М.: Наука, 1984.
- 3. Костенко В.А. Алгоритмы комбинаторной оптимизации, сочетающие жадные стратегии и ограниченный перебор // Известия РАН. Теория и системы управления. 2017. № 2. C. 48-56.
- 4. Lawler E.L., Wood D.E. Branch-and-Bound Methods: A Survey // Oper. Res. 1966. V. 14. No. 4. P. 699-719. https://doi.org/10.1287/opre.14.4.699
- 5. Fujita S. A Branch-and-Bound Algorithm for Solving the Multiprocessor Scheduling Problem with Improved Lower Bounding Techniques // IEEE Transact. Comput. 2011. https://doi.org/10.1016/j.procs.2016.07.216
- 6. Калашников А.В., Костенко В.А. Параллельный алгоритм имитации отжига для построения многопроцессорных расписаний // Известия РАН. Теория и системы управления. 2008. № 3. С. 133-142.
- 7. Зорин Д.А., Костенко В.А. Алгоритм имитации отжига для решения задач построения многопроцессорных расписаний // АиТ. 2014. № 10. С. 97-110.
- 8. Holland J.N. Adaptation in Natural and Arti cial Systems / Ann Arbor, Michigan: Univ. of Michigan Press, 1975.
- 9. Скобцов Ю.А. Основы эволюционных вычислений. Донецк: ДонНТУ, 2008.
- 10. Akbari M., Rashidi H. An E cient Algorithm for Compile-Time task scheduling problem on heterogeneous computing systems // Int. J. Academ. Res. 2015. V. 7. No. 1. P. 192-202. https://doi.org/10.7813/2075-4124.2015/7-1/A.45
- 11. Rzadca K., Seredynski F. Heterogeneous Multiprocessor Scheduling with Di erential Evolution // IEEE Congress on Evolutionary Computation, 2005. V. 3. P. 2840-2847. https://doi.org/10.1109/CEC.2005.1555051
- 12. Dorigo M. Optimization, Learning and Natural Algorithms // Ph.D. Thesis. Dipartimentodi Elettronica. Milano: Politechnico Di Milano, 1992.
- 13. Штовба С.Д. Муравьиные алгоритмы: теория и применение // Программирование. 2005. № 4. С. 1-15.
- 14. Myszkowski P.B., Skowronski M.E., Olech L.P. et al. Hybrid ant colony optimization in solving multi-skill resource-constrained project scheduling problem // Soft Comput. 2015. V. 19. No. 12. P. 3599-3619. https://doi.org/10.1007/s00500-014-1455-x
- 15. Растригин Л.А. Статистические методы поиска. М.: Наука, 1968.
- 16. Шахбазян К.В., Тушкина Т.А. Обзор методов составления расписаний для многопроцессорных систем // Зап. научн. сем. ЛОМИ. 1975. Т. 54. C. 229-258.
- 17. Garey M.R., Johnson D.S.Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., 1979.
- 18. Rahman M. Branch and Bound Algorithm for Multiprocessor Scheduling // M.S. Thesis, Dept.Comput. Eng., Dalarna Univ., Sweden, 2009.
- 19. Venugopalan S., Sinnen O. Optimal Linear Programming Solutions for Multiprocessor Scheduling with Communication Delays // Proc. ICA3PP 2012: Algorithms and Architectures for Parallel Processing, 2012. P. 129-138. https://doi.org/10.1016/j.jpdc.2016.03.003
- 20. Mallach S. Improved Mixed-Integer Programming Models for the Multiprocessor Scheduling Problem with Communication Delays // J. Combinat. Optim. 2018. V. 36. P. 871-895. https://doi.org/10.1007/s10878-017-0199-9
- 21. Hwang R., Gen M., Katayama H. A Comparison of Multiprocessor Task Scheduling Algorithms with Communication Costs // Comput. Oper. Res. 2008. V. 35. P. 976-993. https://doi.org/10.1016/j.cor.2006.05.013
- 22. Красовский Д.В. Алгоритмы решения задачи составления оптимального расписания без прерываний // Дисс.. канд. физ.-мат. наук, 05.13.18 Москва, 2007, 109 с.
- 23. da Silva E.C., Gabriel P.H.R. Genetic Algorithms and Multiprocessor Task Scheduling: A Systematic Literature Review // Proc. ENIAC 2019. P. 250-261. https://doi.org/10.5753/eniac.2019.9288
- 24. Sheikh H.F., Ahmad I., Fan D. An Evolutionary Technique for Performance-Energy-Temperature Optimized Scheduling of Parallel Tasks on Multi-Core Processors // IEEE Trans. Parallel Distributed Syst., 2016. V. 27. No. 3. P. 668-681. https://doi.org/10.1109/TPDS.2015.2421352
- 25. Lo S.-T., Chen R.-M., Huang Y.-M., Wu C.-L. Multiprocessor System Scheduling with Precedence and Resource Constraints Using an Enhanced Ant Colony System // Expert Syst. Appl. 2008. V. 34. No. 3. P. 2071-2081. https://doi.org/10.1016/j.eswa.2007.02.022
- 26. METIS - Serial Graph Partitioning and Fill-reducing Matrix Ordering: [Электронный ресурс]. URL: http://glaros.dtc.umn.edu/gkhome/metis/metis/overview (Дата обращения: 21.11.2022).
- 27. METIS. A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices Version 5.1.0: [Электронный ресурс]. URL: http://glaros.dtc.umn.edu/gkhome/fetch/sw/metis/manual.pdf (Дата обращения: 21.11.2022).
- 28. Wu M.-Y., Gajski D.D. Hypertool: A programming aid for message-passing systems // IEEE Trans. Parallel Distributed Syst. 1990. V. 1. P. 330-343. https://doi.org/10.1109/71.80160
- 29. Костенко В.А. Задача построения расписания при совместном проектировании аппаратных и программных средств // Программирование. 2002. № 3. С. 64-80.
