Conditions for length reduction of the parallel sequence of special digraphs’ vertices  in the presence of interruptions

Turchyna V.A.; Kovalenko Y.O.

doi:10.34185/1562-9945-6-155-2024-19

Автор(и)

Turchyna V.A.
Kovalenko Y.O.

DOI:

https://doi.org/10.34185/1562-9945-6-155-2024-19

Ключові слова:

теорія розкладів, задачі комбінаторної оптимізації, паралельні упорядкування, орієнтовані графи, гусениці, граціозна розмітка, переривання, комбінаторна конфігурація.

Анотація

Прикладні задачі планування виробництва часто можна змоделювати у вигляді оптимізаційних задачах на орграфах, що відносяться до задач теорії розкладів. Однією з таких є задача паралельного упорядкування, в якій необхідно мінімізувати су-марний час виконання усіх робіт, на порядок виконання яких може бути накладено те-хнологічні обмеження, при заданих ресурсах. Для випадків, коли орграф задачі має спе-ціальну структуру, досліджено способи побудови на основі комбінаторних конфігура-цій та визначено, за яких умов дозвіл переривань при виконанні робіт може зменшити значення цільової функції.

Посилання

Burdyuk V. Ya. Parallel sequencing algorithms: textbook. / V. Ya. Burdyuk, V. A. Turchyna. – Dnipropetrovsk: DSU, 1985. 83 p.

Kovalenko Y. O. Analysis of the graph structure influence on the parallel sequencing problems with interruptions solution optimality [Electronic resource] / Y. O. Kovalenko, V. A. Turchyna // Problems of applied mathematics and mathematical modeling. – 2021. – Vol. 21. – pp. 130–137. - Mode of access: https://doi.org/10.15421/322113.

Turchyna V. A. The influence of the parallel sequencing problem with interruptions initial data on the solution optimality [Electronic resource] / V. A. Turchyna, Y. O. Kovalenko // Problems of applied mathematics and mathematical modeling. – 2022. – Vol. 22. – pp. 158-167. – Mode of access: https://doi.org/10.15421/322217.

Turchyna V. A. Investigation of the parallel sequencing problem with interruptions for one subclass of trees [Electronic resource] / V. A. Turchyna, Y. O. Kovalenko // Problems of applied mathematics and mathematical modeling. – 2023. – Vol. 23. – pp. 118-125. – Mode of access: https://doi.org/10.15421/322313.

Baker K. R. Principles of Sequencing and Scheduling [Electronic resource] / Kenneth R. Baker, Dan Trietsch. – Hoboken, NJ, USA : John Wiley & Sons, Inc., 2018. – Mode of ac-cess: https://doi.org/10.1002/9781119262602.

Lenstra J. K. On the complexity of scheduling unrelated parallel machines with limited preemptions [Electronic resource] / Jan Karel Lenstra, Nodari Vakhania // Operations Re-search Letters. – 2023. – Vol. 51, № 2. – P. 187-189. – Mode of ac-cess: https://doi.org/10.1016/j.orl.2023.02.004.

Petreniuk D. A. Graceful Trees: the State of Arts and the Prospects [Electronic resource] / D. A. Petreniuk // Control systems and computers. — 2016. — Vol. 1, № 2. — P. 16–25. – Mode of access: https://doi.org/10.15407/usim.2016.01.016.

Semeniuta M. F. Combinatorial Configurations in the Definition of Antimagic Labelings of Graphs [Electronic resource] / M. F. Semeniuta // Cybernetics and Systems Analysis. – 2021. – Vol. 57, № 2. – P. 196–204. – Mode of access: https://doi.org/10.1007/s10559-021-00344-y.