81
правка
Изменения
→Условие задачи
В нотации Грэхема задача носит название <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>
Дано <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> мы хотим найти достижимое расписание с наименьшими максимальным временем опоздания:
