ПРО НЕОБХІДНІ УМОВИ ІСНУВАННЯ ЩІЛЬНИХ УПОРЯДКУВАНЬ В КЛАСИЧНІЙ ЗАДАЧІ ПАРАЛЕЛЬНОГО УПОРЯДКУВАННЯ
DOI:
https://doi.org/10.34185/1562-9945-2-151-2024-07Ключові слова:
графи, комбінаторна оптимізація, теорія розкладів, метод гілок та меж, розмітка графів, щільні упорядкування, оптимальний розподіл вершин.Анотація
Побудова схем паралелізації обчислень на ЕОМ при обробці великих масивів даних нерозривно пов’язана з задачами паралельного упорядкування. Розглядається класична задача мінімізації довжини упорядкування при заданій ширині, в якій шукане упорядкування є щільним. Досліджуються необхідні умови існування щільного упоряд-кування при застосуванні методу гілок та меж, пов’язані з обмеженістю потужності місць та можливістю їх заповнення. Отримані умови були зведені до однієї, запропо-новано ефективні алгоритми її перевірки в загальному випадку та для графів, всі вер-шини яких знаходяться на критичних шляхах. В результаті дослідження також були отримані нові уточнені оцінки знизу довжини упорядкування та запропоновані уза-гальнення спеціальних упорядкувань, які враховують ширину упорядкування.
Посилання
Burdiuk V. Ya., Turchyna V. A. Parallel sequencing algorithms: training manual. Dnipropetrovsk: DSU, 1985. 83 p.
Levey E., Rothvoss T. A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies. SIAM Journal on Computing. 2019. P. 201–217.
Garg Sh. Quasi-PTAS for scheduling with precedences using LP hierarchies. In 45th International Colloquium on Automata, Languages, and Programming, ICALP. 2018.
Li S. Towards PTAS for Precedence Constrained Scheduling via Combinatorial Al-gorithms. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). 2021. P. 2991–3010.
Nederlof J., Swennenhuis C. M. F., Węgrzycki K. A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints. 2023. 25 p. (Pre-print. arXiv; arXiv:2312.03495).
Gangal D., Ranade A. Precedence constrained scheduling in (2−7/3p+1)optimal. Journal of Computer and System Sciences. 2008. Vol. 74, no. 7. P. 1139–1146.
Muhuri P. K., Biswas S. K. Bayesian optimization algorithm for multi-objective scheduling of time and precedence constrained tasks in heterogeneous multiproces-sor systems. Applied Soft Computing. 2020. Vol. 92. P. 106–274.
Yoo M. Real-time task scheduling by multiobjective genetic algorithm. Journal of Systems and Software. 2009. Vol. 82, no. 4. P. 619–628.
Turchyna V., Karavaiev K. Analysis of algorithms for constructing dense sequenc-ing of digraphs vertices. Proceedings of The Third International Workshop on Computer Modeling and Intelligent Systems (CMIS-2020), Zaporizhzhia, 2020.
P. 690–703.
Chardon M., Moukrim A. The Coffman-Graham Algorithm Optimally Solves UET Task Systems with Overinterval Orders. SIAM Journal on Discrete Mathematics. 2005. Vol. 19, no. 1. P. 109–121.
Vásquez Ó. C. The Scheduling Zoo. URL: http://schedulingzoo.lip6.fr/ (date of access: 30.03.2024).
Li K. Scheduling Precedence Constrained Tasks for Mobile Applications in Fog Computing. IEEE Transactions on Services Computing. 2022. P. 1–14.
Karavaiev K. D., Turchuna V.A. Analysis of the effect of graph automorphism on state search schemes. Problems of applied mathematics and mathematical modelling, Dnipro, 2021. Vol. 21. P. 94–104.
Turchuna V. A., Karavaiev K. D. Investigation of the estimates of the length of parallel alignment of the vertices of the graph. Problems of applied mathematics and mathematical modelling, Dnipro, 2018. Vol. 18. P. 186–195.
Bentley J. Programming pearls. Communications of the ACM. 1984. Vol. 27, no. 9. P. 865–873.
Завантаження
Опубліковано
Номер
Розділ
Ліцензія
Авторське право (c) 2024 Системні технології
Ця робота ліцензується відповідно до ліцензії Creative Commons Attribution 4.0 International License.
