Karavaiev K. Methods and algorithms for solving classical and generalised problems of digraph vertices sequencing

Українська версія

Thesis for the degree of Doctor of Philosophy (PhD)

State registration number

0824U002290

Thesis Registration Form

0824U002290.pdf

Applicant for

Kostiantyn D. Karavaiev

Specialization

113 - Прикладна математика

Specialized Academic Board

ДФ 08.051.086 ID 6112 Караваєв К.Д.

Oles Honchar Dnipro National University

Essay

The thesis is devoted to the development and justification of exact and approximate methods and algorithms for solving classical and generalised problems of parallel sequencing of acyclic directed graph vertices. The scientific novelty of the obtained results is as follows: for the first time, the possibility of reducing any classical optimal sequencing problem to a problem with a dense sequencing and a given parity of width was proved; the classical algorithm for solving the problem with two executors was further developed for the construction of dense sequencings; for the first time, an approach to reduce the branching in the branch-and-bound method by excluding branches corresponding to isomorphic subgraphs is proposed: exact and approximate variants of its implementation are considered; a necessary condition for the existence of dense sequencings was obtained and efficient algorithms for its testing for general and special graph structures were proposed; for the first time, a sequence of lower-bound estimates of the sequencing length was constructed, in which each subsequent estimate is theoretically more accurate than the previous one; a method for determining the range of valid vertex places was further developed by taking into account the width of the sequencing; the possibility of reducing a problem with a variable sequencing width to a classical problem was proved; new scientific results on polynomial approximate algorithms for solving the problem with variable width for binary in-trees were obtained; for the first time, a class of generalized optimal sequencing problems with incomplete workload is considered; computational experiments were conducted to determine the effectiveness of the proposed methods and algorithms. The obtained results can improve the efficiency of scheduling tasks in various practically important areas and industries, including industrial production, logistics, prioritization of resource use and their allocation, parallelization and distribution of computing, real-time data processing and monitoring, etc. In addition, they can be of great importance for the development of modern technologies, in particular automated parallelization, and serve as a foundation for new areas of research in this field.

Thesis supervisor

Valentyna A. Turchyna

Official opponents

Maryna F. Semeniuta
Oksana S. Pichugina
Igor V. Kozin

Reviewers

Natalia A. Guk

Research papers

1. Караваєв К. Д. Про необхідні умови існування щільних упорядкувань в класичній задачі паралельного упорядкування. Збірник наукових праць «Системні технології», м. Дніпро, 2024. Вип. 151. С. 76–91. DOI: https://doi.org/10.34185/1562-9945-2-151-2024-07.

2. Караваєв К. Д., Турчина В. А. Узагальнення задач упорядкування з урахуванням неповного завантаження. Збірник наукових праць «Питання прикладної математики і математичного моделювання», м. Дніпро, 2022. Вип. 22. С. 67–79. DOI: https://doi.org/10.15421/322207.

3. Караваєв К. Д., Турчина В. А. Аналіз впливу автоморфізму графу на схеми направленого перебору. Збірник наукових праць «Питання прикладної математики і математичного моделювання», м. Дніпро, 2021. Вип. 21. С. 94–104. DOI: https://doi.org/10.15421/322110.

4. Turchyna V., Karavaiev K. Analysis of algorithms for constructing dense sequencing of digraphs vertices. Proceedings of The Third International Workshop on Computer Modeling and Intelligent Systems (CMIS-2020), Zaporizhzhia, 2020. P. 690–703. DOI: https://doi.org/10.32782/cmis/2608-53.

5. Турчина В. А., Караваєв К. Д. Дослідження оцінок довжини паралельного упорядкування вершин графу. Збірник наукових праць «Питання прикладної математики і математичного моделювання», м. Дніпро, 2018. Вип. 18. С. 186–195. DOI: https://doi.org/10.15421/321819.

6. Турчина В. А., Караваєв К. Д. Контрприклад до алгоритму перерахування паралельно-послідовних графів без ізоморфізму. Математичне та програмне забезпечення інтелектуальних систем (MSSIS-2023): Матеріали XXI міжнародної науково-практичної конференції, 22-24 листопада 2023 р., м. Дніпро, 2023. С. 291–292. URL: http://mpzis.dnu.dp.ua/wp-content/uploads/2023/11/mpzis-2023.pdf.

7. Караваєв К. Д., Турчина В. А. Про необхідні та достатні умови наявності автоморфізму у паралельно-послідовних графах. Комбінаторні конфігурації та їхні застосування: Матеріали XXV Міжнародного науково-практичного семінару імені А. Я. Петренюка, (Запоріжжя – Кропивницький, 14-16 червня 2023 року) / за ред. Г.П. Донця, м. Запоріжжя - Кропивницький, 2023. C. 122–129. URL: https://zp.edu.ua/uploads/dept_s&r/2023/conf/1.4/Petrenyuk_ISPS-25-proc.pdf.

8. Караваєв К. Д. Використання інваріантів графів для скорочення напрямленого перебору у задачах упорядкування. Математичне та програмне забезпечення інтелектуальних систем (MSSIS-2022): Матеріали XX ювілейної міжнародної науково-практичної конференції, 23-25 листопада 2022 р., м. Дніпро, 2022. С. 96–97. URL: http://mpzis.dnu.dp.ua/wp-content/uploads/2022/12/MPZIS-2022-1.pdf.

9. Караваєв К. Д., Турчина В. А. Про зв’язок задач ізоморфізму графів та упорядкування їх вершин. Комбінаторні конфігурації та їхні застосування: Матеріали XXIV Міжнародного науково-практичного семінару імені А. Я. Петренюка, (Запоріжжя – Кропивницький, 13-14 травня 2022 року) / за ред. Г.П. Донця, м. Запоріжжя - Кропивницький, 2022. C. 30–33. URL: https://zp.edu.ua/uploads/dept_s&r/2023/conf/1.4/Petrenyuk_ISPS-25-proc.pdf.

10. Караваєв К. Д., Турчина В. А. Деякі узагальнення задачі паралельного упорядкування. Комбінаторні конфігурації та їхні застосування: Матеріали XXIII Міжнародного науково-практичного семінару імені А. Я. Петренюка, присвяченого 70-річчю Льотної академії Національного авіаційного університету, (Запоріжжя – Кропивницький, 13-15 травня 2021 року) / за ред. Г.П. Донця, м. Запоріжжя - Кропивницький, 2021. C. 93–97. URL: https://www.glau.kr.ua/images/docs/sbornik/materiali_23_mnp_seminaru.pdf.

11. Karavaiev K., Turchyna V., Hurko O. The problem of consistencing the architecture of computational systems and algorithms. Сучасні науково-технічні дослідження у контексті мовного простору (іноземними мовами) 13 травня 2021 року: матеріали X Регіональної науково-практичної конференції молодих учених та студентів, м. Дніпро, 2021. С. 142–145. URL: https://www.dnu.dp.ua/docs/ndc/2021/19_Сучасні%20науково-технічні%20дослідження%20у%20контексті%20мовного%20простору.pdf.

12. Турчина В. А., Караваєв К. Д. Дослідження оцінки точності алгоритму, заснованого на лексикографічному порядку. Математичне та програмне забезпечення інтелектуальних систем (MSSIS-2019): Матеріали XVІІ міжнародної науково-практичної конференції, 20-22 листопада 2019 р., м. Дніпро, 2019. С. 258–259. URL: http://mpzis.dnu.dp.ua/wp-content/uploads/2019/12/MPZIS_2019.pdf.

13. Турчина В. А., Караваєв К. Д. Застосування рівневого принципу до аналізу задач паралельного упорядкування та їх узагальнення. Міжнародний науковий симпозіум «Інтелектуальні рішення». Обчислювальний інтелект (результати, проблеми, перспективи): праці міжнар. наук.-практ. конф., 15-20 квітня 2019 р., м. Ужгород, 2019. С. 56–57. URL: https://er.chdtu.edu.ua/bitstream/ChSTU/3192/1/OI-2019.pdf.

0824U002255

Vitalii O. Husak

Ways to improve the efficiency of numerical-analytical methods for solving boundary value problems for non-canonical domains

0824U002172

Oleh S. Kharkov

Modified Extragradient Algorithms for Variational Inequalities and Their Applications

0824U002162

Stanislav S. Masalykin

Statistical modeling of energy flows in the systems of solar energy concentration

0824U002163

Andrii H. Borysenko

Mathematical and computer modeling of heat exchange in the nanofluid heat transfer fluid of solar thermodynamic plants

0824U002179

Roman S. Yurkov

Modeling of energy flows in thermal energy storage systems with “solid - liquid” phase transition