Точна мінімізація загального зваженого часу завершення в задачі планування з перемиканнями зі зростанням значущості наступних завдань однакового об’єму

Анотація

Теорія розкладів є важливою галуззю прикладної математики, спрямованою на організацію багатоетапних процесів компонування, виробництва, будівництва, диспетчеризації, обчислень тощо. Одним з головних критеріїв є мінімізація загального зваженого часу завершення. Існує клас задач планування з перемиканнями, у яких виконання одного завдання може бути перервано на користь виконання іншого завдання. У цьому класі існує підклас задач, у якому значущість наступних завдань зростає. Такі задачі планування виникають у системах, чий розвиток стає більш складним разом зі зростаючими витратами для підтримки цього розвитку. Коли кількість завдань сягає кількох сотень, такі задачі можуть розв’язуватися за допомогою евристик. Але знаходження точного мінімального загального зваженого часу завершення є цілком можливим для випадків з кількома завданнями, хоча це і потребує значно довших обчислень. Однак, оскільки евристики можуть дати лише наближені розклади, точні розклади для короткострокових задач планування все ще представляють інтерес. Тому метою є з’ясувати, чи оптимальний розклад міг би бути знайдений швидше у рамках точної моделі. Встановлюється, що за числа завдань до шести, без випадковостей у формуванні задачі, за виключенням випадку з чотирма завданнями, слабка перевага порядку завдань зі спадаючими вагами існує лише у середньому. Зі зростанням кількості завдань перевага порядку завдань або зі спадаючими вагами, або зі зростаючими вагами стає більш чіткою. Коли ваги пріоритетів сформовані випадково, очікується, що саме порядок завдань зі спадаючими вагами буде швидшим.