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

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

Версия 21:44, 16 июня 2012

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

[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] в вершину входит не более одного ребра
  • prec [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]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]


Источники