ПРО ПОКРАЩЕННЯ НАБЛИЖЕНИХ РОЗВ’ЯЗКІВ ЗАДАЧІ ПАРАЛЕЛЬНОГО УПОРЯДКУВАННЯ ТА АНАЛІЗ МОДЕЛІ ОДНОГО ЇЇ УЗАГАЛЬНЕННЯ

Анотація

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