ПОРЯДОК ВВЕДЕННЯ ЗАВДАНЬ ДЛЯ ЕФЕКТИВНОЇ ТОЧНОЇ МІНІМІЗАЦІЇ ЗАГАЛЬНОГО ЗАПІЗНЮВАННЯ У ЩІЛЬНОМУ ПРОГРЕСУЮЧОМУ ОДНОМАШИННОМУ ПЛАНУВАННІ З ПЕРЕМИКАННЯМИ БЕЗ ПРОСТОЮ

Анотація

Анотація. Розклад, що забезпечує строго мінімальне загальне запізнювання, можна знайти
за відповідною цілочисловою задачею лінійного програмування. Відкритим є питання про те, чи
змінюється час обчислення точного розкладу, якщо дати запуску завдань вводяться у модель у
зворотному порядку. Мета полягає у тому, щоб встановити, чи впливає на швидкість обчислення
точного розв’язку порядок завдань у щільному прогресуючому одномашинному плануванні з
перемиканнями без простою. Для пошуку розкладів з мінімальним загальним запізнюванням
використовується модель бульового лінійного програмування. Для досягнення зазначеної мети проводиться обчислювальне дослідження з метою оцінки усередненого часу обчислення як для
висхідного порядку, так і для спадного порядку дат запуску завдань. Приклади задачі планування
завдань генеруються так, що розклади, які можна отримати тривіально, без точної моделі, не
розглядаються. Як і у випадку з рівноцінними завданнями, було встановлено, що порядок завдань
дійсно впливає на швидкість обчислення розкладів, загальне запізнювання яких мінімальне.
Планування від двох до п’яти завдань виконується у середньому швидше за спадним порядком
завдань, де очікується прискорення від 1 до 3 %. Подальше збільшення кількості планованих
завдань не може гарантувати жодного прискорення, навіть у середньому. Цей результат подібний
до випадку з рівноцінними завданнями, але регулярності в такому ефективному порядку введення
завдань немає. Без жодних гарантій щодо однієї задачі планування завдань, ефективна точна
мінімізація загального запізнювання за спадним порядком завдань повинна трактуватися лише як у
середньому.