0.1.Основные понятия Теории расписаний

Machine Scheduling Номенклатура и классификация задач ТР Сложность задач и методы исследования

Номенклатура и классификация задач ТР

Тахонов Иван Иванович	Основные понятия теории расписаний

Machine Scheduling Номенклатура и классификация задач ТР Сложность задач и методы исследования

Для представления задач построения оптимальных расписаний используется номенклатура | | :

Ïîëå служит для описания обслуживающей системы.

Ïîëå описывает характеристики работ.

Ïîëå содержит информацию о целевой функции (критерии).

Тахонов Иван Иванович	Основные понятия теории расписаний

Machine Scheduling Номенклатура и классификация задач ТР Сложность задач и методы исследования

Ïîëå 1 2

Символ 1 P t; 1; P; Q; R; O; F; Ju. Указывает на вид системы. Одностадийные системы:

1 одномашинная система;

P идентичные парал. машины, pij pj äëÿ âñåõ i è j;

Q парал. машины с различными производительностями, pij pj{si, ãäå si ýòî скорость Mi;

R различные параллельные машины, pij произвольны. Многостадийные системы (Shops):

F Flow Shop, операции линейно упорядочены, маршруты работ одинаковы, каждая машина посещается ровно 1 раз;

J Job Shop, операции линейно упорядочены, маршруты могут различаться;

O Open Shop, операции не упорядочены, каждая машина посещается однократно (как правило).

Тахонов Иван Иванович	Основные понятия теории расписаний

Machine Scheduling Номенклатура и классификация задач ТР Сложность задач и методы исследования

Ïîëå 1 2

Символ 2 P N Y t u указывает на количество приборов.

m: число машин фиксировано и равно m.

пусто: число машин переменная величина, являющаяся элементом входных данных задачи.

Замечание 1

Алгоритм трудоемкости Opnmq для задачи Om| | полиномиален, а для задачи O| | экспоненциален.

Тахонов Иван Иванович	Основные понятия теории расписаний

Machine Scheduling Номенклатура и классификация задач ТР Сложность задач и методы исследования

Ïîëå 1 2 3 4 5 : : :

Прерывания (preemptions):

prmp прерывания разрешены;

не указано прерывания не допускаются. Длительности (processing times):

pj p, pij p, : : : длительности работ (операций) принимают особые значения (например, все равны p);

не указано длины работ (операций) произвольны. Директивные сроки (due dates):

dj d; : : : заданы мягкие дир.сроки, которые имеют особые значения (например, все d);

dj заданы жесткие дир.сроки;

не указано директивные сроки либо отсутствуют, либо произвольны (см. ).

Тахонов Иван Иванович	Основные понятия теории расписаний

Machine Scheduling Номенклатура и классификация задач ТР Сложность задач и методы исследования

Ïîëå 1 2 3 4 5 : : :

Времена поступления работ (release times):

rj заданы времена поступления работ;

rj r времена поступления заданы и имеют особые значения (например, все равны r);

не указано времена поступления не заданы (все =0). Ограничения предществования (precedence constraints):

prec заданы огр. предш. общего вида (DAG);

chain; chains; tree; intree; outtree; : : : заданы огр. предш. особого вида; не указано огр. предш. нет (граф пуст).

Тахонов Иван Иванович	Основные понятия теории расписаний

Machine Scheduling Номенклатура и классификация задач ТР Сложность задач и методы исследования

Ïîëå

Целевая функция как правило зависит от времен завершения работ и выражается через следующие величины:

Cj момент завершения обслуживания работы Jj;

Lj Cj dj временнoе смещение работы;

Uj sgnpLjq штрафная функция (единичный штраф), равная 1, если работа Jj является запаздывающей относительно директивного срока dj, и нулю иначе;

Tj maxt0; Lju запаздывание работы Jj.

Тахонов Иван Иванович	Основные понятия теории расписаний

Machine Scheduling Номенклатура и классификация задач ТР Сложность задач и методы исследования

Ïîëå

hmax

max

h

jp

C

макс. стоимость вып. работ;

j

t

jqu

Cmax

max

C

ju

длина расписания;

j

t

Lmax

max

t

L

ju

максимальное временное смещение;

j

Tmax

max

t

T

ju

максимальное запаздывание;

j

°°

hj hjpCjq сумм. стоимость выполнения работ;

°	j	°	°
	°
	Cj j	Cj (	wjCj j	wjCj) суммарное (взв.)
время завершения;
°Uj °Uj (°wjUj °wjUj) (взв.) число
	j		j

запаздывающих работ;

° ° ° °

Tj Tj ( wjTj wjTj) суммарное (взв.)

j	j
запаздывание.

Тахонов Иван Иванович	Основные понятия теории расписаний

Machine Scheduling Номенклатура и классификация задач ТР Сложность задач и методы исследования

Ïîëå

Для задач распознавания свойств в поле может находиться выражение X ¤ Y , ãäå

X некоторый критерий, а

Y пороговое значение этого критерия.

Задача состоит в ответе на вопрос, существует ли допустимое расписание со значением критерия X, не превышающим Y .

Например: O3||Cmax ¤ 4.

Существует ли расписание длины не более 4 в системе Open Shop с тремя машинами?

Тахонов Иван Иванович	Основные понятия теории расписаний

Machine Scheduling Номенклатура и классификация задач ТР Сложность задач и методы исследования

Представление расписаний: схема Гантта

J1

J6

J9

J2

J4

J7

J3

J5

J8

0

16

Некоторое расписание для системы P 3

J1	M1				M2									M3													M4									M1
J2					M1					M2						M1												M3																		M1						M3
	0				2				4							7				9						12								16										21								25				27

Расписание для системы J4 с двумя работами

M1	J1	J2	J4 J4		J4
M2	J2	J1		J2	J3
M3	J4	J3		J1	J1

04 7 8 9 10

Расписание для системы O3 прерываниями

Тахонов Иван Иванович	Основные понятия теории расписаний