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

Задача Джонсона з одним верстатом — задача складання оптимального розкладу обробки $n$ деталей на єдиному верстаті, якщо $i$-а деталь обробляється на ньому за час $t_{i}$, а за $t$ секунд очікування до обробки цієї деталі сплачується штраф $f_{i}(t)$.

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

$F(\pi )=f_{\pi _{1}}(0)+f_{\pi _{2}}(t_{\pi _{1}})+f_{\pi _{3}}(t_{\pi _{1}}+t_{\pi _{2}})+\ldots +f_{\pi _{n}}\left(\sum _{i=1}^{n-1}t_{\pi _{i}}\right)\cdot$

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

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

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

Навчимося вирішувати цю задачу в разі, коли всі $f_{i}(t)$ лінійні, тобто мають вигляд:

$f_{i}(t)=c_{i}\cdot t$, 

де $c_{i}$ — невід'ємні числа. Зауважимо, що в цих лінійних функціях вільний член дорівнює нулю, тому що в іншому випадку до відповіді відразу можна додати цей вільний член, і вирішувати задачу з нульовим вільним членом. Зафіксуємо деяку розклад — перестановку $\pi$. Зафіксуємо якийсь номер $i=1\ldots n-1$, і нехай перестановка $\pi ^{\prime }$ дорівнює перестановці $\pi$,в якій обміняли $i$-ий і $i+1$-ий елементи. Подивимося на скільки при цьому змінився штраф:

$F(\pi ^{\prime })-F(\pi )=$

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

$=c_{\pi _{i}^{\prime }}\sum _{k=1}^{i-1}t_{\pi _{k}^{\prime }}+c_{\pi _{i+1}^{\prime }}\sum _{k=1}^{i}t_{\pi _{k}}-c_{\pi _{i}}\sum _{k=1}^{i-1}t_{\pi _{k}}-c_{\pi _{i+1}}\sum _{k=1}^{i}t_{\pi _{k}}=$

$=c_{\pi _{i+1}}\sum _{k=1}^{i-1}t_{\pi _{k}^{\prime }}+c_{\pi _{i}}\sum _{k=1}^{i}t_{\pi _{k}}-c_{\pi _{i}}\sum _{k=1}^{i-1}t_{\pi _{k}}-c_{\pi _{i+1}}\sum _{k=1}^{i}t_{\pi _{k}}=$

$=c_{\pi _{i}}t_{\pi _{i+1}}-c_{\pi _{i+1}}$

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

$\forall \ i=1\ldots n-1:c_{\pi _{i}}t_{\pi _{i+1}}-c_{\pi _{i+1}}t_{\pi _{i}}\geq \ 0.$

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

$\forall \ i=1\ldots n-1:{\frac {c_{\pi _{i}}}{t_{\pi _{i}}}}\geq \ {\frac {c_{\pi _{i+1}}}{t_{\pi _{i+1}}}}.$

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

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

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

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

$f_{i}(t)=c_{i}\cdot e^{\alpha \cdot t}$, 

де всі числа $c_{i}$ невід'ємні, константа $\alpha$ позитивна.

Тоді, застосовуючи аналогічним чином тут перестановочний прийом, легко отримати, що деталі треба сортувати в порядку убування величин: $v_{i}={\frac {1-e^{\alpha \cdot t_{i}}}{c_{i}}}.$

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

У цьому випадку вважається, що всі $f_{i}(t)$ збігаються з деякою функцією $\phi (t)$, яка є зростаючою.

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

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

Теорема Лівшиця-Кладова встановлює, що перестановочний прийом застосовується лише для вищеописаних трьох окремих випадків, і тільки них, тобто: Лінейний випадок: $f_{i}(t)=c_{i}\cdot t+d_{i}$, де $c_{i}$ — невід'ємні константи, Експонентний випадок: $f_{i}(t)=c_{i}\cdot e^{\alpha \cdot t}+d_{i}$, де $c_{i}$ і $\alpha$ — позитивні константи, Тотожний випадок: $f_{i}(t)=\phi (t)$, де $\phi$ — зростаюча функція. Ця теорема доведена в припущенні, що функції штрафу є досить гладкими (існують треті похідні). У всіх трьох випадках застосуємо перестановочний прийом, завдяки якому шукане оптимальний розклад може бути знайдено простий сортуванням, отже, за час $O(n\ logn)$.