Изменения

Будем делить имеющиеся у нас работы на множества <tex> I_1, I_2</tex> так, чтобы для любого <tex>j \geqslant k</tex> <tex>I_1 = \{1,\ldots, j\}\setminus\{k\}</tex>, <tex>I_2 = \{j+1,\ldots, n\}</tex>. Тогда в оптимальном расписании все работы из <tex>I_1</tex> окажутся до <tex>k</tex>, а работы из <tex>I_2</tex> будут расположены после <tex>k</tex>. Для работ из <tex> I_1</tex> оптимальное время начала выполнения <tex>t_1 = 0</tex>, для работ из <tex>I_2</tex> оптимальное начало <tex>t_2 = p = \sum\limits_{i=1}^j p_i</tex>. Таким образом, для любой <tex>j</tex> задача разбивается на 2 две подзадачи. <br>