Изменения
→Описание алгоритма
Пусть при добавлении <tex>k+1</tex>-й работы произошло переполнение нулевого тайм-слота.
Рассмотрим алгоритм добавления в тайм-слоты: работа <tex>i</tex>добавляется в тайм-слоты <tex>[d_i - m + 1; d_i]</tex>, после чего из переполнившихся работы перебрасываются в более ранние. Временно разрешим хранить в тайм-слоте сколь угодно много работ: отменим перебрасывание. Посмотрим на то, что получилось. Так как работу нельзя выполнять одновременно на двух станках, то ни одну единицу работы отсрочить нельзя. Будем рассматривать тайм-слоты в порядке уменьшения времени. Если в очередном тайм-слоте <tex>t</tex> в данный момент больше, чем <tex>m</tex> работ, то остаток нужно перекинуть на какие-то более ранние тайм-слоты. Заметим, что выгоднее перекинуть на наиболее поздние тайм-слоты: более ранние тайм-слоты могут понадобиться для перекидываний с тайм-слотов, идущих раньше просматриваемого. .
Также заметим, что алгоритм перекидывания работ таков, что итоговое распределение количеств работ в соответствующих тайм-слотах не зависит от того, в каком порядке обрабатывались переполнившиеся тайм-слоты.
количеством паросочетаний.
Построим двудольный граф. В левой доле вершинам будут соответствоввать соответствовать работы, в правой {{---}} времена. Соответственно, в левой доле будет <tex>n</tex> вершин, в правой {{---}} <tex>d_{max}</tex>. Ребро между работой <tex>i</tex> и временем <tex>t</tex> будет, если работа <tex>i</tex> есть в тайм-слоте <tex>t</tex>.
Рассмотрим какое-то паросочетание <tex>M</tex> в этом графе. Оно соответствует корректному расписанию работ на одной машине: ни одна работа не выполняется два раза, и ни в один момент времени не выполняется более одной работы.
