Классификация задач

Материал из Викиконспекты
Перейти к: навигация, поиск

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

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

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

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

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

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

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


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


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


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



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


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


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


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

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


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


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


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


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


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


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


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

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


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


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


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


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


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

Источники