По этой же причине не
Для нетреугольной матрицы S на рис. 7.10 при T = 10 находим ?26(10) = ?25(10) = 10. Обработка четвёртого столбца откладывается, т.к. не найдено значение ?22(10). По этой же причине не обрабатывается третий столбец. После обработки второго столбца находим ?22(10) = ?26(10) - t6 = 9.
Обработка первого столбца невозможна, т.к. ещё не найдено значение ?23(10). Продолжаем циклический обзор столбцов. После обработки четвёертого столбца получаем ?24(10) = ?22(10) - t2 = 6. Обработка третьего столбца даёт ?23(10) = min {?22(10) - t2, ?25(10) - t5} = 6. После обработки первого столбца находим ?21(10) = ?23(10) - t3 = 4.
Диаграммы выполнения работ при поздних сроках окончания, по графам на рис. 7.1 и 7.10, при T = 10 представлены на рис. 7.12 — (а) и (б), соответственно. (Стрелки, соответствующие дугам в графах, опущены в связи с их избыточностью.)
Рис. 7.12. Диаграммы выполнения работ при поздних сроках окончания: а — для графа на рис. 7.1,б — для графа на рис. 7.10
Пусть ?j — произвольное значение момента окончания выполнения j-й работы, j =1 , ... , m,
?1j
Меняя значения {?j}, j = 1 , ... ,m, но соблюдая при этом порядок следования работ, мы получим множество допустимых расписаний выполнения работ.
Нашей конечной целью является выбор таких расписаний, которые позволяют решить задачи 1 и 2.
Определение 7. Функцию
назовём плотностью загрузки, найденной для значений ?1 , ... , ?m.
Для заданных ?1 , ... , ?m значение функции F в каждый момент времени t совпадает с числом одновременно (параллельно) выполняющихся в этот момент работ.
Например, по диаграмме на 7.11, т.е. для ?1 = ?11, ?2 = ?12, ... , ?8 = ?18, функция F(2, 3, 3, 4, 7, 8, 6, 9, t) имеет вид, представленный на рис. 7.13а. Для допустимого расписания, определяемого набором значений ?1 = 2, ?2 = 4, ?3 = 3, ?4 = 4, ?5 = 8, ?6 = 9, ?7 = 7, ?8 = 10, функция F(2, 4, 3, 4, 8, 9, 7, 10, t) имеет вид, представленный на рис. 7.13б.
