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

Проблематика. Задача мінімізації загального зваженого запізнювання може бути розв’язана або точно за відповідними моделями, або евристично. На момент жовтня 2019 р. близькою до найкращої є евристика на основі використання залишкового наявного ресурсу та залишкового періоду до обробки. Ця евристика є надзвичайно швидкою порівняно з моделями точного розв’язку, але її точність може бути як 100 %, так і недопустимо низькою. Мета дослідження. З огляду на відсутність знань щодо взаємозв’язку між цією евристикою та моделлю булевого лінійного програмування для точних розв’язків метою є вивчення статистичної різниці між ними для одномашинної задачі планування з перемиканнями без періодів простою, у якій періоди обробки є рівними, а послідовно прогресуючі моменти запуску та прийому виконання задані щільно. Методика реалізації. Визначається відносна похибка евристики, а потім вивчається, як вона змінюється залежно від зрос­таючої складності задач планування завдань. Під складністю розуміється кількість завдань разом із кількістю періодів обробки одного завдання. Тривалості обчислень евристики і точної моделі фіксуються також. Результати дослідження. Евристика успішно замінила точну модель не менш ніж у 72 % окремих прикладів без переви­щення ліміту часу, де вона розплановує завдання з тим самим мінімальним загальним зваженим запізнюванням (100 %-ва точ­ність). У середньому цей рівень коливається від 90 до 97 %, хоча у решті випадків можуть з’являтися величезні похибки. У практиці розкладів із вимогами швидкого оновлення модель булевого лінійного програмування насправді є ледь здійсненною, коли йдеться про планування розкладів не менш ніж 14 завдань, де кожне завдання складається з двох частин, та не менш ніж 10 завдань, де кожне завдання складається з трьох частин. Планування завдань, де кожне завдання розділене на більшу кількість частин, матиме значно меншу найгіршу похибку, ніж планування завдань, де кожне завдання розділене на меншу кількість частин. Якщо завдання ще можна розділити, то наполегливо рекомендується ділити завдання на якомога більшу кількість частин. Якщо планування лише 2-х завдань є неможливим, то наполегливо рекомендується штучно збільшити кількість завдань для складання їх розкладу. Висновки. Мінімізація загального зваженого запізнювання у щільному прогресуючому одномашинному плануванні з пере­миканнями без періодів простою може бути достатньо точною за допомогою евристики, якщо складається розклад для не менш ніж 7-х завдань, де кожне розділене не менш ніж на п’ять частин (схема “7/5”). Винятком з цього правила є те, що лише 2 завдання евристика розплановує завжди з точністю 100 %, незалежно від того, на скільки частин завдання розділене (виняток “2/any”). Певною проміжною ланкою між схемою “7/5” та винятком “2/any” є те, що планування 3-х завдань, де кожне розділене на чотири або п’ять частин, є також достатньо точним, де неточність не перевищує 0,7 %. В інших випадках або евристика незастосовна, або існує великий ризик отримання недопустимих похибок. Незастосовність тут не означає одразу сильну неточність, а мається на увазі непередбачуване існування серйозного спаду точності. Наприклад, 974 з 1000 окремих прикладів, що складалися з виключно 3-х завдань, розділених на дві частини, були розплановані з точністю 100 %, але 26 прикладів були розплановані із середньою похибкою в 13,31 %, що є вкрай недопустимим і, відповідно, незастосовним.