Изменения

Перейти к: навигация, поиск

J2pij1Lmax

25 байт добавлено, 21:52, 21 июня 2012
Условие задачи
В нотации Грэхема задача носит название <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>n_i</tex> операций <tex>O_{ij}</tex> <tex>(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>max\{C_i - d_i | i = 1, \ldots, n\}</tex>
81
правка

Навигация