Методы решения задач теории расписаний — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(агрумент -> аргумент)
(Выделены задачи в конспекты, добавлены ссылки, разделы в конце конспекта)
Строка 5: Строка 5:
 
Примечание — если требуется полиномиальное время для решения задачи, требуется, чтобы сведение к другой задаче и трансформация расписания в допустимое также происходили за полиномиальное время.
 
Примечание — если требуется полиномиальное время для решения задачи, требуется, чтобы сведение к другой задаче и трансформация расписания в допустимое также происходили за полиномиальное время.
  
* Задачи класса Open Shop при условии <tex>p_{ij}=1</tex>, сводятся к задачам равной длительности на параллельных станках.
+
С помощью этого метода решаются:
* Задачи класса Flow Shop при условии <tex>p_{ij}=1</tex>, сводятся к задаче на одном станке.  
+
* Некоторые задачи класса Open Shop при условии <tex>p_{ij}=1</tex> сводятся к задачам равной длительности на параллельных станках.
 +
** <tex> O \mid p_{ij} = 1 \mid \sum w_i C_i </tex> ([[Opij1Sumwc|ссылка]])
 +
** <tex> O \mid p_{ij} = 1, r_i \mid C_{max} </tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 161</ref>
 +
* Некоторые задачи класса Flow Shop при условии <tex>p_{ij}=1</tex> сводятся к задаче на одном станке.  
 +
** <tex> F \mid p_{ij} = 1 \mid \sum w_i U_i </tex> ([[Fpij1sumwu|ссылка]])
 
* Часто в задачах, в которых допускаются прерывания, оптимальный ответ совпадает с соответствующими задачами без прерываний:
 
* Часто в задачах, в которых допускаются прерывания, оптимальный ответ совпадает с соответствующими задачами без прерываний:
** <tex> P \mid pmtn \mid \sum w_i C_i </tex>
+
** <tex> P \mid pmtn \mid \sum w_i C_i </tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 121</ref>
** <tex> F2 \mid pmtn \mid C_{max} </tex>
+
** <tex> F2 \mid pmtn \mid C_{max} </tex> ([[Flow_shop|ссылка]])
* Многие задачи проверки существования расписания сводятся к задаче поиска максимального потока:
+
* Некоторые задачи проверки существования расписания сводятся к задаче поиска максимального потока:
** <tex> Q \mid pmtn, r_i, d_i \mid - </tex>
+
** <tex> Q \mid pmtn, r_i\mid L_{max} </tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 129-133</ref>
 
+
** <tex> R \mid \mid \sum C_i </tex> ([[RSumCi|ссылка]])
=== Примеры ===
+
* <tex> 1 \mid intree \mid \sum w_i C_i </tex> ([[1outtreesumwc|ссылка]])
==== 1 | intree | Sum(w_i C_i) ====
 
Предположим, что мы уже умеем решать [[1outtreesumwc|задачу <tex> S' = 1 \mid outtree \mid \sum w_i C_i </tex>]]<ref>P. Brucker. Scheduling Algorithms (2006), 5th edition, p. 73 </ref>. Сведем нашу задачу <tex> S </tex> к ней следующим образом:
 
* Развернем все ребра, теперь если работа <tex> i </tex> зависела от работы <tex> j </tex>, работа <tex> j </tex> будет зависеть от <tex> i </tex>.
 
* Заменим все стоимости <tex> w_i </tex> на противоположные <tex> w'_i = - w_i</tex>.
 
Утверждается, что решив соответствующую задачу <tex> S' </tex> и развернув полученное расписание, мы получим ответ для текущей задачи.
 
# Полученное расписание будет допустимым, так как расписание для <tex> S' </tex> было допустимым, и в нем никакие две работы не пересекались и не прерывались. Развернув, мы не могли нарушить это свойство. Также из-за того, что мы развернули расписание, мы добились того, что все работы выполняются в правильном порядке (в расписании для <tex> S' </tex> из-за того, что все ребра были развернуты, порядок был нарушен для всех работ). Таким образом, получили что расписание — допустимое.
 
# Пусть с помощью задачи <tex> S' </tex> мы получили последовательность работ <tex> 1 \dots n </tex>. Распишем по определению значение целевой функции для <tex> S' </tex>:
 
#: <tex>\sum -w_i C_i = \sum \limits_{i=1}^n ( -w_i \sum \limits_{j=1}^i p_j ) = \\
 
\sum\limits_{i=1}^n ( w_i \sum\limits_{j=i+1}^n p_j ) - \sum\limits_{i=1}^n w_i \sum \limits_{i=1}^n p_i = \\
 
\sum\limits_{i=1}^n ( w_i \sum\limits_{j=i}^n p_j ) - \sum\limits_{i=1}^n w_i p_i - \sum\limits_{i=1}^n w_i \sum \limits_{i=1}^n p_i </tex>
 
#: Заметим, что первое слагаемое соответствует целевой функции <tex> \sum w_i C_i </tex> для последовательности <tex> n \dots 1 </tex>, а второе и третье слагаемые — константы, зависящие только от входных данных и не зависящие от перестановки работ. Таким образом, оптимальное значение для <tex> S' </tex> также минимизирует <tex> S </tex>, ч.т.д.
 
 
 
==== R || Sum(C_i) ====
 
В этой задаче дано <tex> n </tex> работ и <tex> m </tex> станков, причем для каждого станка длительность выполнения на нем <tex>i</tex>-й работы своя и равна <tex> p_{ij} </tex>.
 
 
 
Рассмотрим произвольное допустимое расписание для этой задачи. Рассмотрим какую-то станок <tex> j </tex>, пусть на нем выполняется <tex>n_j</tex> работ. Тогда вклад этого станка в целевую функцию (не теряя общности, пронумеруем работы на этом станке от <tex>1 </tex> до <tex>n_j</tex>) рассчитывается как:
 
 
 
<tex> \sum\limits_{i=1}^{n_j} (p_ij + \sum\limits_{q=1}^{i-1} p_qj) = n_j p_{1j} + (n_j - 1) p_{2j} + \dots + 2 p_{(n_j-1)j} + p_{n_jj} </tex>
 
 
 
Заметим, что в каждом допустимом расписании перед каждой работой окажется коэффициент <tex> k </tex>, означающий, что соответствующая работа выпллняется <tex> k </tex>-й с конца. Понятно, что в различных расписаниях <tex> k </tex> может принимать значения от <tex>1</tex> до <tex>n</tex>.
 
 
 
Сведем задачу к назначению каждой работы <tex> i </tex> позиции с конца <tex> k </tex> на станке <tex> j </tex> с помощью задачи [[Поток минимальной стоимости | mincost-maxflow]]. Поместим в левую долю графа работы, в правую долю — пары из станка и коэффициента и проведем соответствующие ребра пропускной способности <tex>1</tex> и стоимости <tex>k p_{ij}</tex>, соответствующие вкладу работы в целевую функцию, если она окажется в позиции <tex> k </tex> с конца на станке <tex> j </tex>. Проведем из стока в левую долю ребра стоимости <tex>0</tex> и пропускной способности <tex>1</tex>, из правой доли в сток — также ребра стоимости <tex> 0 </tex> и пропускной способности <tex>1</tex>. Найдем в этой сети максимальный поток минимальной стоимости. Утверждается, что если ребро <tex> i \to (j, k) </tex> насыщено потоком, то работа <tex> i </tex> в оптимальном расписании должна стоять на станке <tex> j </tex> в позиции <tex> k </tex> с конца.
 
 
 
# Целевые функции задачи mincost-maxflow и текущей задачи совпадают, так как у ребер между долями пропускная способность 1, а у дополнительных ребер из истока и в сток нулевая стоимость, и они не могут внести вклад в целевую функцию.
 
# Расписание, построенное по вышепредставленному способу действительно будет допустимым.
 
## Благодаря ограничениям на поток, входящий в левую долю, каждая работа будет назначена только один раз.
 
## Благодаря ограничениям на поток, выходящий из правой доли, на каждую позицию будет назначено не более одной работы.
 
## Докажем, что не возникает ситуации такой, что существует такая позиция <tex> l </tex>, что в этой позиции с конца стоит какая-то работа, а в позиции <tex> l - 1 </tex> с конца — нет (это противоречит определению <tex>l</tex>-й с конца работы). Такая ситуация означает, что ребро <tex> i \to (j, l) </tex> оказалось насышено потоком, а ребро <tex>i \to (j, l - 1) </tex> — не насыщено. Но стоимость ребра <tex> i \to (j, l - 1) </tex> меньше стоимости ребра <tex> i \to (j, l) </tex>, поэтому можем переместить поток с ребра <tex> i \to (j, l) </tex> на ребро <tex> i \to (j, l - 1) </tex>, не нарушив свойства потока и улучшив целевую функцию, что противоречит оптимальности ответа для mincost-maxflow. Следовательно, такой позиции не возникнет и расписание будет допустимым.
 
 
 
==== O | p_ij=1 | Sum(w_i C_i) ====
 
Докажем, что оптимальный ответ для <tex> S </tex> равен оптимальному ответу к задаче <tex>S' = P \mid p_i=m, pmtn \mid \sum w_i C_i </tex>, где прерывания позволено делать только в целые моменты времени.
 
# Целевые функции задач совпадают, поэтому из оптимальности <tex> S' </tex> следует оптимальность <tex> S </tex>.
 
# Покажем, как получить из расписания <tex> S' </tex> допустимое расписание для <tex>S</tex> (в расписании для <tex>S'</tex> допустимость нарушает то, что на одном станке выполняется несколько блоков одной работы):
 
## Построим двудольный граф, в левую долю которого поместим работы, а в правую — возможные моменты времени. Из вершины, соответствующей работе <tex> i </tex> будет идти ребро в вершину, соответствующую временному моменту <tex> t</tex>, если работа <tex> i </tex> в расписании для <tex> S' </tex> претендует на выполнение в момент времени <tex>t</tex>.
 
## Раскрасим ребра этого графа в <tex>m</tex> цветов, из теории графов известно, что это можно сделать.
 
## Назначим выполнение единичного элемента работы <tex>i</tex> в момент времени <tex>t</tex> на станке <tex>k</tex>, если соответствующее ребро раскрашено в цвет <tex>k</tex>.
 
## После данного преобразования мы не изменим значение целевой функции (так как мы переставляем только элементы работ, выполняющихся в один и тот же момент времени). Также расписание станет допустимым для <tex> S </tex>, так как по определению реберной раскраски, не будет ни одной работы, два единичных блока которых выполняется на одном станке и во все моменты времени не окажется того, что на один станок назначено две работы.
 
Чтобы непосредственно решить эту задачу, воспользуемся теоремой о том, что для задачи <tex> P \mid p_i=m, pmtn \mid \sum w_i C_i </tex> существует оптимальное расписание без прерываний<ref>P. Brucker. Scheduling Algorithms (2006), 5th edition, p. 121 </ref>. Известно, что для того, чтобы получить оптимальное расписание для такой задачи без прерываний, надо помещать работы по очереди на станки <tex>1 \dots m </tex> в порядке убывания весов. Длительности у всех работ совпадают, поэтому расписание будет состоять из <tex> \lfloor \frac{n}{m} \rfloor </tex> блоков по <tex> m </tex> работ и, возможно, одного неполного блока из <tex> n \mod m </tex> работ. Таким образом, аналогично задаче <tex> O \mid p_{ij}=1 \mid C_{max}</tex>, чтобы получить допустимое расписание, можно не строить раскраску графа, а просто циклически сдвигать последовательности работ внутри каждого блока, что позволяет достичь асимптотики <tex> O(m n) </tex>.
 
  
 
== Построение расписания по нижней оценке ==
 
== Построение расписания по нижней оценке ==
Строка 57: Строка 23:
  
 
С помощью этого метода решаются:
 
С помощью этого метода решаются:
* <tex> P \mid pmtn \mid C_{max}</tex>
+
* <tex> P \mid pmtn \mid C_{max}</tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 108</ref>
* <tex> R \mid pmtn \mid C_{max}</tex>
+
* <tex> R \mid pmtn \mid C_{max}</tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 137-139</ref>
* <tex> O \mid p_{ij}=1 \mid C_{max}</tex>
+
* <tex> O \mid p_{ij}=1 \mid C_{max}</tex> ([[Opij1Cmax|ссылка]])
* <tex> Q \mid pmtn \mid C_{max}</tex> ([[QpmtnCmax |ссылка]])
+
* <tex> Q \mid pmtn \mid C_{max}</tex> ([[QpmtnCmax|ссылка]])
  
=== Примеры ===
+
=== P | pmtn | C_max ===
==== P | pmtn | C_max ====
 
 
# В допустимом расписании выполнение всех работ не может завершиться раньше одной из них, поэтому <tex> T \ge p_i </tex>.
 
# В допустимом расписании выполнение всех работ не может завершиться раньше одной из них, поэтому <tex> T \ge p_i </tex>.
 
# Если все станки работали время <tex> T </tex>, на них могло выполниться не больше <tex> Tm </tex> работы, то есть <tex> \sum\limits_i p_i \le Tm </tex> и <tex> T \ge \frac1m \sum\limits_i p_i </tex>.
 
# Если все станки работали время <tex> T </tex>, на них могло выполниться не больше <tex> Tm </tex> работы, то есть <tex> \sum\limits_i p_i \le Tm </tex> и <tex> T \ge \frac1m \sum\limits_i p_i </tex>.
 
# Тогда <tex> T_{min} = \max {(\max\limits_i p_i, \frac1m \sum\limits_i p_i)} </tex>.
 
# Тогда <tex> T_{min} = \max {(\max\limits_i p_i, \frac1m \sum\limits_i p_i)} </tex>.
 
Построим расписание, подходящее под эту границу: будем по очереди заполнять машины работами в произвольном порядке, и если очередная работа не помещается на текущей машине полностью, перенесем ее выходящую за <tex> T_{min} </tex> часть на следующую машину. Благодаря первому ограничению никакая работа не будет выполняться одновременно на двух станках, а благодаря второму — не останется работы, которую мы не сможем выполнить.
 
Построим расписание, подходящее под эту границу: будем по очереди заполнять машины работами в произвольном порядке, и если очередная работа не помещается на текущей машине полностью, перенесем ее выходящую за <tex> T_{min} </tex> часть на следующую машину. Благодаря первому ограничению никакая работа не будет выполняться одновременно на двух станках, а благодаря второму — не останется работы, которую мы не сможем выполнить.
 
==== O | p_ij=1 | C_max ====
 
# В допустимом расписании на каждом станке надо обработать каждую работу, поэтому <tex> T \ge n </tex>.
 
# В допустимом расписании каждую работу нужно обработать на всех станках, причем ее нельзя обрабатывать на двух станках одновременно, поэтому <tex> T \ge m </tex>.
 
# Тогда <tex> T_{min} = \max {(m, n)} </tex>
 
Оптимальное расписание получается циклическими сдвигами последовательности <tex> 1 \dots n </tex> и выглядит следующим образом:
 
* Для <tex> n < m </tex>:
 
        '''0  1  2  ... n-1 n  n+1 ... m-1 m'''
 
  '''M_1'''    1  2  3  ... n-1 n  -  ... -  -
 
  '''M_2'''    -  1  2  ... n-2 n-1 n  ... -  -
 
  '''.'''      ... ... ... ... ... ... ... ... ... ...
 
  '''M_m-1'''  -  -  -  ... ... ... ... ... n  -
 
  '''M_m'''    -  -  -  ... ... ... ... ... n-1 n
 
* Для <tex> n \ge m </tex>:
 
        '''0    1    2  ... k  k+1 ... n-1 n'''
 
  '''M_1'''    1    2    3  ... k  k+1 ... n-1 n
 
  '''M_2'''    n    1    2  ... k-1 k  ... n-2 n-1
 
  '''.'''      ...  ...  ... ... ... ... ... ... ...
 
  '''.'''      ...  ...  ... ... ... ... ... ... ...
 
  '''M_m'''    n-m+2 n-m+3 ... ... ... ... ... n-m n-m+1
 
  
 
== Бинарный поиск по ответу ==
 
== Бинарный поиск по ответу ==
Строка 93: Строка 38:
  
 
Этим методом решаются:
 
Этим методом решаются:
* <tex> O \mid p_{ij} = 1 \mid \sum U_I </tex>
 
* <tex> O \mid p_{ij} = 1, r_i \mid C_{max} </tex>
 
 
* <tex> Q \mid pmtn, r_i \mid L_{max} </tex> ([[QpmtnriLmax |ссылка]])
 
* <tex> Q \mid pmtn, r_i \mid L_{max} </tex> ([[QpmtnriLmax |ссылка]])
 
=== Примеры ===
 
==== O | p_ij = 1| Sum(U_i) ====
 
Перенумеруем работы по неубыванию их дедлайнов, то есть <tex> d_1 \le d_2 \le \dots d_n </tex>.
 
{{Утверждение
 
|statement=
 
Если мы можем выполнить <tex> k </tex> каких-то работ, мы можем выполнить <tex> k </tex> последних работ.
 
|proof=
 
Действительно, если в допустимом расписании все периоды выполнения <tex> t_{iq} </tex> работы <tex> i </tex> заменить на периоды выполнения работы <tex> j > i </tex>, оно останется допустимым, так как <tex> t_{iq} \le d_i \le d_j </tex>.
 
}}
 
Таким образом, будем брать последние <tex> k </tex> работ и пытаться составить из них допустимое расписание (для этого известен полиномиальный алгоритм за <tex> O(mn) </tex><ref>P. Brucker. Scheduling Algorithms (2006), 5th edition, p. 163 </ref>). Получили решение за <tex> O(mn\log n ) </tex>.
 
  
 
== Жадное построение расписания ==
 
== Жадное построение расписания ==
Строка 118: Строка 50:
 
С помощью этого метода решаются:
 
С помощью этого метода решаются:
 
* <tex> 1 \mid prec \mid f_{max} </tex> ([[Правило Лаулера|''Lawler's algorithm]])
 
* <tex> 1 \mid prec \mid f_{max} </tex> ([[Правило Лаулера|''Lawler's algorithm]])
* <tex> 1 \mid outtree \mid \sum w_i C_i </tex>
+
* <tex> 1 \mid outtree \mid \sum w_i C_i </tex> ([[1outtreesumwc|ссылка]])
* <tex> 1 \mid p_i = 1 \mid \sum w_i U_i </tex> (''Earliest Due Date rule'')
+
* <tex> 1 \mid p_i = 1 \mid \sum w_i U_i </tex> ([[1pi1sumwu|''Earliest Due Date rule'']])
* <tex> 1 \mid \mid \sum U_i </tex>
+
* <tex> 1 \mid \mid \sum U_i </tex> ([[1sumu|ссылка]])
  
 
Обычно оптимальность жадного выбора доказывают двумя способами:  
 
Обычно оптимальность жадного выбора доказывают двумя способами:  
Строка 132: Строка 64:
  
 
=== Правильно ===
 
=== Правильно ===
Правильная стратегия (аргумент замены, ''exchange argument'') заключается в рассмотрении текущего решения <tex> S </tex> и оптимального решения <tex> O </tex>. Далее предлагается способ модификации <tex> O </tex> в <tex> O'</tex> так, что:
+
При доказательстве оптимательности применима стратегия '''аргумент замены''' (англ. ''exchange argument''). Стратегия заключается в рассмотрении текущего решения <tex> S </tex> и оптимального решения <tex> O </tex>. Далее предлагается способ модификации <tex> O </tex> в <tex> O'</tex> так, что:
 
# <tex> f(O') \le f(O) </tex>, то есть <tex> O' </tex> также оптимально.
 
# <tex> f(O') \le f(O) </tex>, то есть <tex> O' </tex> также оптимально.
 
# <tex> O' </tex> «более похоже» на <tex> S </tex>, чем на <tex> O </tex>.
 
# <tex> O' </tex> «более похоже» на <tex> S </tex>, чем на <tex> O </tex>.
Строка 139: Строка 71:
  
 
Отношение «более похоже» должно быть [[Отношение порядка | отношением частичного строгого порядка]]. Часто в качестве него можно выбрать отношение «длина наибольшего общего префикса решения <tex> A </tex> и <tex> S </tex> меньше наибольшего общего префикса решения <tex> B </tex> и <tex> S </tex>». Тогда если мы сможем увеличить длину наибольшего общего префикса для оптимального решения, не нарушив оптимальности, мы приблизимся к <tex> S </tex>. Можно выбирать и более сложные отношения, например, в доказательстве оптимальности алгоритма <tex> P \mid \mid \sum w_i C_i </tex> для решения задачи <tex> P \mid pmtn \mid \sum w_i C_i </tex> используется отношение «время последнего прерывания больше или количество прерываний меньше».
 
Отношение «более похоже» должно быть [[Отношение порядка | отношением частичного строгого порядка]]. Часто в качестве него можно выбрать отношение «длина наибольшего общего префикса решения <tex> A </tex> и <tex> S </tex> меньше наибольшего общего префикса решения <tex> B </tex> и <tex> S </tex>». Тогда если мы сможем увеличить длину наибольшего общего префикса для оптимального решения, не нарушив оптимальности, мы приблизимся к <tex> S </tex>. Можно выбирать и более сложные отношения, например, в доказательстве оптимальности алгоритма <tex> P \mid \mid \sum w_i C_i </tex> для решения задачи <tex> P \mid pmtn \mid \sum w_i C_i </tex> используется отношение «время последнего прерывания больше или количество прерываний меньше».
 +
 +
== См. также. ==
 +
* [[Правило Лаулера]]
 +
* [[Flow shop]]
 +
* [[Opi1sumu|<tex> O \mid p_{ij} = 1 \mid \sum U_i</tex>]]
  
 
== Примечания ==
 
== Примечания ==
 
<references/>
 
<references/>
 +
 +
==  Источники информации ==
 +
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer ISBN 978-3-540-69515-8
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

Версия 12:31, 6 июня 2016

Сведение к другой задаче

При сведении текущей задачи теории расписаний [math] S [/math] к какой-то другой [math] S' [/math](не обязательно задаче теории расписаний) необходимо доказать два пункта:

  1. Допустимость расписания, построенного с помощью задачи [math] S' [/math], или существование способа его трансформации в допустимое без нарушения оптимальности.
  2. Следствие того, что если мы оптимизируем [math] S' [/math], мы также оптимизируем ответ для [math] S [/math].

Примечание — если требуется полиномиальное время для решения задачи, требуется, чтобы сведение к другой задаче и трансформация расписания в допустимое также происходили за полиномиальное время.

С помощью этого метода решаются:

  • Некоторые задачи класса Open Shop при условии [math]p_{ij}=1[/math] сводятся к задачам равной длительности на параллельных станках.
    • [math] O \mid p_{ij} = 1 \mid \sum w_i C_i [/math] (ссылка)
    • [math] O \mid p_{ij} = 1, r_i \mid C_{max} [/math] [1]
  • Некоторые задачи класса Flow Shop при условии [math]p_{ij}=1[/math] сводятся к задаче на одном станке.
    • [math] F \mid p_{ij} = 1 \mid \sum w_i U_i [/math] (ссылка)
  • Часто в задачах, в которых допускаются прерывания, оптимальный ответ совпадает с соответствующими задачами без прерываний:
    • [math] P \mid pmtn \mid \sum w_i C_i [/math] [2]
    • [math] F2 \mid pmtn \mid C_{max} [/math] (ссылка)
  • Некоторые задачи проверки существования расписания сводятся к задаче поиска максимального потока:
    • [math] Q \mid pmtn, r_i\mid L_{max} [/math] [3]
    • [math] R \mid \mid \sum C_i [/math] (ссылка)
  • [math] 1 \mid intree \mid \sum w_i C_i [/math] (ссылка)

Построение расписания по нижней оценке

Этот метод обычно применим к задачам, в которых целевая функция — [math] C_{max}[/math]. Построим какой-то набор нижних ограничений на произвольное расписание для задачи [math] S [/math] и возьмем из них максимальное. Затем построим произвольное допустимое расписание, достигающее этой оценки.

С помощью этого метода решаются:

  • [math] P \mid pmtn \mid C_{max}[/math] [4]
  • [math] R \mid pmtn \mid C_{max}[/math] [5]
  • [math] O \mid p_{ij}=1 \mid C_{max}[/math] (ссылка)
  • [math] Q \mid pmtn \mid C_{max}[/math] (ссылка)

P | pmtn | C_max

  1. В допустимом расписании выполнение всех работ не может завершиться раньше одной из них, поэтому [math] T \ge p_i [/math].
  2. Если все станки работали время [math] T [/math], на них могло выполниться не больше [math] Tm [/math] работы, то есть [math] \sum\limits_i p_i \le Tm [/math] и [math] T \ge \frac1m \sum\limits_i p_i [/math].
  3. Тогда [math] T_{min} = \max {(\max\limits_i p_i, \frac1m \sum\limits_i p_i)} [/math].

Построим расписание, подходящее под эту границу: будем по очереди заполнять машины работами в произвольном порядке, и если очередная работа не помещается на текущей машине полностью, перенесем ее выходящую за [math] T_{min} [/math] часть на следующую машину. Благодаря первому ограничению никакая работа не будет выполняться одновременно на двух станках, а благодаря второму — не останется работы, которую мы не сможем выполнить.

Бинарный поиск по ответу

Этот способ часто подходит для задач, в которых надо минимизировать [math]C_{max} [/math] (если мы умеем решать соответствующую задачу существования расписания), реже для [math] \sum w_i U_i [/math]. Важно помнить, что если требуется полиномиальное по [math] n [/math] решение, оно не должно зависеть от логарифма ответа, но иногда ответ ограничен полиномом от [math]n[/math], и мы можем применить этот метод.

Этим методом решаются:

  • [math] Q \mid pmtn, r_i \mid L_{max} [/math] (ссылка)

Жадное построение расписания

Определение:
Жадный алгоритм — алгоритм, в котором локальные оптимизации решения достигают глобального оптимума.


Естественно, далеко не все оптимизационные задачи можно решать жадно — для этого сначала необходимо доказать оптимальность жадного выбора.

С помощью этого метода решаются:

Обычно оптимальность жадного выбора доказывают двумя способами:

Неправильно

Приведем пример часто распространенных неправильных действий при доказательстве оптимальности жадного алгоритма:

Пусть предложенным нами алгоритмом мы получили какое-то решение [math] S [/math]. Атомарными изменениями в этом решении [math] S [/math] будем получать другие допустимые решения [math] S' [/math] и докажем, что [math] f(S) \le f(S') [/math]. Тогда решение [math] S [/math] — оптимально.

Проблема в этих рассуждениях в том, что ими мы доказываем локальную оптимальность алгоритма в решении [math] S [/math]. Получение же глобального минимума может потребовать нескольких атомарных изменений в расписании, поэтому доказать оптимальность таким образом в общем случае невозможно. Как ближайшую аналогию, можно привести неправильное утверждение для произвольной функции [math] f(\bar x) [/math] — «если все частные производные [math] \frac{\partial f}{\partial x_1} \dots \frac{\partial f}{\partial x_n} [/math] неотрицательны, то в точке [math] \bar x [/math] наблюдается глобальный минимум».

Правильно

При доказательстве оптимательности применима стратегия аргумент замены (англ. exchange argument). Стратегия заключается в рассмотрении текущего решения [math] S [/math] и оптимального решения [math] O [/math]. Далее предлагается способ модификации [math] O [/math] в [math] O'[/math] так, что:

  1. [math] f(O') \le f(O) [/math], то есть [math] O' [/math] также оптимально.
  2. [math] O' [/math] «более похоже» на [math] S [/math], чем на [math] O [/math].

Если такой способ найден, получаем, что какой-то последовательностью модификаций [math] O \to O_t' \to \dots \to O_1' \to S [/math] получим [math] f(S) \le f(O_1') \le \dots \le f(O_t') \le f(O) [/math], из чего следует оптимальность [math] S [/math].

Отношение «более похоже» должно быть отношением частичного строгого порядка. Часто в качестве него можно выбрать отношение «длина наибольшего общего префикса решения [math] A [/math] и [math] S [/math] меньше наибольшего общего префикса решения [math] B [/math] и [math] S [/math]». Тогда если мы сможем увеличить длину наибольшего общего префикса для оптимального решения, не нарушив оптимальности, мы приблизимся к [math] S [/math]. Можно выбирать и более сложные отношения, например, в доказательстве оптимальности алгоритма [math] P \mid \mid \sum w_i C_i [/math] для решения задачи [math] P \mid pmtn \mid \sum w_i C_i [/math] используется отношение «время последнего прерывания больше или количество прерываний меньше».

См. также.

Примечания

  1. Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 161
  2. Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 121
  3. Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 129-133
  4. Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 108
  5. Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 137-139

Источники информации

  • Peter Brucker «Scheduling Algorithms», fifth edition, Springer ISBN 978-3-540-69515-8