Планування робіт на одній машині

Це завдання полягає в пошуку оптимального розкладу для $n$ робіт на одній машині, якщо роботу $i$ можна виконати за час $t_i$, але за $t$ секунд очікування перед початком виконання роботи доводиться сплатити штраф $f_i(t)$.

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

$$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)$$

Коли підходить цей алгоритм?

• Чи всі роботи виконуються на одній машині, а оптимізуємо порядок задля мінімального сумарного штрафу за очікування? (якщо машин дві → Планування задач на двох машинах)
• Чи функція штрафу належить до випадків, де працює метод перестановок — лінійна, експоненційна або однакова монотонна (теорема Лівшиця–Кладова)?
• Чи можна знайти оптимум простим сортуванням за компаратором сусідніх робіт?

Розв'язки для окремих випадків

Лінійні функції штрафу

Спершу розв'яжемо задачу для випадку, коли всі функції штрафу $f_i(t)$ є лінійними, тобто мають вигляд $f_i(t) = c_i \cdot t$, де $c_i$ — невід'ємне число. Зауважимо, що ці функції не мають сталого члена. Інакше ми могли б додати всі сталі члени і розв'язати задачу без них.

Зафіксуймо деяку перестановку $\pi$ і візьмімо індекс $i = 1 \dots n-1$. Нехай перестановка $\pi'$ дорівнює перестановці $\pi$ із переставленими елементами $i$ та $i+1$. Подивімося, наскільки змінився штраф.

$$F(\pi') - F(\pi) =$$

Легко бачити, що зміни відбуваються лише в $i$-му та $(i+1)$-му доданках:

$$\begin{align} &= c_{\pi_i'} \cdot \sum_{k = 1}^{i-1} t_{\pi_k'} + c_{\pi_{i+1}'} \cdot \sum_{k = 1}^i t_{\pi_k'} - c_{\pi_i} \cdot \sum_{k = 1}^{i-1} t_{\pi_k} - c_{\pi_{i+1}} \cdot \sum_{k = 1}^i t_{\pi_k} \\ &= c_{\pi_{i+1}} \cdot \sum_{k = 1}^{i-1} t_{\pi_k'} + c_{\pi_i} \cdot \sum_{k = 1}^i t_{\pi_k'} - c_{\pi_i} \cdot \sum_{k = 1}^{i-1} t_{\pi_k} - c_{\pi_{i+1}} \cdot \sum_{k = 1}^i t_{\pi_k} \\ &= c_{\pi_i} \cdot t_{\pi_{i+1}} - c_{\pi_{i+1}} \cdot t_{\pi_i} \end{align}$$

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

$$c_{\pi_{i}} \cdot t_{\pi_{i+1}} - c_{\pi_{i+1}} \cdot t_{\pi_i} \ge 0 \quad \forall i = 1 \dots n-1$$

А після перегрупування отримуємо:

$$\frac{c_{\pi_i}}{t_{\pi_i}} \ge \frac{c_{\pi_{i+1}}}{t_{\pi_{i+1}}} \quad \forall i = 1 \dots n-1$$

Таким чином, ми отримуємо оптимальний розклад, просто відсортувавши роботи за дробом $\frac{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)$ рівні, і ця функція монотонно зростає.

Очевидно, що в цьому випадку оптимальною перестановкою є впорядкування робіт за неспадним часом виконання $t_i$.

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

Теорема Лівшиця-Кладова стверджує, що метод перестановок застосовний лише для трьох згаданих вище випадків, а саме:

• Лінійний випадок: $f_i(t) = c_i(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 \log n)$.