РЕШЕНИЕ ЗАДАЧ ПЛАНИРОВАНИЯ РАБОЧЕГО ЦЕХА С МАШИНАМИ,  ДОПУСКАЮЩИМИ ОДНОВРЕМЕННУЮ ОБРАБОТКУ ТРЕБОВАНИЙ

Дмитрий Игоревич Коровин; Лев Николаевич Чернышов

doi:10.6060//ivecofin.2021493.560

Дмитрий Игоревич Коровин Финансовый университет при правительстве Российской Федерации https://orcid/org/0000-0001-9941-0322
Лев Николаевич Чернышов Московский авиационный институт https://orcid/org/0000-0002-1512-4052

DOI: https://doi.org/10.6060//ivecofin.2021493.560

Ключевые слова: теория графов, теория расписаний, окраска графа, садка, алгоритм построения расписаний

Аннотация

В статье приводится авторский алгоритм для решения одной задачи теории расписаний, которая возникла в реализации производственной деятельности. Метод основан на принципе раскраски графов и позволяет реализовать одновременную обработку нескольких деталей на одном рабочем месте. В кратком анализе задач теории расписаний определяется место рассматриваемой постановки задачи в общей классификации задач. Разработан алгоритм и программа, решающие эту задачу для различных критериев оптимальности. Реализованы два варианта программы. Первый непосредственно следует структурам данных и последовательности действий метода, основанного на раскраске графов. Во втором варианте используются структуры линейного представления графа, а также введены многотактовые операции, что позволило повысить эффективность алгоритма. Приведены временные характеристики выполнения программы на разном количестве деталей для двух вариантов программы. В заключение рассматриваются перспективы развития программы и сферы ее применения.

Литература

Schedule Theory. https://ru.wikipedia.org/wiki/Теория расписаний. (in Russian).

Garey M.R., Johnson D.S., Ravi Sethi. The Complexity of Flowshop and Jobshop Scheduling. INFORMS. Mathematics of Operations Research. 1976. Vol. 1. N 2. Р. 117-129.

The Scheduling Zoo. http://www-desir.lip6.fr/~durrc/query/.

Shaw A. The Logical Design of Operating System. Mir. 1981. 360 p. (in Russian).

Korovin D.I. Logical principles in the organization of production. Ivanovo: IvSU. 2006.154 р. (in Russian).

Beregovyh U.V., Vasiliev B.A., Volodin N.A. Algorithm for scheduling classes. Artificial intelligence. 2009. N 2. Р. 50-56. (in Russian).

Pankratiev E.V., Cherepovskij A.M., Cherepanov E.A., Chernyshov S.V. Algorithms and methods for solving scheduling problems and other extremal problems on graphs of large dimensions. Fundamental and Applied Mathematics. 2003. Vol. 9. № 1, Р. 235-251. (in Russian).