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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Описание алгоритма)
м (rollbackEdits.php mass rollback)
 
(не показано 26 промежуточных версий 6 участников)
Строка 1: Строка 1:
==Описание задачи==
+
<tex dpi = "200">O \mid p_{ij} = 1 \mid \sum U_i</tex>
Дано <tex>m</tex> одинаковых станков, которые работают параллельно и <tex>n</tex> работ, котороые необходимо выполнить
+
{{Задача
в произвольном порядке на всех станках. Время выполнения каждой работы на любом станке одинаково и равно одному.  
+
|definition=Дано <tex>m</tex> одинаковых станков, которые работают параллельно и <tex>n</tex> работ, котороые необходимо выполнить в произвольном порядке на всех станках. Время выполнения каждой работы на любом станке одинаково и равно одному. Для каждой работы известно время, до которого её необходимо выполнить. Необходимо успеть выполнить как можно больше работ. }}
Для каждой работы известно время, до которого её необходимо выполнить. Необходимо успеть выполнить как можно больше работ.  
+
==Алгоритм==
 
+
===Описание алгоритма===
==Описание алгоритма==
 
Отсортируем работы в порядке невозрастания дедлайнов.
 
 
 
{{Утверждение
 
|statement=Если в оптимальном расписании можно сделать <tex>k</tex> работ, то можно сделать первые <tex>k</tex> работ.
 
|proof=Пусть в оптимальном расписании были сделаны работы <tex>i_1, i_2, \ldots, i_k</tex>. Докажем, что существует
 
оптимальное расписание, в котором сделаны работы <tex>1, 2, \ldots, k</tex>. Пусть работы <tex>i_1, i_2, \ldots, i_k</tex>
 
тоже отсортированы в порядке неубывания дедлайна. Тогда <tex>d_{i1} \le d_1, d_{i2}\le d_2, \ldots, d_{ik}\le d_{k}</tex>.
 
Тогда, если заменить во всём расписании работу <tex>i_j</tex> на работу <tex>j</tex>, то она, тем более, будет выполнена.
 
}}
 
 
 
 
{{Определение
 
{{Определение
|definition=Обозначим за ''тайм-слот t'' множество из не более, чем <tex>m</tex> различных чисел {{---}}  
+
|definition=Обозначим за '''тайм-слот''' <tex>t</tex> множество из не более, чем <tex>m</tex> различных чисел {{---}}  
 
номера работ, которые мы хотим выполнить в момент времени <tex>t</tex>.
 
номера работ, которые мы хотим выполнить в момент времени <tex>t</tex>.
 
}}
 
}}
Строка 26: Строка 15:
 
<tex>m</tex> работ, и в него добавили <tex>m+1</tex>-ю).  
 
<tex>m</tex> работ, и в него добавили <tex>m+1</tex>-ю).  
 
Для переполнившегося тайм-слота найдём найдем самый правый левее него тайм-слот, который ещё не переполнился и перекинем работу,  
 
Для переполнившегося тайм-слота найдём найдем самый правый левее него тайм-слот, который ещё не переполнился и перекинем работу,  
которой там еще нет, в него. Так как в нем меньше элементов, то, по принципу Дирихле, это можно сделать.  
+
которой там еще нет, в него. Так как в нем меньше элементов, то по принципу Дирихле, это можно сделать.  
 +
 
 +
Сведем задачу построения распинания по построенным тайм-слотам к задаче о покрытии двудольного [[Основные_определения_теории_графов|графа]] минимальным
 +
количеством [[Паросочетания:_основные_определения,_теорема_о_максимальном_паросочетании_и_дополняющих_цепях|паросочетаний]].
 +
 
 +
Определим <tex>k</tex> как максимальное число работ, которые можно успеть выполнить.
 +
 
 +
Построим двудольный граф. В левой доле вершинам будут соответствовать работы, в правой {{---}} времена. Соответственно, в левой доле будет <tex>n</tex> вершин, в правой {{---}} <tex>d_{max}</tex>. Ребро между работой <tex>i</tex> и временем <tex>t</tex> будет, если работа <tex>i</tex> есть в тайм-слоте <tex>t</tex>.
 +
 
 +
Рассмотрим какое-то паросочетание <tex>M</tex> в этом графе. Оно соответствует корректному расписанию работ на одной машине: ни одна работа не выполняется два раза и ни в один момент времени не выполняется более одной работы.
 +
 
 +
Тогда, если мы сможем построить множество мощности <tex>m</tex> такое, что каждое ребро находится хотя бы в одном из паросочетаний, то оно будет соответствовать тому, что каждая работа обработана на каждом станке, а значит, составлено корректное расписание для этих <tex>k</tex> работ.
 +
 
 +
Достроим граф до регулярного степени <tex>m</tex>. Достраивать будем следующим образом. Каждая вершина в левой доле имеет степень <tex>m</tex>, так как каждая работа представлена в <tex>m</tex> тайм-слотах. В правой доле степень каждой вершины не больше <tex>m</tex>, так как в тайм-слоте не может быть больше, чем <tex>m</tex> работ. Значит, в левой доле не больше вершин, чем в правой.
 +
Добавим в левую долю фиктивных вершин, чтобы количества вершин в левой и правой долях сравнялись. После чего просто будем добавлять ребра между вершинами, степень которых еще меньше <tex>m</tex>. Для покрытия этого графа паросочетаниями воспользуемся тем фактом, что регулярный двудольный граф степени <tex>d</tex> можно покрыть <tex>d</tex> паросочетаниями.
 +
 
 +
При помощи построения паросочетаний было построено расписание для тех <tex>k</tex> работ, которые можно успеть сделать. Так как остальные работы уже нельзя успеть, расписание для них можно составить произвольное. Например, выполнять их по очереди после выполнения первых <tex>k</tex> работ.
 +
 
 +
<!--{{Теорема
 +
|statement=Если в оптимальном расписании можно сделать <tex>k</tex> работ, то можно сделать первые <tex>k</tex> работ.
 +
|proof=Пусть в оптимальном расписании были сделаны работы <tex>i_1, i_2, \ldots, i_k</tex>. Докажем, что существует
 +
оптимальное расписание, в котором сделаны работы <tex>1, 2, \ldots, k</tex>. Пусть работы <tex>i_1, i_2, \ldots, i_k</tex>
 +
тоже отсортированы в порядке неубывания дедлайна. Тогда <tex>d_{i1} \leqslant d_1, d_{i2}\leqslant d_2, \ldots, d_{ik}\leqslant d_{k}</tex>.
 +
Тогда, если заменить во всём расписании работу <tex>i_j</tex> на работу <tex>j</tex>, то она, тем более, будет выполнена.
 +
}}-->
  
{{Утверждение
+
===Существование решения===
 +
{{Теорема
 
|statement=Следуя этому алгоритму, расписания не существует тогда и только тогда, когда
 
|statement=Следуя этому алгоритму, расписания не существует тогда и только тогда, когда
 
переполнился нулевой тайм-слот.
 
переполнился нулевой тайм-слот.
 
|proof=
 
|proof=
 
<tex>\Rightarrow</tex>
 
<tex>\Rightarrow</tex>
 +
 
Расписания не существует, а значит, никакой алгоритм его не найдет.
 
Расписания не существует, а значит, никакой алгоритм его не найдет.
  
 
<tex>\Leftarrow</tex>
 
<tex>\Leftarrow</tex>
Пусть при добавлении <tex>k+1</tex>-й работы произошло переполнение нулевого тайм-слота.
 
  
Рассмотрим алгоритм добавления в тайм-слоты: работа <tex>i</tex>добавляется в тайм-слоты <tex>[d_i - m + 1; d_i]</tex>, после чего из переполнившихся работы перебрасываются в более ранние. Временно разрешим хранить в тайм-слоте сколь угодно много работ: отменим перебрасывание. Посмотрим на то, что получилось. Так как работу нельзя выполнять одновременно на двух станках, то ни одну единицу работы отсрочить нельзя.  Будем рассматривать тайм-слоты в порядке уменьшения времени. Если в очередном тайм-слоте <tex>t</tex> в данный момент больше, чем <tex>m</tex> работ, то остаток нужно перекинуть на какие-то более ранние тайм-слоты. Заметим, что выгоднее перекинуть на наиболее поздние тайм-слоты: более ранние тайм-слоты могут понадобиться для перекидываний с тайм-слотов, идущих раньше просматриваемого. .
+
Введем понятие ''фронта'' расписания. ''Фронтом'' назовем вектор размеров тайм-слотов. Заметим, что от того, в каком порядке происходят перебрасывания из переполнившихся тайм-слотов, итоговый фронт не зависит. Поэтому, если мы сначала положим все работы в тайм-слоты, игнорируя ограничение на их размер, а потом в каком-то порядке перекинем, итоговый фронт окажется тем же. В случае, если при построении тайм-слотов игнорировалось ограничение на их размер, ни одну единицу работы нельзя назначить позже.
  
Также заметим, что алгоритм перекидывания работ таков, что итоговое распределение количеств работ в соответствующих тайм-слотах не зависит от того, в каком порядке обрабатывались переполнившиеся тайм-слоты.  
+
Будем также рассматривать тайм-слоты без номеров работ: в каждом тайм-слоте просто лежит сколько-то единиц работ. От этого итоговый фронт также не изменится. Заметим, что если нельзя составить корректную в плане наполненности конфигурацию тайм-слотов при данном ослаблении, то нельзя это сделать и в случае существования номера у каждой единицы работы. Будем рассматривать тайм-слоты по убыванию времени с <tex>d_1</tex> до <tex>0</tex>. В каждый момент времени будем хранить сколько работ ''необходимо'' перекинуть на более ранние тайм-слоты. Изначально это число равно нулю.
  
При рассмотрении очередного переполнившегося тайм-слота мы необходимо должны куда-то перекинуть несколько работ из него. Так как перекидывание происходит в тайм-слот с наибольшим допустимым временем, то то, что неоходимо перекинуть что-то из нулевого, влечет то, что не существует расписания, в котором можно успеть выполнить все эти работы
+
Рассмотрим очередной тайм-слот. Пусть в нем занято <tex>h</tex> ячеек из <tex>m</tex>, а также есть еще <tex>a</tex> нераспределяемых позже единиц работы. Здесь возможны два случая:
 +
* <tex>h +  a > m</tex>. В этом случае, так как более <tex>m</tex> единиц работы сейчас выполнить нельзя, а также ничего нельзя назначить позже, то оказывается, что невыполняемых сейчас или позже работ стало <tex>h + a - m</tex>.
 +
* Если <tex>h + a \leqslant m</tex>. Здесь можно назначить все нераспределяемые позже работы на это время, и сбросить их счетчик.
 +
 
 +
Так как и этот, и изучаемый алгоритм получают в итоге одинаковый фронт, а в этом мы вышли из нулевого времени, а невыполненные единицы работы остались, то так как распределить их никак невозможно, то не существует расписания, в котором бы выполнились все работы.
 
}}
 
}}
  
Опираясь на это утверждение, можно найти максимальное количество работ, которое можно выполнить. Обозначим его за <tex>k</tex>.
+
===Оценка сложности алгоритма===
 +
Рассмотрим добавление очередной работы в тайм-слоты. За <tex>O(t)</tex> найдём переполнившийся тайм-слот и за <tex>O(m)</tex> перекинем из него элемент. Так как <tex>t=O(nm)</tex>, итоговая сложность этой части {{---}} <tex>O(n^2m)</tex>.
  
Сведем задачу построения распинания по построенным тайм-слотам к задаче о покрытии двудольного графа минимальным
+
Достроение графа до регулярного делается за <tex>O(E)</tex>, где <tex>E</tex> {{---}} количество ребер в нем. Количество ребер в регулярном двудольном графе <tex>E = Vd</tex>, где <tex>V</tex> {{---}} количество вершин в одной из долей, а <tex>d</tex> {{---}} степень. Количество вершин в правой доле {{---}} <tex>O(t) = O(nm)</tex>. Значит граф будет построен за <tex>O(nm^2)</tex>, так как степень каждой вершины {{---}} <tex>m</tex>.
количеством паросочетаний.
 
  
Построим двудольный граф. В левой доле вершинам будут соответствоввать работы, в правой {{---}} времена. Соответственно, в левой доле будет <tex>n</tex> вершин, в правой {{---}} <tex>d_{max}</tex>. Ребро между работой <tex>i</tex> и временем <tex>t</tex> будет, если работа <tex>i</tex> есть в тайм-слоте <tex>t</tex>.
+
Сложность последней фазы зависит от того, каким алгоритмом граф разбивается на паросочетания. Использовав, например, алгоритм Куна, можно добиться сложности <tex>O(m \cdot M) = O(m \cdot n^3m^3)</tex>. Итоговая сложность алгоритма {{---}} <tex>O(n^3m^4)</tex>.
  
Рассмотрим какое-то паросочетание <tex>M</tex> в этом графе. Оно соответствует корректному расписанию работ на одной машине: ни одна работа не выполняется два раза, и ни в один момент времени не выполняется более одной работы.
+
==См. также==
 +
* [[Opij1di|<tex>O \mid p_{ij} = 1, d_i \mid - </tex>]]
  
Тогда, если мы сможем построить множество мощности <tex>m</tex> такое, что каждое ребро находится хотя бы в одном из паросочетаний, то оно будет соответствовать тому, что каждая работа обработана на каждом станке, а значит, составлено корректное расписание для этих <tex>k</tex> работ.
+
==Источники информации==
 +
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer {{---}} с. 179 ISBN 978-3-540-69515-8
  
Достроим граф до регулярного степени <tex>m</tex>. Достраивать будем следующим образом. Каждая вершина в левой доле имеет степень <tex>m</tex>, так как каждая работа представлена в <tex>m</tex> тайм-слотах. В правой доле степень каждой вершины не больше <tex>m</tex>, так как в тайм-слоте не может быть больше, чем <tex>m</tex> работ. Значит, в левой доле не больше вершин, чем в правой.
+
[[Категория: Алгоритмы и структуры данных]]
Добавим в левую долю фиктивных вершин, чтобы количества вершин в левой и правой долях сравнялись. После чего просто будем добавлять ребра между вершинами, степень которых еще меньше <tex>m</tex>. Для покрытия этого графа паросочетаниями воспользуемся тем фактом, что регулярный двудольный граф степени <tex>d</tex> можно покрыть <tex>d</tex> паросочетаниями.
+
[[Категория: Теория расписаний]]
 
 
При помощи построения паросочетаний было построено расписание для тех <tex>k</tex> работ, которые можно успеть сделать. Так как остальные работы уже нельзя успеть, расписание для них можно составить произвольное. Например, выполнять их по очереди после выполнения первых <tex>k</tex> работ.
 
 
 
==Оценка сложности алгоритма==
 
Рассмотрим добавление очередной работы в тайм-слоты. За <tex>O(t)</tex> найдём переполнившийся тайм-слот и за <tex>O(m)</tex> перекинем из него элемент. Так как <tex>t=O(nm)</tex>, итоговая сложность этой части {{---}} <tex>O(n^2m)</tex>.
 
 
 
Достроение графа до регулярного делается за <tex>O(E)</tex>, где <tex>E</tex> {{---}} количество ребер в нем. Количество ребер в регулярном двудольном графе <tex>E = Vd</tex>, где <tex>V</tex> {{---}} количество вершин в одной из долей, а <tex>d</tex> {{---}} степень. Количество вершин в правой доле {{---}} <tex>O(t) = O(nm)</tex>. Значит, граф будет построен за <tex>O(nm^2)</tex>, так как степень каждой вершины {{---}} <tex>m</tex>.
 
 
 
Сложность последней фазы зависит от того, каким алгоритмом граф разбивается на паросочетания. Использовав, например, алгоритм Куна, можно добиться сложности <tex>O(m \cdot M) = O(m \cdot n^3m^3)</tex>. Итоговая сложность алгоритма {{---}} <tex>O(n^3m^4)</tex>.
 

Текущая версия на 19:13, 4 сентября 2022

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

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

Алгоритм

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

Определение:
Обозначим за тайм-слот [math]t[/math] множество из не более, чем [math]m[/math] различных чисел — номера работ, которые мы хотим выполнить в момент времени [math]t[/math].


Введем тайм-слот для каждого момента времени от [math]0[/math] до [math]d_n[/math]. Каждую работу будем пытаться сделать как можно позже. Будем рассматривать работы в порядке невозрастания дедлайнов. [math]i[/math]-ю работу попытаемся добавить в тайм-слоты с номерами от [math]d_i - m + 1[/math] по [math]d_i[/math]. После добавления некоторые тайм-слоты могли переполниться (тайм-слот переполнился, если в нём уже находилось [math]m[/math] работ, и в него добавили [math]m+1[/math]-ю). Для переполнившегося тайм-слота найдём найдем самый правый левее него тайм-слот, который ещё не переполнился и перекинем работу, которой там еще нет, в него. Так как в нем меньше элементов, то по принципу Дирихле, это можно сделать.

Сведем задачу построения распинания по построенным тайм-слотам к задаче о покрытии двудольного графа минимальным количеством паросочетаний.

Определим [math]k[/math] как максимальное число работ, которые можно успеть выполнить.

Построим двудольный граф. В левой доле вершинам будут соответствовать работы, в правой — времена. Соответственно, в левой доле будет [math]n[/math] вершин, в правой — [math]d_{max}[/math]. Ребро между работой [math]i[/math] и временем [math]t[/math] будет, если работа [math]i[/math] есть в тайм-слоте [math]t[/math].

Рассмотрим какое-то паросочетание [math]M[/math] в этом графе. Оно соответствует корректному расписанию работ на одной машине: ни одна работа не выполняется два раза и ни в один момент времени не выполняется более одной работы.

Тогда, если мы сможем построить множество мощности [math]m[/math] такое, что каждое ребро находится хотя бы в одном из паросочетаний, то оно будет соответствовать тому, что каждая работа обработана на каждом станке, а значит, составлено корректное расписание для этих [math]k[/math] работ.

Достроим граф до регулярного степени [math]m[/math]. Достраивать будем следующим образом. Каждая вершина в левой доле имеет степень [math]m[/math], так как каждая работа представлена в [math]m[/math] тайм-слотах. В правой доле степень каждой вершины не больше [math]m[/math], так как в тайм-слоте не может быть больше, чем [math]m[/math] работ. Значит, в левой доле не больше вершин, чем в правой. Добавим в левую долю фиктивных вершин, чтобы количества вершин в левой и правой долях сравнялись. После чего просто будем добавлять ребра между вершинами, степень которых еще меньше [math]m[/math]. Для покрытия этого графа паросочетаниями воспользуемся тем фактом, что регулярный двудольный граф степени [math]d[/math] можно покрыть [math]d[/math] паросочетаниями.

При помощи построения паросочетаний было построено расписание для тех [math]k[/math] работ, которые можно успеть сделать. Так как остальные работы уже нельзя успеть, расписание для них можно составить произвольное. Например, выполнять их по очереди после выполнения первых [math]k[/math] работ.


Существование решения

Теорема:
Следуя этому алгоритму, расписания не существует тогда и только тогда, когда переполнился нулевой тайм-слот.
Доказательство:
[math]\triangleright[/math]

[math]\Rightarrow[/math]

Расписания не существует, а значит, никакой алгоритм его не найдет.

[math]\Leftarrow[/math]

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

Будем также рассматривать тайм-слоты без номеров работ: в каждом тайм-слоте просто лежит сколько-то единиц работ. От этого итоговый фронт также не изменится. Заметим, что если нельзя составить корректную в плане наполненности конфигурацию тайм-слотов при данном ослаблении, то нельзя это сделать и в случае существования номера у каждой единицы работы. Будем рассматривать тайм-слоты по убыванию времени с [math]d_1[/math] до [math]0[/math]. В каждый момент времени будем хранить сколько работ необходимо перекинуть на более ранние тайм-слоты. Изначально это число равно нулю.

Рассмотрим очередной тайм-слот. Пусть в нем занято [math]h[/math] ячеек из [math]m[/math], а также есть еще [math]a[/math] нераспределяемых позже единиц работы. Здесь возможны два случая:

  • [math]h + a \gt m[/math]. В этом случае, так как более [math]m[/math] единиц работы сейчас выполнить нельзя, а также ничего нельзя назначить позже, то оказывается, что невыполняемых сейчас или позже работ стало [math]h + a - m[/math].
  • Если [math]h + a \leqslant m[/math]. Здесь можно назначить все нераспределяемые позже работы на это время, и сбросить их счетчик.
Так как и этот, и изучаемый алгоритм получают в итоге одинаковый фронт, а в этом мы вышли из нулевого времени, а невыполненные единицы работы остались, то так как распределить их никак невозможно, то не существует расписания, в котором бы выполнились все работы.
[math]\triangleleft[/math]

Оценка сложности алгоритма

Рассмотрим добавление очередной работы в тайм-слоты. За [math]O(t)[/math] найдём переполнившийся тайм-слот и за [math]O(m)[/math] перекинем из него элемент. Так как [math]t=O(nm)[/math], итоговая сложность этой части — [math]O(n^2m)[/math].

Достроение графа до регулярного делается за [math]O(E)[/math], где [math]E[/math] — количество ребер в нем. Количество ребер в регулярном двудольном графе [math]E = Vd[/math], где [math]V[/math] — количество вершин в одной из долей, а [math]d[/math] — степень. Количество вершин в правой доле — [math]O(t) = O(nm)[/math]. Значит граф будет построен за [math]O(nm^2)[/math], так как степень каждой вершины — [math]m[/math].

Сложность последней фазы зависит от того, каким алгоритмом граф разбивается на паросочетания. Использовав, например, алгоритм Куна, можно добиться сложности [math]O(m \cdot M) = O(m \cdot n^3m^3)[/math]. Итоговая сложность алгоритма — [math]O(n^3m^4)[/math].

См. также

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

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