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

2013-05-27T20:48:15Z

109.205.252.162: /* Характеристики работ */

==Нотация Грэхема==
<tex> \alpha </tex> | <tex> \beta </tex> | <tex> \gamma </tex>

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

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

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

==Типы обработки==
{{Определение
|definition =
'''Одна машина''' (Single machine, '''1''') В системе находится одна машина.}}

{{Определение
|definition =
'''Параллельные одинаковые машины''' (Parallel and Identical Machines, '''<tex>P_{m}</tex>''') В системе находится m одинаковых машин, работающих параллельно.}}

{{Определение
|definition =
'''Параллельные однородные машины''' (Uniform Machines, '''<tex>Q_{m}</tex>''') В системе находится m машин, работающих параллельно. У машин разные скорости выполнения работ.}}

{{Определение
|definition =
'''Параллельные несвязанные машины''' (Unrelated Machines, '''<tex>R_{m}</tex>''') В системе находится m машин, работающих параллельно. У машин разные скорости выполнения разных работ.}}

{{Определение
|definition =
'''Job shop''' ('''<tex>J_{m}</tex>''') В системе находится m машин, работающих параллельно. У каждой работы свой упорядоченный список машин, на которых они должны быть выполнены.}}

{{Определение
|definition =
'''Flow shop''' ('''<tex>F_{m}</tex>''') В системе находится m машин, работающих параллельно. Машины упорядочены. Работы должны выполняться сначала на первой машине, потом на второй и т.д. до последней.}}

{{Определение
|definition =
'''Open shop''' ('''<tex>O_{m}</tex>''') В системе находится m машин, работающих параллельно. Каждая работа должна быть выполнена один раз на каждой машин. Порядок не важен}}

==Характеристики работ==
{{Определение
|definition =
'''Время работы''' (Processing time, <tex>p_{i,j}</tex>) Если работа <tex>j</tex> выполняется на машине <tex>i</tex>, то <tex>p_{i,j}</tex> является временем обработке работы <tex>j</tex> на машине <tex>i</tex>}}

{{Определение
|definition =
'''Время появления''' (Release date, <tex>r_{j}</tex>) <tex>r_{j}</tex> является временем появления в системе работы <tex>j</tex>, минимальное время в которое можно начать обработку работы <tex>j</tex>}}

{{Определение
|definition =
'''Время окончания''' (Due date, <tex>d_{j}</tex>) <tex>d_{j}</tex> является временем до которого ожидается выполнения работы <tex>j</tex>. Если работа <tex>j</tex> была выполнена после <tex>d_{j}</tex>, то налагается штраф}}

{{Определение
|definition =
'''Дедлайн''' (Deadline, <tex>d_{j}</tex>) Тоже самое что и время окончания, но после дедлайна выполнять работу нельзя.}}

{{Определение
|definition =
'''Вес''' (Weight, <tex>w_{j}</tex>) Величина, отражающая значение работы <tex>j</tex>.}}

{{Определение
|definition =
'''Прерывание''' (Preemption, <tex>pmtn</tex>) Работа может быть прервана и продолжена позже.}}

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

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

{{Определение
|definition =
'''Цель оптимизации''' минимизировать тот или иной критерий.}}

{{Определение
|definition =
<tex> {-} </tex> (None) Цель - просто сделать.}}

{{Определение
|definition =
'''Время окончания работы''' (Completion time, <tex>C_{j}</tex>) Время окончания обработки работы <tex>j</tex>.}}

{{Определение
|definition =
'''Опоздание''' (Lateness, <tex>L_{j}</tex>) .<tex>L_{j}</tex> = <tex>C_{j}</tex> - <tex>d_{j}</tex>}}

{{Определение
|definition =
'''Опоздание''' (Tardiness, <tex>T_{j}</tex>) .<tex>T_{j}</tex> = <tex>max(L_{i}, 0)</tex>}}

{{Определение
|definition =
'''Штраф''' (Unit penalty, <tex>U_{j}</tex>) . Если <tex>C_{j}</tex> > <tex>d_{j}</tex>, то <tex>U_{j}</tex> = 1, иначе <tex>U_{j}</tex> = 0 }}

{{Определение
|definition =
'''Опоздание''' (Tardiness, <tex>L_{j}</tex>) .<tex>T_{j}</tex> = <tex>max(L_{i}, 0)</tex>}}

==Источники==
*[http://books.google.ru/books?id=MAY1ZstmGPkC&dq=HandBook+of+Scheduling&hl=ru&sa=X&ei=O8PMT8nYEKjh4QTKgsHsBw&ved=0CDMQ6AEwAA Handbook of scheduling: algorithms, models, and performance analysis, Joseph Y-T. Leung ]
*[http://books.google.ru/books?id=FrUytMqlCv8C&printsec=frontcover&dq=scheduling+algorithms&hl=ru&sa=X&ei=0MPMT4HqKYSk4gSBm6gp&sqi=2&ved=0CDEQ6AEwAA#v=onepage&q=scheduling%20algorithms&f=false Scheduling Algorithms, Peter Brucker]

Викиконспекты - Вклад участника [ru]

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