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

Шаблон:Вікіфікувати Задача Джонсона з одним верстатом — задача складання оптимального розкладу обробки $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})+\dots +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\dots 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$ є оптимальним, то будь-яке його зміна приводить до збільшення штрафу (або збереження колишнього значення), тому для оптимального плану можна записати умову:

$\mathrm{\forall }i=1\dots n-1:c_{{\pi }_i}{t}_{{\pi }_{i+1}}-c_{{\pi }_{i+1}}{t}_{{\pi }_i}\ge 0.$

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

$\mathrm{\forall }i=1\dots n-1:\frac{c_{{\pi }_i}}{t_{{\pi }_i}}\ge \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)$ збігаються з деякою функцією $\varphi (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)=\varphi (t)$, де $\varphi$ — зростаюча функція. Ця теорема доведена в припущенні, що функції штрафу є досить гладкими (існують треті похідні). У всіх трьох випадках застосуємо перестановочний прийом, завдяки якому шукане оптимальний розклад може бути знайдено простий сортуванням, отже, за час $O(nlogn)$. Шаблон:Ізольована стаття