Евристичні алгоритми побудови ефективних послідовностей виконання завдань на одній машині у взаємопов'язаних виробничих системах

• Main Author: Zack, Yuriy O.
• Format: Article
• Language: rus
• Published: The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2020
• Subjects: послідовності виконання завдань; багатостадійні розклади; мінімальний час; евристичний алгоритм; нижня межа значення критерію оптимальності; последовательности выполнения заданий; многостадийные расписания; минимальное время; эвристический алгоритм; нижняя граница значения критерия оптимальности; task execution sequences; multistage schedules; minimum time; heuristic algorithm; lower bound on the value of the optimality criterion
• Online Access: http://journal.iasa.kpi.ua/article/view/209140

The classical task in the theory of scheduling which is the task of constructing a sequence of tasks on one machine, taking into account not only the time spent on equipment operation, but also the loss of post-processing, is considered for multi-stage production systems consisting of an interconnected chain of sections and workshops of an industrial enterprise. As an optimality criterion, the implementation of a multi-stage schedule in the shortest possible time is considered. Methods are proposed for calculating the lower bound on the length of the optimal pattern along with heuristic algorithms for obtaining approximate solutions that require small amounts of computation. The proposed algorithms are illustrated by numerical examples.