Обозначения. Примеры. Динамическое программирование.

Для представления задач ТР используется обозначение α/β/γ.

2.1. Первое поле α = α1α2 описывает обслуживающую систему (вид и количество приборов).

Символ α1 описывает вид системы

Вид системы (α1{·,P,Q,R,O,F,J} где · - пустой символ)
Одностадийные системы(каждое требование может быть обслужено любым прибором)
1. · один прибop: p1j = pj, где pj - длительность обслуживания прибором требования j
2. P параллельные идентичныеприборы: plj =pj для всех приборов
3. Q параллельныеприборыразной производительности: plj = pj/vl, где vl – производительность прибора l
4. R параллельные различныеприборы: plj являются произвольными целыми неотрицательными числами
Многостадийные системы(plj являются произвольными целыми неотрицательными числами)
5. O open-shop: каждое требование должно быть обслужено каждым из приборов 1,..., m
6. F flow-shop: каждое требование должно быть обслужено каждым из приборов 1,..., m причем в порядке 1,..., m, т.е. до начала обслуживания требования приборомl+1 его обслуживание должно завершиться на прибореl, l = 1,... ,m-1.
7. J job-shop: требования в системе имеют заданные, не обязательно одинаковые маршруты прохождения приборов 1,..., mв которых приборы могут повторяться

Символ α2 служит для описания количестваприборов.

В случае α2=m имеется в виду, что количество приборов фиксировано и равно т.

В случае α2= · количество приборов - переменная величина, ее значение - элемент входных данных задачи.

Обозначение α1 = · применяется лишь в сочетании с α2 = 1.

2.2. Второе поле βописывает характеристики требований.

Предполагается, что β{β1,..., β5}, где βkопределены следующим образом:

Прерывания (β1{·,pmtn})
1. · прерывания обслуживания любого требования запрещены
2. pmtn прерывания разрешены
Длительности обслуживания (β2{·, pj = p, plj = p })
1. · длительности обслуживания требований pjлибо plj произвольны;
2. pl│ plj = p длительностиplили plj одинаковыи равны pдля всех требований и приборов
Директивные сроки (β3{·, dj = d })
1. · если заданы директивные сроки dj, то они являются произвольными
2. dj = d директивные сроки одинаковы и равны d
Моменты поступления(β4{·, rj })
1. · моменты поступления равны 0 для всех требований
2. rj Заданы произвольные моменты поступления rj
Отношения предшествования (β5{·, prec, tree, in-tree, out- tree, s-p, chain})
1. · на множестве требовании не заданы отношения предшествования
2. prec на множестве требований заданы отношения предшествования, которые представляются произвольным ацикличным ориентированным графом
3. tree, in-tree, out- tree, s-p, chain граф отношений предшествования является деревом, входящим деревом, выходящим деревом, последовательно-параллельным графом набором цепей

2.3. Третье поле γ описывает критерий задачи (поиск допустимого относительно директивных сроков либо минимизирующего некоторую целевую функцию расписания).