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

Анотація

Теорiя розкладiв, яка вивчає, зокрема, мiнiмiзацiю загального зваженого часу завершення, що належить до планування, органiзацiї та виконання комплексних або багатоетапних процесiв компонування, виробництва, будiвництва, диспетчеризацiї, обчислень тощо, володiє i точними, i евристичними пiдходами до обчислення розкладiв. Обчислювальний час пiдходу з точним розкладом непомiрно зростає, коли кiлькiсть завдань збiльшують вiд лише декiлькох одиниць (приблизно вiд 6 до 9, залежно також вiд того, як завдання розбитi на частини). Тому використовують низку евристик для того, щоб знайти наближений розклад й отримати його якомога швидше. Наближений розклад за евристиками не завжди виконується за точно мiнiмальний загальний зважений час завершення, але втрата зазвичай є невеликою. Коли кiлькiсть завдань становить порядок сотень, задачi планування стають нерозв'язними за будь-якими пiдходами до точних розкладiв, i тому евристики залишаються єдиним способом визначення розкладу. Розглядаючи задачу планування з перемиканнями зi зростанням значущостi наступних завдань однакового об'єму, iснує два шляхи подання моментiв вiдпуску завдань i вiдповiдних ваг прiоритетiв. З одного боку, моменти вiдпуску можуть бути поданi у порядку зростання; тодi вiдповiднi ваги прiоритетiв будуть множиною, взагалi кажучи, неспадних значень. З iншого моменти вiдпуску можуть бути поданi у порядку спадання; тодi вже вiдповiднi ваги прiоритетiв будуть множиною, загалом незростаючих значень. Оцiнивши середнiй час отримання наближеного розкладу за зростаючим i спадаючим порядками подання моментiв вiдпуску завдань, виявляється, що порядок завдань у визначенiй евристицi вельми значущий. Його значущiсть зростає за зростаючої кiлькостi завдань. Вплив порядку завдань у визначенiй евристицi також зростає зi зростанням кiлькостi частин завдання. Спадаючий порядок завдань має зростаючу перевагу при плануваннi близько 300 завдань i бiльше. Зокрема, перевага спадаючого порядку завдань при плануваннi 100000 завдань, кожне з яких роздiлене на двi частини, становить майже 42%. Отже, для мiнiмiзацiї загального зваженого часу завершення у задачi планування з перемиканнями зi зростанням значущостi наступних завдань однакового об'єму моменти вiдпуску завдань треба подавати у спадаючому порядку. Однак виграш порядку завдань у визначенiй евристицi при плануваннi меншої кiлькостi завдань (вiд декiлькох десяткiв до 100, 200, 300) залишається невизначеним внаслiдок суттєвих флуктуацiй значно меншого часу обчислень.