Классификация задач — различия между версиями
(→Типы обработки) |
(→Критерий оптимизации) |
||
Строка 76: | Строка 76: | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
− | '''Цель оптимизации''' минимизировать тот или иной критерий.}} | + | '''Цель оптимизации''' {{---}} минимизировать тот или иной критерий.}} |
{{Определение | {{Определение | ||
|definition = | |definition = | ||
− | <tex> {-} </tex> (None) Цель - просто сделать.}} | + | <tex> {-} </tex> (англ. ''None''). Цель {{---}} просто сделать.}} |
{{Определение | {{Определение | ||
|definition = | |definition = | ||
− | '''Время окончания работы''' (Completion time, <tex>C_{j}</tex>) | + | '''Время окончания работы''' (англ. ''Completion time'', ''<tex>C_{j}</tex>'') {{---}} время окончания обработки работы <tex>j</tex>.}} |
{{Определение | {{Определение | ||
|definition = | |definition = | ||
− | '''Опоздание''' (Lateness, <tex>L_{j}</tex>) .<tex>L_{j} | + | '''Опоздание''' (англ. ''Lateness'', ''<tex>L_{j}</tex>''). <tex>L_{j} = C_{j} - d_{j}</tex>.}} |
{{Определение | {{Определение | ||
|definition = | |definition = | ||
− | '''Опоздание''' (Tardiness, <tex>T_{j}</tex>) .<tex>T_{j} | + | '''Опоздание''' (англ. ''Tardiness'', ''<tex>T_{j}</tex>''). <tex>T_{j} = max(L_{i}, 0)</tex>.}} |
{{Определение | {{Определение | ||
|definition = | |definition = | ||
− | '''Штраф''' (Unit penalty, <tex>U_{j}</tex>) . Если <tex>C_{j} | + | '''Штраф''' (англ. ''Unit penalty'', ''<tex>U_{j}</tex>''). Если <tex>C_{j} > d_{j}</tex>, то <tex>U_{j} = 1</tex>, иначе <tex>U_{j} = 0</tex>. }} |
{{Определение | {{Определение | ||
|definition = | |definition = | ||
− | '''Опоздание''' (Tardiness, <tex>L_{j}</tex>) .<tex>T_{j} | + | '''Опоздание''' (англ. ''Tardiness'', ''<tex>L_{j}</tex>''). <tex>T_{j} = 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=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] | *[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] |
Версия 15:35, 7 июня 2015
Содержание
Нотация Грэхема
| |
Поле
описывает тип обработки. Задается одним значением.Поле
описывает характеристики работ. Задает параметры работ, и то, какими свойствами должно обладает расписание.Поле
описывает критерий оптимизации. Содержит функцию, которую нужно оптимизировать.Типы обработки
Определение: |
Одна машина (англ. Single machine, | ). В системе находится одна машина.
Определение: |
Параллельные одинаковые машины (англ. Parallel and Identical Machines, | ). В системе находится одинаковых машин, работающих параллельно.
Определение: |
Параллельные однородные машины (англ. Uniform Machines, | ). В системе находится машин, работающих параллельно. У машин разные скорости выполнения работ.
Определение: |
Параллельные несвязанные машины (англ. Unrelated Machines, | ). В системе находится машин, работающих параллельно. У машин разные скорости выполнения разных работ.
Определение: |
Job shop ( | ). В системе находится машин, работающих параллельно. У каждой работы свой упорядоченный список машин, на которых они должны быть выполнены.
Определение: |
Flow shop ( | ). В системе находится машин, работающих параллельно. Машины упорядочены. Работы должны выполняться сначала на первой машине, потом на второй и так далее до последней.
Определение: |
Open shop ( | ). В системе находится машин, работающих параллельно. Каждая работа должна быть выполнена один раз на каждой машин. Порядок не важен
Характеристики работ
Определение: |
Время работы (англ. Processing time, | ). Если работа выполняется на машине , то является временем обработке работы на машине
Определение: |
Время появления (англ. Release date, | ) является временем появления в системе работы , минимальное время в которое можно начать обработку работы
Определение: |
Время окончания (англ. Due date, | ) является временем до которого ожидается выполнения работы . Если работа была выполнена после , то налагается штраф
Определение: |
Дедлайн (англ. Deadline, | ) — тоже самое что и время окончания, но после дедлайна выполнять работу нельзя.
Определение: |
Вес (англ. Weight, | ) — величина, отражающая значение работы .
Определение: |
Прерывание (англ. Preemption, | ). Работа может быть прервана и продолжена позже.
Определение: |
Зависимость между работами (англ. Precedence Contraints,
| ). Работа может начаться только после выпонения некоторых других работ. Может быть представлено в виде ориентированного графа. При этом каждой вершине соответствует работа и работа выполняется перед работой , если есть ребро из вершины в .
Критерий оптимизации
Определение: |
Цель оптимизации — минимизировать тот или иной критерий. |
Определение: |
(англ. None). Цель — просто сделать. |
Определение: |
Время окончания работы (англ. Completion time, | ) — время окончания обработки работы .
Определение: |
Опоздание (англ. Lateness, | ). .
Определение: |
Опоздание (англ. Tardiness, | ). .
Определение: |
Штраф (англ. Unit penalty, | ). Если , то , иначе .
Определение: |
Опоздание (англ. Tardiness, | ). .