ПОСТРОЕНИЕ МАКСИМАЛЬНО ВОЗМОЖНЫХ И ПРЕДЕЛЬНЫХ ПУТЕЙ

Воспользуемся простейшим алгоритмом Веллмана—Калаба, который можно реализовать непосредственно на рис. 7.1 графа. Предположим, что слои вершин уже построены.

Пусть, как и выше, U — множество дуг, образующих сеть, Ur — множество дуг сети, входящих в вершину /, U+ — множество дуг сети, выходящих из вершины /, L — длительность дуги (/, у), и t* — ожидаемый и предельный сроки наступления события /.

В этих обозначениях алгоритм Веллмана—Калаба имеет вид:

Результаты вычислений представлены на рис. 7.1. В прямоугольниках около номера работы указаны два числа: слева — справа — t*.

КЛАСС ЗАДАЧ ТЕОРИИ РАСПИСАНИЙ

Для задач теории расписаний с одним и двумя станками основным методом решения является метод динамического программирования. Данный метод предназначен для построения оптимального управления многоэтапными процессами, обладающими, прежде всего, свойством аддитивности функции цели, когда значение функции цели на п этапах процесса есть сумма ее значений на каждом из этапов.

Кроме того, динамическое программирование, во-первых, связано с пошаговым конструированием самого решения задачи и, во-вторых, с использованием при таком конструировании принципа оптимальности.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >