ЗАДАЧА МІНІМІЗАЦІЇ СУМАРНОГО ВІДХИЛЕННЯ ВІД СПІЛЬНОГО ДИРЕКТИВНОГО СТРОКУ ПРИ ВИКОНАННІ ЗАВДАНЬ ПАРАЛЕЛЬНИМИ ПРИСТРОЯМИ

Анотація

У статті розглядається задача теорії розкладів, у якій необхідно скласти розклад виконання завдань зі спільним директивним строком паралельними пристроями за критерієм мінімізації сумарного відхилення моментів завершення завдань від директивного строку. Особливістю задач, які розглядаються, є те, що немає обмежень на початок виконання завдань (на момент запуску розкладу). У роботі розглядаються два випадки: в першому пристрої є ідентичними, а в другому – пропорційними, тобто такими, що відрізняються швидкістю роботи. Окремо розглядається частковий випадок, коли в обслуговуючій системі є тільки один пристрій. Для усіх задач розроблено алгоритм побудови оптимального розкладу. Наведено приклади розв’язання розглянутих задач.

Ключові слова: розклад, директивний строк, момент запуску, паралельні пристрої, ідентичні пристрої, пропорційні пристрої, запізнення, випередження, мінімізація сумарного відхилення.

магистрант, Годная А. В., кандидат технических наук, доцент, Жданова Е. Г., магистрант, Маленко А. А., кандидат технических наук, старший преподаватель, Сперкач М. О. Задача минимизации суммарного отклонения от общего директивного срока при выполнении заданий параллельными приборами / Национальный технический университет Украины «Киевский политехнический институт имени Игоря Сикорского», Украина, Киев

В статье рассматривается задача теории расписаний, в которой необходимо составить расписание выполнения заданий c общим директивным сроком параллельными устройствами по критерию минимизации суммарного отклонения моментов завершения заданий от директивного срока. Особенностью задач, которые рассматриваются, является то, что нет ограничений на начало выполнения заданий (на момент запуска расписания). В работе рассматриваются два случая: в первом устройства идентичны, а во втором - пропорциональны, то есть такие, которые отличаются скоростью работы. Отдельно рассматривается частный случай, когда в обслуживающей системе есть только одно устройство. Для всех задач разработан алгоритм построения оптимального расписания. Приведены примеры решения рассмотренных задач.

Ключевые слова: расписание, директивный срок, момент запуска, параллельные приборы, идентичные приборы, пропорциональные приборы, запаздывание, опережение, минимизация суммарного отклонения.

undergraduate, Hodna A. V., PhD, associate professor, Zhdanova O. G., undergraduate, Malenko A. O., PhD, senior lecturer, Sperkach M. O. The problem of minimizing the total deviation of ending times of performing task  for common due date by parallel machines / National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Ukraine, Kyiv

The article presents the problem of scheduling theory, in which it is necessary to schedule the tasks with a common due date on several parallel machines by the criterion of minimizing the total deviation of the completion of tasks from the due date. Problem’s main feature is that there are no restrictions on the beginning of the tasks execution (at the schedule’s launch time). Two cases are considered in the article: in the first device are identical, and in the second - are proportional, that is, those that differ in the speed of work. Servicing system with only one device is considered as a corner case. Optimal scheduling algorithm has been developed for all considered problems. Algorithm usage examples are provided.

Key words: schedule, due date, release date, parallel machines, identical machines, proportional machines, tardiness, earliness, minimizing the total deviation.