MAXimal | |
добавлено: 11 Jun 2008 11:20 Содержание [скрыть] Задача Джонсона с одним станкомЭто задача составления оптимального расписания обработки Таким образом, задача заключается в поиске такого переупорядочения деталей, что следующая величина (размер штрафа) минимальна. Если мы обозначим через Иногда эта задача называется задачей однопроцессорного обслуживания множества заявок. Решение задачи в некоторых частных случаяхПервый частный случай: линейные функции штрафаНаучимся решать эту задачу в случае, когда все где Зафиксируем некоторое расписание — перестановку легко понять, что изменения произошли только с Понятно, что если расписание Преобразуя, получаем: Таким образом, оптимальное расписание можно получить, просто отсортировав все детали по отношению Следует отметить, что мы получили этот алгоритм так называемым перестановочным приёмом: мы попробовали обменять местами два соседних элемента расписания, вычислили, насколько при этом изменился штраф, и отсюда вывели алгоритм поиска оптимального расписания. Второй частный случай: экспоненциальные функции штрафаПусть теперь функции штрафа имеют вид: где все числа Тогда, применяя аналогичным образом здесь перестановочный приём, легко получить, что детали надо сортировать в порядке убывания величин: Третий частный случай: одинаковые монотонные функции штрафаВ этом случае считается, что все Понятно, что в этом случае оптимально располагать детали в порядке увеличения времени обработки Теорема Лившица-КладоваТеорема Лившица-Кладова устанавливает, что перестановочный приём применим только для вышеописанных трёх частных случаев, и только них, т.е.:
Эта теорема доказана в предположении, что функции штрафа являются достаточно гладкими (существуют третьи производные). Во всех трёх случаях применим перестановочный приём, благодаря которому искомое оптимальное расписание может быть найдено простой сортировкой, следовательно, за время
|