Задача Джонсона з одним верстатом

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Задача Джонсона з одним верстатом — задача складання оптимального розкладу обробки деталей на єдиному верстаті, якщо -а деталь обробляється на ньому за час , а за секунд очікування до обробки цієї деталі сплачується штраф .

Таким чином, завдання полягає в пошуку такого переупорядковування деталей, що наступна величина (розмір штрафу) мінімальна. Якщо ми позначимо через перестановку деталей ( — номер першої оброблюваної деталі,  — другий, і т. д.), то розмір штрафу дорівнює:


Іноді це завдання називається завданням однопроцесорного обслуговування безлічі заявок.

Рішення завдання в деяких окремих випадках

[ред. | ред. код]

Перший приватний випадок: лінійні функції штрафу

[ред. | ред. код]

Навчимося вирішувати цю задачу в разі, коли всі лінійні, тобто мають вигляд:

, 

де  — невід'ємні числа. Зауважимо, що в цих лінійних функціях вільний член дорівнює нулю, тому що в іншому випадку до відповіді відразу можна додати цей вільний член, і вирішувати задачу з нульовим вільним членом. Зафіксуємо деяку розклад — перестановку . Зафіксуємо якийсь номер , і нехай перестановка дорівнює перестановці ,в якій обміняли -ий і -ий елементи. Подивимося на скільки при цьому змінився штраф:


легко зрозуміти, що зміни відбулися тільки з -им і -им складовими:

Зрозуміло, що якщо розклад є оптимальним, то будь-яке його зміна приводить до збільшення штрафу (або збереження колишнього значення), тому для оптимального плану можна записати умову:

Перетворюючи, отримуємо:


Таким чином, оптимальний розклад можна отримати, якщо відсортувати всі деталі по відношенню до в зворотному порядку.

Слід зазначити, що ми отримали цей алгоритм так званим перестановки прийомом: ми спробували обміняти місцями два сусідніх елемента розкладу, вирахували, наскільки при цьому змінився штраф, і звідси вивели алгоритм пошуку оптимального розкладу.

Другий окремий випадок: експоненціальні функції штрафу

[ред. | ред. код]

Нехай тепер функції штрафу мають вигляд:

, 

де всі числа невід'ємні, константа позитивна.

Тоді, застосовуючи аналогічним чином тут перестановочний прийом, легко отримати, що деталі треба сортувати в порядку убування величин:

Третій окремий випадок: однакові монотонні функції штрафу

[ред. | ред. код]

У цьому випадку вважається, що всі збігаються з деякою функцією , яка є зростаючою.

Зрозуміло, що в цьому випадку оптимально розташовувати деталі в порядку збільшення часу обробки .

Теорема Лівшиця-Кладова

[ред. | ред. код]

Теорема Лівшиця-Кладова встановлює, що перестановочний прийом застосовується лише для вищеописаних трьох окремих випадків, і тільки них, тобто: Лінейний випадок: , де  — невід'ємні константи, Експонентний випадок: , де і  — позитивні константи, Тотожний випадок: , де  — зростаюча функція. Ця теорема доведена в припущенні, що функції штрафу є досить гладкими (існують треті похідні). У всіх трьох випадках застосуємо перестановочний прийом, завдяки якому шукане оптимальний розклад може бути знайдено простий сортуванням, отже, за час .