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

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

[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]) Если работа [math]j[/math] выполняется на машине [math]i[/math], то [math]p_{i,j}[/math] является временем обработке работы [math]j[/math] на машине [math]i[/math]

Определение:

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

Определение:

Время окончания (Due date, [math]d_{j}[/math]) [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]. chains [math]{-}[/math] в каждую вершину входит не более одного ребра и выходит не более одного ребра intree [math]{-}[/math] из вершины выходит не более одного ребра outtree [math]{-}[/math] в вершину входит не более одного ребра prec [math]{-}[/math] произвольный ациклический граф зависимостей

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

Определение:

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

Определение:

[math] {-} [/math] (None) Цель - просто сделать.

Определение:

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

Определение:

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

Определение:

Опоздание (Tardiness, [math]T_{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]

Источники

• Handbook of scheduling: algorithms, models, and performance analysis, Joseph Y-T. Leung
• Scheduling Algorithms, Peter Brucker