РОЗДІЛ 2
ЕФЕКТИВНА СХЕМА ПОБУДОВИ ОПТИМАЛЬНИХ ЗА ШВИДКОДІЄЮ РОЗКЛАДІВ В ЗАДАЧАХ ПРО ПРИЗНАЧЕННЯ РОБІТ НА НЕІДЕНТИЧНІ МАШИНИ
4.3. 2.1. Особливості класу задач оптимального призначення
Основною ланкою, що поєднує задачі, які тут розглядаються, є квадратна матриця порядку т з невід'ємними цілими числами , що характеризують витрати на виконання роботи і на машині j. З вибором для кожної роботи машини, спроможної її виконати, пов'язана ефективність призначення т робіт на т машин, яка формально задається цільовим функціоналом.
Першою задачею, що піддається результативному дослідженню, виявилася задача про оптимальне призначення, в якій необхідно мінімізувати сумарні витрати розподілу робіт по машинам. В цілочисловій постановці, що стала хрестоматійною, задача про оптимальне призначення формулюється так:
,
при обмеженнях:
Звісно цілий ряд алгоритмів рішення, що заслуговують на увагу, часова складність яких оцінюється величиною не вище, ніж О((т4)) [2]. Серед них необхідно виділити алгоритм Кана-Мункреса, застосований для розв'язання задачі з додатковими обмеженнями. В [4] показано, що не викликає принципових труднощів адаптація алгоритму для побудови всіх оптимальних рішень, а в [8] викладено його модифікацію, що мінімізує цільову функцію задачі з урахуванням додаткових вимог у вигляді
де .
Причиною, що спонукала розробку модифікацій алгоритму Кана-Мункреса, є великий розкид значень в оптимальному рішенні задачі, викликаний розподілом величин на числовій осі. В численних практичних ситуаціях виявляється недостатнім обмежитися єдиним оптимальним розподілом робіт по машинах. Не менш важливою вимогою є відсутність в рішенні значень, що перевищують задану величину . В цьому випадку в результаті побудови всіх оптимальних призначень задачі стає можливим вибір рішень з підходящим розподілом компонент, що в ньому містяться.
Розглянемо одну з транспортних інтерпретацій задачі про призначення, що містить викладену вимогу до оптимального рішення.
Нехай два автопідприємства, розташовані в пунктах 1 і 2, виконують пасажирські перевезення між цими пунктами т автобусами. З розкладу їх руху в пунктах 1 і 2 звісно час відправлення й час прибуття кожного з 2т рейсів, а також тривалість рейсу, яку будемо вважати постійною величиною.
Необхідно мінімізувати сумарний час, що екіпажі проводять у нарядах, за умови, що всі екіпажі, які відправляються з пункту 1 в пункт 2 повинні повернутися в пункт 1. Ця ж умова поширюється і на всі екіпажі автобусів автопідприємства, розташованого у пункті 2.
В даному разі матриця визначається за допомогою двох таблиць і . Перша таблиця містить інформацію про час в наряді екіпажів у припущенні, що всі перевезення виконує у відповідності з розкладами рейсів автопідприємство пункту 1. Друга таблиця складена за умови, що виконанням усіх рейсів зайняті екіпажі пункту 2. Іншими словами, кожний елемент таблиці дорівнює часу в наряді екіпажу, що виконує рейси i і j з пункту 1 у пункт 2 і у зворотному напрямку з пункту 2 у пункт 1. Аналогічно, у матриці величина дорівнює часу в наряді екіпажу, що відправився у рейс і з пункту 2 у пункт 1 і повернувся рейсом j з пункту 1 у пункт 2.
Очевидно, що рішенням поставленої задачі є рішення задачі про призначення для матриці , в якій .
По належності елементів оптимального рішення до матриці чи визначається кількість автобусів автопідприємства пункту 1 і кількість автобусів автопідприємства пункту 2, що забезпечують згідно заданому розкладу їх прямування мінімальний сумарний час перебування екіпажів у наряді.
Дії всіх звісних алгоритмів рішення задачі про призначення завершуються одразу ж після побудови першого оптимального призначення, в якому розходження між найбільшим і найменшим значеннями його компонент з практичної точки зору можуть виявитися непридатно більшими. В наведеній змістовній постановці задачі отримані в оптимальному рішенні тривалості перебування екіпажів у наряді в загальному випадку потребують корекції.
4.4. 2.2. Постановки узагальнень задачі про призначення в термінах теорії розкладів і алгоритми побудови їх допустимих розв'язків
Поряд з розробкою модифікацій алгоритму Кана-Мункреса корекція одержаного результату може бути виконана в результаті рішення задач вибору в матриці значень, що оцінюються іншими критеріями. Такі задачі зручно вивчати в рамках теорії розкладів, представляючи допустиме рішення як перестановку рядків матриці і пов'язуючи з кожним рядком і на машину j. Рішення, що задає мінімум вибраному функціоналу, знаходиться на множині всіх перестановок рядків матриці .
Нехай в ? вибір роботи i для машини j оцінюється штрафом
Для перестановки ? визначимо сумарний штраф
.
Тоді задача про призначення міститься в побудові послідовності ?*, для якої
.(2.1)
Якщо з перестановкою ? пов'язати штраф
для знаходження
(2.2)
то, звертаючись до транспортної інтерпретації задачі про призначення, становиться очевидним, що задача (2.2) міститься в мінімізації найбільшої тривалості перебування екіпажів у наряді.
Узагальненням задачі (2.1) і (2.2) є задача побудови оптимального за швидкодією розкладу з п двохетапних робіт, виконуємих дворівневою системою машин, в якій перший рівень представлено єдиною машиною, а другий рівень складається з т паралельно діючих неідентичних машин.
Кожна робота і спочатку виконується на машині першого рівня протягом часу , а потім на паралельній машині j, , протягом часу , так що тривалості других етапів робіт задаються матрицею , де , якщо машина j не може виконати роботу і. В будь-який момент часу кожна машина зайнята виконанням лише однієї роботи. Початком розкладу є момент часу, коли всі п робіт готові до виконання на машині першого