Изменения

<tex dpi ="200">O \mid p_{ij} =Описание задачи1 \mid \sum U_i</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>t</tex> множество из не более, чем <tex>m</tex> различных чисел {{---}}

Каждую работу будем пытаться сделать как можно позже. Будет Будем рассматривать работы в порядке невозрастания дедлайнов. <tex>i</tex>-ю работу попытаемся добавить в тайм-слоты с номерами от <tex>d_i - m + 1</tex> по <tex>d_i</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>, то она, тем более, будет выполнена.}}-->

===Существование решения==={{УтверждениеТеорема

Рассмотрим алгоритм добавления в Введем понятие ''фронта'' расписания. ''Фронтом'' назовем вектор размеров тайм-слоты: работа <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>O(t)</tex> найдём переполнившийся тайм-слот и за <tex>kO(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>d_{max}</tex>. Ребро между работой <tex>i</tex> и временем <tex>t</tex> будет, если работа <tex>i</tex> есть в тайм-слоте <tex>tO(n^3m^4)</tex>.

Рассмотрим какое-то паросочетание ==См. также==* [[Opij1di|<tex>MO \mid p_{ij} = 1, d_i \mid - </tex> в этом графе. Оно соответствует корректному расписанию работ на одной машине: ни одна работа не выполняется два раза, и ни в один момент времени не выполняется более одной работы.]]

Тогда==Источники информации==* Peter Brucker «Scheduling Algorithms», если мы сможем построить множество мощности <tex>m</tex> такоеfifth edition, что каждое ребро находится хотя бы в одном из паросочетаний, то оно будет соответствовать тому, что каждая работа обработана на каждом станке, а значит, составлено корректное расписание для этих <tex>k</tex> работ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>.[[Категория: Теория расписаний]]