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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 22 промежуточные версии 7 участников)
Строка 1: Строка 1:
 
==Нотация Грэхема==
 
==Нотация Грэхема==
<tex> \alpha </tex> | <tex> \beta </tex> | <tex> \gamma </tex>
+
<tex> \alpha \mid \beta \mid \gamma </tex>
  
 
Поле <tex> \alpha </tex> описывает тип обработки. Задается одним значением.
 
Поле <tex> \alpha </tex> описывает тип обработки. Задается одним значением.
Строка 11: Строка 11:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Одна машина''' (Single machine, '''1''') В системе находится одна машина.}}
+
'''Одна машина''' (англ. ''Single machine'', ''<tex>1</tex>''). В системе находится одна машина.}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Параллельные одинаковые машины''' (Parallel and Identical Machines, '''<tex>P_{m}</tex>''') В системе находится m одинаковых машин, работающих параллельно.}}
+
'''Параллельные одинаковые машины''' (англ. ''Parallel and Identical Machines'', ''<tex>P_{m}</tex>''). В системе находится <tex>m</tex> одинаковых машин, работающих параллельно.}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Параллельные однородные машины''' (Uniform Machines, '''<tex>Q_{m}</tex>''') В системе находится m машин, работающих параллельно. У машин разные скорости выполнения работ.}}
+
'''Параллельные однородные машины''' (англ. ''Uniform Machines'', ''<tex>Q_{m}</tex>''). В системе находится <tex>m</tex> машин, работающих параллельно. У машин разные скорости выполнения работ.}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Параллельные несвязанные машины''' (Unrelated Machines, '''<tex>R_{m}</tex>''') В системе находится m машин, работающих параллельно. У машин разные скорости выполнения разных работ.}}
+
'''Параллельные несвязанные машины''' (англ. ''Unrelated Machines'', ''<tex>R_{m}</tex>''). В системе находится <tex>m</tex> машин, работающих параллельно. У машин разные скорости выполнения разных работ.}}
  
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Job shop''' ('''<tex>J_{m}</tex>''') В системе находится m машин, работающих параллельно. У каждой работы свой упорядоченный список машин, на которых они должны быть выполнены.}}
+
'''Job shop''' (''<tex>J_{m}</tex>''). В системе находится <tex>m</tex> машин, работающих параллельно. У каждой работы свой упорядоченный список машин, на которых они должны быть выполнены.}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Flow shop''' ('''<tex>F_{m}</tex>''') В системе находится m машин, работающих параллельно. Машины упорядочены. Работы должны выполняться сначала на первой машине, потом на второй и т.д. до последней.}}
+
'''Flow shop''' (''<tex>F_{m}</tex>''). В системе находится <tex>m</tex> машин, работающих параллельно. Машины упорядочены. Работы должны выполняться сначала на первой машине, потом на второй и так далее до последней.}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Open shop''' ('''<tex>O_{m}</tex>''') В системе находится m машин, работающих параллельно. Каждая работа должна быть выполнена один раз на каждой машин. Порядок не важен}}
+
'''Open shop''' (''<tex>O_{m}</tex>''). В системе находится <tex>m</tex> машин, работающих параллельно. Каждая работа должна быть выполнена один раз на каждой машине. Порядок не важен}}
  
 
==Характеристики работ==
 
==Характеристики работ==
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Время работы''' (Processing time, <tex>p_{i,j}</tex>) Если работа j выполняется на машине i, то <tex>p_{i,j}</tex> является временем обработке работы j на машине i}}
+
'''Время работы''' (англ. ''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 =
 
|definition =
'''Время появления''' (Release date, <tex>r_{j}</tex>) <tex>r_{j}</tex> является временем появления в системе работы j, минимальное время в которое можно начать обработку работы j}}
+
'''Время появления''' (англ. ''Release date'', ''<tex>r_{j}</tex>'') является временем появления в системе работы <tex>j</tex>, минимальное время в которое можно начать обработку работы <tex>j</tex>}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Время окончания''' (Due date, <tex>d_{j}</tex>) <tex>d_{j}</tex> является временем до которого ожидается выполнения работы j. Если работа j была выполнена после <tex>d_{j}</tex>, то налагается штраф}}
+
'''Время окончания''' (англ. ''Due date'', ''<tex>d_{j}</tex>'') является временем до которого ожидается выполнения работы <tex>j</tex>. Если работа <tex>j</tex> была выполнена после <tex>d_{j}</tex>, то налагается штраф}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Дедлайн''' (Deadline, <tex>d_{j}</tex>) Тоже самое что и время окончания, но после дедлайна выполнять работу нельзя.}}
+
'''Дедлайн''' (англ. ''Deadline'', ''<tex>d_{j}</tex>'') {{---}} тоже самое что и время окончания, но после дедлайна выполнять работу нельзя.}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Вес''' (Weigth, <tex>w_{j}</tex>) Величина отражающая значение работы j.}}
+
'''Вес''' (англ. ''Weight'', ''<tex>w_{j}</tex>'') {{---}} величина, отражающая значение работы <tex>j</tex>.}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Прерывание''' (Preemption, <tex>pmtn</tex>) Работа может быть прервана и продолжена позже.}}
+
'''Прерывание''' (англ. ''Preemption'', ''<tex>pmtn</tex>''). Работа может быть прервана и продолжена позже.}}
 +
 
 +
==Зависимость между работами==
 +
Работа может начаться только после выполнения некоторых других работ. Зависимость между работами может быть представлена в виде [[Основные определения теории графов#oriented_grath|ориентированного графа]]. При этом каждой вершине сопоставляется работа таким образом, что если <tex>i</tex> выполняется перед <tex>j</tex>, то существует ребро из вершины <tex>i</tex> в <tex>j</tex>.
 +
 
 +
{{Определение
 +
|definition =
 +
'''Prec''' {{---}} произвольный ациклический граф зависимостей.
 +
}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Зависимость между работами''' (Precedence Contraints, <tex>prec</tex>) {Работа может начаться только после выпонения некоторых других работ. Может быть представлено ввиде ориентированного графа. При этом каждой вершине соответствует работа и работа i выполняется перед работой j, если есть ребро из вершины i в j.
+
'''Chains''' {{---}} ациклический граф зависимостей, причём в каждую вершину входит не более одного ребра и выходит не более одного ребра.
*''chains'' <tex>{-}</tex> в каждую вершину входит не более одного ребра и выходит не более одного ребра
+
}}
*''intree'' <tex>{-}</tex> из вершины выходит не более одного ребра
 
*''outtree'' <tex>{-}</tex> в вершину входит не более одного ребра
 
}}
 
  
 +
{{Определение
 +
|id = intree
 +
|definition =
 +
'''Intree''' {{---}} дерево зависимостей, из каждой вершины которого выходит не более одного ребра.
 +
}}
 +
 +
{{Определение
 +
|definition =
 +
'''Outtree''' {{---}} дерево зависимостей, в каждую вершину которого входит не более одного ребра.
 +
}}
  
 
==Критерий оптимизации==
 
==Критерий оптимизации==
Строка 76: Строка 91:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Цель оптимизации''' минимизировать тот или иной критерий.}}
+
'''Цель оптимизации''' {{---}} минимизировать тот или иной критерий.}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Время окончания работы''' (Completion time, <tex>C_{j}</tex>) Время окончания обработки работы j.}}
+
<tex> {-} </tex> (англ. ''None''). Цель {{---}} просто сделать.}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Опоздание''' (Lateness, <tex>L_{j}</tex>) .<tex>L_{j}</tex> = <tex>C_{j}</tex> - <tex>d_{j}</tex>}}
+
'''Время окончания работы''' (англ. ''Completion time'', ''<tex>C_{j}</tex>'') {{---}} время окончания обработки работы <tex>j</tex>.}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Опоздание''' (Tardiness, <tex>T_{j}</tex>) .<tex>T_{j}</tex> = <tex>max(L_{i}, 0)</tex>}}
+
'''Опоздание''' (англ. ''Lateness'', ''<tex>L_{j}</tex>''). <tex>L_{j} = C_{j} - d_{j}</tex>.}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|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 }}
+
'''Медлительность''' (англ. ''Tardiness'', ''<tex>T_{j}</tex>''). <tex>T_{j} = \max(L_{i}, 0)</tex>.}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Опоздание''' (Tardiness, <tex>L_{j}</tex>) .<tex>T_{j}</tex> = <tex>max(L_{i}, 0)</tex>}}
+
'''Штраф''' (англ. ''Unit penalty'', ''<tex>U_{j}</tex>''). Если <tex>C_{j} > d_{j}</tex>, то <tex>U_{j} = 1</tex>, иначе <tex>U_{j} = 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]
 +
 +
[[Категория:Алгоритмы и структуры данных]]
 +
[[Категория:Теория расписаний]]

Текущая версия на 19:39, 4 сентября 2022

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

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

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

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

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

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

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


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


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


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



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


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


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


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

Определение:
Время работы (англ. 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]j[/math], минимальное время в которое можно начать обработку работы [math]j[/math]


Определение:
Время окончания (англ. Due date, [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]). Работа может быть прервана и продолжена позже.


Зависимость между работами

Работа может начаться только после выполнения некоторых других работ. Зависимость между работами может быть представлена в виде ориентированного графа. При этом каждой вершине сопоставляется работа таким образом, что если [math]i[/math] выполняется перед [math]j[/math], то существует ребро из вершины [math]i[/math] в [math]j[/math].


Определение:
Prec — произвольный ациклический граф зависимостей.


Определение:
Chains — ациклический граф зависимостей, причём в каждую вершину входит не более одного ребра и выходит не более одного ребра.


Определение:
Intree — дерево зависимостей, из каждой вершины которого выходит не более одного ребра.


Определение:
Outtree — дерево зависимостей, в каждую вершину которого входит не более одного ребра.


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

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


Определение:
[math] {-} [/math] (англ. None). Цель — просто сделать.


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


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


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


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


См. также

Источники информации