Opij1Sumwc — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Конспект создан)
 
(Скобки, см. также)
(не показаны 2 промежуточные версии этого же участника)
Строка 3: Строка 3:
 
|definition = Дано <tex>m</tex> одинаковых станков, которые работают параллельно и <tex>n</tex> работ, котороые необходимо выполнить в произвольном порядке на всех станках. Время выполнения каждой работы на любом станке одинаково и равно 1. Необходимо минимизировать взвешенную сумму времен завершения работ.  
 
|definition = Дано <tex>m</tex> одинаковых станков, которые работают параллельно и <tex>n</tex> работ, котороые необходимо выполнить в произвольном порядке на всех станках. Время выполнения каждой работы на любом станке одинаково и равно 1. Необходимо минимизировать взвешенную сумму времен завершения работ.  
 
}}
 
}}
 
 
==Алгоритм==
 
==Алгоритм==
  
Строка 9: Строка 8:
 
{{Утверждение
 
{{Утверждение
 
|statement=Оптимальный ответ для <tex>S = O \mid p_{ij}=1 \mid \sum w_i C_i</tex> равен оптимальному ответу к задаче <tex>S' = P \mid p_i=m, pmtn \mid \sum w_i C_i</tex>
 
|statement=Оптимальный ответ для <tex>S = O \mid p_{ij}=1 \mid \sum w_i C_i</tex> равен оптимальному ответу к задаче <tex>S' = P \mid p_i=m, pmtn \mid \sum w_i C_i</tex>
|proof=Для доказательства этого утверждения необходимо показать то, что из оптимальности <tex> S' </tex> следует оптимальность <tex> S </tex>, и способ построения допустимого расписания для <tex> S </tex> из расписания для <tex> S' </tex>:
+
|proof=Для доказательства этого утверждения необходимо показать то, что из оптимальности <tex> S' </tex> следует оптимальность <tex> S </tex>, и предоставить способ построения допустимого расписания для <tex> S </tex> из расписания для <tex> S' </tex>:
 
# Целевые функции задач совпадают, поэтому из оптимальности <tex> S' </tex> следует оптимальность <tex> S </tex>.
 
# Целевые функции задач совпадают, поэтому из оптимальности <tex> S' </tex> следует оптимальность <tex> S </tex>.
 
# Покажем, как получить из расписания <tex> S' </tex> допустимое расписание для <tex>S</tex> (в расписании для <tex>S'</tex> допустимость нарушает то, что на одном станке выполняется несколько блоков одной работы):
 
# Покажем, как получить из расписания <tex> S' </tex> допустимое расписание для <tex>S</tex> (в расписании для <tex>S'</tex> допустимость нарушает то, что на одном станке выполняется несколько блоков одной работы):
Строка 17: Строка 16:
 
## После данного преобразования мы не изменим значение целевой функции (так как мы переставляем только элементы работ, выполняющихся в один и тот же момент времени). Также расписание станет допустимым для <tex> S </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> 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> \left\lfloor \dfrac{n}{m} \right\rfloor </tex> блоков по <tex> m </tex> работ и, возможно, одного неполного блока из <tex> n \bmod m </tex> работ. Таким образом, аналогично задаче <tex> O \mid p_{ij}=1 \mid C_{max}</tex>, чтобы получить допустимое расписание, можно не строить раскраску графа, а просто циклически сдвигать последовательности работ внутри каждого блока.
  
 
===Время работы===
 
===Время работы===
Чтобы построить циклические сдвиги внутри одного блока требуется <tex> O(m^2) </tex> времени. Всего блоков <tex> O(\frac{n}{m}) </tex>.  
+
Чтобы построить циклические сдвиги внутри одного блока требуется <tex> \mathcal{O} \left( m^2 \right) </tex> времени. Всего блоков <tex> \mathcal{O} \left( \dfrac{n}{m} \right) </tex>.  
Значит, итоговая ассимптотика равна <tex> O(n \cdot m) </tex>.
+
Значит, итоговая ассимптотика равна <tex> \mathcal{O}(n \cdot m) </tex>.
  
 
==См. также.==
 
==См. также.==
 
* [[Методы решения задач теории расписаний]]
 
* [[Методы решения задач теории расписаний]]
 +
* [[1outtreesumwc|<tex> 1 \mid outtree \mid \sum w_i C_i </tex>]]
 +
* [[1ripi1sumwc|<tex> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex>]]
 +
* [[RSumCi|<tex> R \mid \mid \sum C_i </tex>]]
  
 
==Примечания==
 
==Примечания==
 
<references/>
 
<references/>
  
[[Категория: Дискретная математика и алгоритмы]]
+
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

Версия 04:18, 7 июня 2016

[math]O \mid p_{ij}=1 \mid \sum w_i C_i[/math]

Задача:
Дано [math]m[/math] одинаковых станков, которые работают параллельно и [math]n[/math] работ, котороые необходимо выполнить в произвольном порядке на всех станках. Время выполнения каждой работы на любом станке одинаково и равно 1. Необходимо минимизировать взвешенную сумму времен завершения работ.

Алгоритм

Описание алгоритма

Утверждение:
Оптимальный ответ для [math]S = O \mid p_{ij}=1 \mid \sum w_i C_i[/math] равен оптимальному ответу к задаче [math]S' = P \mid p_i=m, pmtn \mid \sum w_i C_i[/math]
[math]\triangleright[/math]

Для доказательства этого утверждения необходимо показать то, что из оптимальности [math] S' [/math] следует оптимальность [math] S [/math], и предоставить способ построения допустимого расписания для [math] S [/math] из расписания для [math] S' [/math]:

  1. Целевые функции задач совпадают, поэтому из оптимальности [math] S' [/math] следует оптимальность [math] S [/math].
  2. Покажем, как получить из расписания [math] S' [/math] допустимое расписание для [math]S[/math] (в расписании для [math]S'[/math] допустимость нарушает то, что на одном станке выполняется несколько блоков одной работы):
    1. Построим двудольный граф, в левую долю которого поместим работы, а в правую — возможные моменты времени. Из вершины, соответствующей работе [math] i [/math] будет идти ребро в вершину, соответствующую временному моменту [math] t[/math], если работа [math] i [/math] в расписании для [math] S' [/math] претендует на выполнение в момент времени [math]t[/math].
    2. Раскрасим ребра этого графа в [math]m[/math] цветов, из теории графов известно, что это можно сделать.
    3. Назначим выполнение единичного элемента работы [math]i[/math] в момент времени [math]t[/math] на станке [math]k[/math], если соответствующее ребро раскрашено в цвет [math]k[/math].
    4. После данного преобразования мы не изменим значение целевой функции (так как мы переставляем только элементы работ, выполняющихся в один и тот же момент времени). Также расписание станет допустимым для [math] S [/math], так как по определению реберной раскраски, не будет ни одной работы, два единичных блока которых выполняется на одном станке и во все моменты времени не окажется того, что на один станок назначено две работы.
[math]\triangleleft[/math]

Чтобы непосредственно решить эту задачу, воспользуемся теоремой о том, что для задачи [math] P \mid p_i=m, pmtn \mid \sum w_i C_i [/math] существует оптимальное расписание без прерываний[1]. Известно, что для того, чтобы получить оптимальное расписание для такой задачи без прерываний, надо помещать работы по очереди на станки [math]1 \dots m [/math] в порядке убывания весов. Длительности у всех работ совпадают, поэтому расписание будет состоять из [math] \left\lfloor \dfrac{n}{m} \right\rfloor [/math] блоков по [math] m [/math] работ и, возможно, одного неполного блока из [math] n \bmod m [/math] работ. Таким образом, аналогично задаче [math] O \mid p_{ij}=1 \mid C_{max}[/math], чтобы получить допустимое расписание, можно не строить раскраску графа, а просто циклически сдвигать последовательности работ внутри каждого блока.

Время работы

Чтобы построить циклические сдвиги внутри одного блока требуется [math] \mathcal{O} \left( m^2 \right) [/math] времени. Всего блоков [math] \mathcal{O} \left( \dfrac{n}{m} \right) [/math]. Значит, итоговая ассимптотика равна [math] \mathcal{O}(n \cdot m) [/math].

См. также.

Примечания

  1. P. Brucker. Scheduling Algorithms (2006), 5th edition, p. 121