Замінник нескінченності у точній мінімізації загального запізнювання у щільному прогресуючому 1-машинному плануванні рівноцінних завдань з перемиканнями без простою

Анотація

Розклад, що забезпечує строго мінімальне загальне запізнювання, можна знайти за відповідною цілочисловою задачею лінійного програмування з нескінченностями. У реальних обчисленнях нескінченність, котра показує, що відповідні стани є забороненими або неможливими, замінюється на достатньо велике додатне ціле. Відкритим є питання про те, чи така заміна може бути підібрана так, щоб час обчислень був би зменшений. Мета полягає у тому, щоб встановити, як збільшення замінника нескінченності у відповідній моделі впливає на час обчислення точних розкладів. Якщо вплив виявиться значним, то слід надати рекомендацію щодо вибору замінника нескінченності для зменшення часу обчислень. Наведено схему генерації екземплярів задачі планування завдань. Екземпляри задачі планування завдань генеруються так, що розклади, які можна отримати тривіально, без точної моделі, виключені. Запропоновано дев’ять варіантів замінника нескінченності. Приріст замінника нескінченності в моделі точної мінімізації загального запізнювання, зведеної до розв’язання цілочислової задачі лінійного програмування, що передбачає підхід методу гілок і меж, може мати поганий вплив на час обчислення точних розкладів. Принаймні більше значення замінника нескінченності не може створити оптимальний розклад швидше у щільному прогресуючому 1-машинному плануванні рівноцінних завдань з перемиканнями без простою. Приблизно найкращим значенням замінника нескінченності є максимум, взятий за усіма скінченними потрійно-індексованими вагами моделі і збільшений потім на 1. Вплив замінника нескінченності “max” є дуже значущим. Порівняно з випадком, коли нескінченність замінена на досить велике ціле, замінник нескінченності “max” заощаджує до 50 % часу обчислень. Це заощаджує години та навіть дні чи місяці, коли розплановується до 8 завдань за кількох рівних періодів до обробки протягом кількох тисяч циклів або довше. Тому настійно рекомендується завжди вибирати замінник нескінченності якомога меншим, щоб скоротити час обчислень.