Изменения

{{в разработке}}

==Условие задачи==

Дано <tex>n</tex> работ <tex>i = 1,\ldots,n</tex> и две машины, обозначенные как <tex>A</tex> и <tex>B</tex>. <tex>i</tex>-тая работа состоит из <tex>n_i</tex> операций <tex>O_{ij} (j = 1,\ldots n_i)</tex>, которые должны быть выполнены последовательно и, при этом, если <tex>O_{ij} </tex>операция была совершена на машине <tex>A (B)</tex>, то операция <tex>O_{i,j-1}</tex> должна быть совершена на машине <tex>B (A)</tex>.

Задача заключается в том, что для данного каждой работе <tex>i</tex> дедлайна <tex>d_i \ge 0</tex> мы хотим найти достижимое расписание с наименьшими максимальным временем опоздания:

==Описание решения==

Таким образом, <tex>i</tex>-тая работа может характеризоваться двумя значениями: количество операций <tex>n_i</tex> и машина, на которой была совершена первая операция. Пусть <tex>r = \sum_{i=1}^n N_i</tex> {{---}} общее количество операций.