Изменения
Нет описания правки
{{Утверждение
|statement=Следуя этому алгоритму, первый тайм-слот переполнится тогдаи расписания не существует тогда и только тогда, когда переполнилнилсяпереполнился нулевой тайм-слот.|proof=?<tex>\Rightarrow</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>m</tex>. Достраивать будем следующим образом. Каждая вершина в левой доле имеет степень <tex>m</tex>, так как каждая работа представлена в <tex>m</tex> тайм-слотах. В правой доле степень каждой вершины не больше <tex>m</tex>, так как в тайм-слоте не может быть больше, чем <tex>m</tex> работ. Значит, в левой доле не больше вершин, чем в правой.
Добавим в левую долю фиктивных вершин, чтобы количества вершин в левой и правой долях сравнялись. После чего просто будем добавлять ребра между вершинами, степень которых еще меньше <tex>m</tex>. Для покрытия этого графа паросочетаниями воспользуемся тем фактом, что регулярный двудольный граф степени <tex>d</tex> можно покрыть <tex>d</tex> паросочетаниями.
