MAXimal

добавлено: 11 Jun 2008 11:20
редактировано: 2 Dec 2010 10:29

Задача Джонсона с одним станком

Это задача составления оптимального расписания обработки $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_[...]$

Иногда эта задача называется задачей однопроцессорного обслуживания множества заявок.

Решение задачи в некоторых частных случаях

Первый частный случай: линейные функции штрафа

Научимся решать эту задачу в случае, когда все $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^\prime_i} \cdot \sum_{k=1}^{i-1} t_{\pi^[...]$
$= c_{\pi_{i+1}} \cdot \sum_{k=1}^{i-1} t_{\pi^\pr[...]$
$= c_{\pi_i} \cdot t_{\pi_{i+1}} - c_{\pi_{i+1}} \[...]$

Понятно, что если расписание $\pi$ является оптимальным, то любое его изменение приводит к увеличению штрафа (или сохранению прежнего значения), поэтому для оптимального плана можно записать условие:

$\forall i=1 \ldots n-1 ~~~:~~ c_{\pi_i} \cdot t_{[...]$

Преобразуя, получаем:

$\forall i=1 \ldots n-1 ~~~:~~ \frac{ c_{\pi_i} }{[...]$

Таким образом, оптимальное расписание можно получить, просто отсортировав все детали по отношению $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 \log n)$ .