24
правки
Изменения
Конспект создан
<tex dpi="200">O \mid p_{ij}=1 \mid \sum w_i C_i</tex>
{{Задача
|definition = Дано <tex>m</tex> одинаковых станков, которые работают параллельно и <tex>n</tex> работ, котороые необходимо выполнить в произвольном порядке на всех станках. Время выполнения каждой работы на любом станке одинаково и равно 1. Необходимо минимизировать взвешенную сумму времен завершения работ.
}}
==Алгоритм==
===Описание алгоритма===
{{Утверждение
|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>:
# Целевые функции задач совпадают, поэтому из оптимальности <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^2) </tex> времени. Всего блоков <tex> O(\frac{n}{m}) </tex>.
Значит, итоговая ассимптотика равна <tex> O(n \cdot m) </tex>.
==См. также.==
* [[Методы решения задач теории расписаний]]
==Примечания==
<references/>
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
{{Задача
|definition = Дано <tex>m</tex> одинаковых станков, которые работают параллельно и <tex>n</tex> работ, котороые необходимо выполнить в произвольном порядке на всех станках. Время выполнения каждой работы на любом станке одинаково и равно 1. Необходимо минимизировать взвешенную сумму времен завершения работ.
}}
==Алгоритм==
===Описание алгоритма===
{{Утверждение
|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>:
# Целевые функции задач совпадают, поэтому из оптимальности <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^2) </tex> времени. Всего блоков <tex> O(\frac{n}{m}) </tex>.
Значит, итоговая ассимптотика равна <tex> O(n \cdot m) </tex>.
==См. также.==
* [[Методы решения задач теории расписаний]]
==Примечания==
<references/>
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
