Изменения

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

J2pij1Lmax

98 байт добавлено, 21:47, 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>d_i \ge 0</tex> мы хотим найти достижимое расписание с наименьшими максимальным временем опоздания:
<tex>max\{C_i - d_i | i = 1, \ldots, n\}</tex>  
==Описание решения==
Таким образом, <tex>i</tex>-тая работа может характеризоваться двумя значениями: количество операций <tex>n_i</tex> и машина, на которой была совершена первая операция. Пусть <tex>r = \sum_{i=1}^n N_i</tex> {{---}} общее количество операций.
81
правка

Навигация