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

Проблематика. У постановці задачі мінімізації загального запізнювання за евристикою на основі використання залишкового наявного ресурсу та залишкового періоду до обробки існують два протилежних способи введення даних: дати запуску зав­дань задаються в порядку зростання або спадання. Нещодавно було доведено, що ефективний порядок завдань може заощадити значний час обчислень при використанні моделі булевого лінійного програмування для пошуку розкладів зі строго мінімальним загальним запізнюванням. Мета дослідження. Метою є встановлення того, чи порядок завдань є суттєвим у складанні розкладів за допомогою евристики. Ефективність порядку завдань буде досліджена на прикладі щільного прогресуючого 1-машинного планування рівноцінних завдань із перемиканнями без простою. Методика реалізації. Для досягнення зазначеної мети проводиться обчислювальне дослідження з метою оцінки усередненого часу обчислення як для висхідного порядку, так і для спадного порядку дат запуску завдань. Приклади задачі планування завдань генеруються так, що розклади, які можна отримати тривіально, без евристики, не розглядаються. Результати дослідження. У випадку кількох завдань їх планування виконується очікувано швидше за висхідного порядку, але у цій частини забагато обчислювальних артефактів. Планування від 30 до 70 завдань на 1,5–2,5 % швидше за спадного порядку. Однак планування до 90 завдань, як очікується, все одно буде швидше за спадним порядком, хоча існує ризик втрати цієї переваги. Для кількості завдань приблизно від 90 до 250 висхідний порядок завдань знову приводить до скорочення часу обчислень. Починаючи з точки близько 250 завдань, тенденція переваги (висхідного або спадного порядку) виглядає більш стабільною. Висновки. При плануванні за допомогою евристики введення порядку завдань є дійсно суттєвим. Середня відносна різниця не перевищує 1,5 % для випадку від 2 до 1000 завдань, що мають до 17 періодів до обробки. Для отримання статистично достовірної переваги швидкості обчислення краще розглядати випадки з не менш як 250 завданнями. Зі збільшенням кількості завдань або кількості частин одного завдання перевага швидкості обчислення може стати нестабільною і з часом зникнути. Водночас висхідний порядок завдань може заощадити багато обчислювального часу у випадку складання розкладів принаймні декількох тисяч завдань, що мають лише кілька періодів до обробки. Після розв’язання тисяч таких випадків заощаджений час може нараховувати години.