Классификация задач — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Критерий оптимизации)
(Характеристики работ)
Строка 65: Строка 65:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Зависимость между работами''' (англ. ''Precedence Contraints'', ''<tex>prec</tex>''). Работа может начаться только после выполнения некоторых других работ. Может быть представлено в виде ориентированного графа. При этом каждой вершине соответствует работа и работа <tex>i</tex> выполняется перед работой <tex>j</tex>, если есть ребро из вершины <tex>i</tex> в <tex>j</tex>. Тогда <tex>prec</tex> {{---}} произвольный ациклический граф зависимостей. Будем называть граф:
+
'''Зависимость между работами''' (англ. ''Precedence Contraints'', ''<tex>prec</tex>''). Работа может начаться только после выполнения некоторых других работ. Может быть представлено в виде ориентированного графа. При этом каждой вершине соответствует работа и работа <tex>i</tex> выполняется перед работой <tex>j</tex>, если есть ребро из вершины <tex>i</tex> в <tex>j</tex>. Тогда <tex>prec</tex> {{---}} произвольный ациклический граф зависимостей. Будем называть граф <tex>chains</tex> {{---}} если в каждую вершину входит не более одного ребра и выходит не более одного ребра, <tex>intree</tex> {{---}} если из каждой вершины выходит не более одного ребра, <tex>outtree</tex> {{---}} если в каждую вершину входит не более одного ребра.
*<tex>chains</tex> {{---}} если в каждую вершину входит не более одного ребра и выходит не более одного ребра;
 
*<tex>intree</tex> {{---}} если из каждой вершины выходит не более одного ребра;
 
*<tex>outtree</tex> {{---}} если в каждую вершину входит не более одного ребра.
 
 
}}
 
}}
  

Версия 21:35, 8 июня 2015

Нотация Грэхема

[math] \alpha \mid \beta \mid \gamma [/math]

Поле [math] \alpha [/math] описывает тип обработки. Задается одним значением.

Поле [math] \beta [/math] описывает характеристики работ. Задает параметры работ, и то, какими свойствами должно обладает расписание.

Поле [math] \gamma[/math] описывает критерий оптимизации. Содержит функцию, которую нужно оптимизировать.

Типы обработки

Определение:
Одна машина (англ. Single machine, [math]1[/math]). В системе находится одна машина.


Определение:
Параллельные одинаковые машины (англ. Parallel and Identical Machines, [math]P_{m}[/math]). В системе находится [math]m[/math] одинаковых машин, работающих параллельно.


Определение:
Параллельные однородные машины (англ. Uniform Machines, [math]Q_{m}[/math]). В системе находится [math]m[/math] машин, работающих параллельно. У машин разные скорости выполнения работ.


Определение:
Параллельные несвязанные машины (англ. Unrelated Machines, [math]R_{m}[/math]). В системе находится [math]m[/math] машин, работающих параллельно. У машин разные скорости выполнения разных работ.



Определение:
Job shop ([math]J_{m}[/math]). В системе находится [math]m[/math] машин, работающих параллельно. У каждой работы свой упорядоченный список машин, на которых они должны быть выполнены.


Определение:
Flow shop ([math]F_{m}[/math]). В системе находится [math]m[/math] машин, работающих параллельно. Машины упорядочены. Работы должны выполняться сначала на первой машине, потом на второй и так далее до последней.


Определение:
Open shop ([math]O_{m}[/math]). В системе находится [math]m[/math] машин, работающих параллельно. Каждая работа должна быть выполнена один раз на каждой машин. Порядок не важен


Характеристики работ

Определение:
Время работы (англ. Processing time, [math]p_{i,j}[/math]). Если работа [math]j[/math] выполняется на машине [math]i[/math], то [math]p_{i,j}[/math] является временем обработке работы [math]j[/math] на машине [math]i[/math]


Определение:
Время появления (англ. Release date, [math]r_{j}[/math]) является временем появления в системе работы [math]j[/math], минимальное время в которое можно начать обработку работы [math]j[/math]


Определение:
Время окончания (англ. Due date, [math]d_{j}[/math]) является временем до которого ожидается выполнения работы [math]j[/math]. Если работа [math]j[/math] была выполнена после [math]d_{j}[/math], то налагается штраф


Определение:
Дедлайн (англ. Deadline, [math]d_{j}[/math]) — тоже самое что и время окончания, но после дедлайна выполнять работу нельзя.


Определение:
Вес (англ. Weight, [math]w_{j}[/math]) — величина, отражающая значение работы [math]j[/math].


Определение:
Прерывание (англ. Preemption, [math]pmtn[/math]). Работа может быть прервана и продолжена позже.


Определение:
Зависимость между работами (англ. Precedence Contraints, [math]prec[/math]). Работа может начаться только после выполнения некоторых других работ. Может быть представлено в виде ориентированного графа. При этом каждой вершине соответствует работа и работа [math]i[/math] выполняется перед работой [math]j[/math], если есть ребро из вершины [math]i[/math] в [math]j[/math]. Тогда [math]prec[/math] — произвольный ациклический граф зависимостей. Будем называть граф [math]chains[/math] — если в каждую вершину входит не более одного ребра и выходит не более одного ребра, [math]intree[/math] — если из каждой вершины выходит не более одного ребра, [math]outtree[/math] — если в каждую вершину входит не более одного ребра.


Критерий оптимизации

Определение:
Цель оптимизации — минимизировать тот или иной критерий.


Определение:
[math] {-} [/math] (англ. None). Цель — просто сделать.


Определение:
Время окончания работы (англ. Completion time, [math]C_{j}[/math]) — время окончания обработки работы [math]j[/math].


Определение:
Опоздание (англ. Lateness, [math]L_{j}[/math]). [math]L_{j} = C_{j} - d_{j}[/math].


Определение:
Медлительность (англ. Tardiness, [math]T_{j}[/math]). [math]T_{j} = \max(L_{i}, 0)[/math].


Определение:
Штраф (англ. Unit penalty, [math]U_{j}[/math]). Если [math]C_{j} \gt d_{j}[/math], то [math]U_{j} = 1[/math], иначе [math]U_{j} = 0[/math].


См. также

Источники информации