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

Анотація

Розклад, що забезпечує строго мінімальне загальне зважене запізнювання, можна знайти за відповідною цілочисловою задачею лінійного програмування. Відкритим є питання про те, чи змінюється час обчислення точного розкладу, якщо дати запуску завдань вводяться у модель у зворотному порядку. Мета полягає у тому, щоб встановити, чи впливає на швидкість обчислення точного розв’язку порядок завдань у щільному прогресуючому одномашинному плануванні з перемиканнями без простою. Завдання можуть мати різні об’єми та різні ваги пріоритетів. Для пошуку розкладів з мінімальним загальним зваженим запізнюванням використовується модель булевого лінійного програмування. Для досягнення зазначеної мети проводиться обчислювальне дослідження з метою оцінки усередненого часу обчислення як для висхідного порядку, так і для спадного порядку дат запуску завдань. Далі відносна різниця між часами обчислень має бути оцінена й опрацьована. Порядок завдань впливає на швидкість обчислення точного розв’язку, але це навряд чи є прогнозованим. Причиною цього є те, що завдання можуть мати різні об’єми та різні ваги пріоритетів, що додатково “розмиває” відповідний порядок вводу завдань, залишаючи лише дати запуску завдань, котрі завжди подаються у цьому порядку. Виявлено, що планування розкладу 3-х або 4-х робіт виконується у середньому швидше за спадного порядку вводу завдань. Однак очікуване прискорення за спадним порядком вводу завдань не може бути оціненим з високою достовірністю. Цей результат спростовує можливість маніпулювати порядком завдань з метою більш ефективного отримання розкладів в одиночному випадку задачі планування розкладу або у декількох таких випадках. Тільки якщо задачі планування розкладів з 3-ма або 4-ма завданнями подібні до спадного порядку вводу завдань і подаються тисячі таких задач, то лише тоді використання такого порядку вводу завдань рекомендовано. Вводити завдання ефективно у такому стилі все ще можливо тоді, коли розкид різних об’ємів завдань та різних ваг пріоритетів не є сильним, що стає ближчим до випадку загального запізнювання за рівних об’ємів завдань і рівних ваг пріоритетів. Цей випадок є найбільш привабливим, де час обчислень за спадного порядку завдань може скорочуватися до 10 % і більше при плануванні розкладів від 2-х до 6-ти завдань, що мають у складі від двох до чотирьох або навіть п’яти частин кожне.