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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1p...»)
 
Строка 1: Строка 1:
−
<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div>
+
==Нотация Грэхема==
−
<includeonly>[[Категория: В разработке]]</includeonly>
+
<tex> \alpha </tex> | <tex> \beta </tex> | <tex> \gamma </tex>
 +
 
 +
Поле <tex> \alpha </tex> описывает тип обработки. Задается одним значением.
 +
 
 +
Поле <tex> \beta </tex> описывает характеристики работ. Задает параметры работ, и то, какими свойствами должно обладает расписание.
 +
 
 +
Поле <tex> \gamma</tex> описывает критерий оптимизации. Содержит функцию, которую нужно оптимизировать.
  
−
Классификация задач
+
==Типы обработки==
−
нотация Грэхема
 
−
a|b|c
 
−
a - тип обработки
 
−
b - характерстика работ
 
−
с - критерий оптимизации
 
−
==Диаграммы Гантта==
 
−
Пусть работы <tex> J_i (i = 1,..,n) </tex> должны быть выполнены на машинах <tex> M_i (i = 1,..,n) </tex>.
 
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
−
'''Расписанием''' называется соответствие между каждой работой и одним или более интервалов времени на одной или более машине, на которой эта работа выполняется.
+
'''Одна машина''' (Single machine, '''1''') В системе находится одна машина.}}
−
}}
 
−
'''Диаграмма Гантта''' <tex>{-}</tex> способ представления расписания.
 
  
−
===Пример===
+
{{Определение
−
'''вставь картинку'''
+
|definition =
 +
'''Параллельные одинаковые машины''' (Parallel and Identical Machines, '''<tex>P_{m}</tex>''') В системе находится m одинаковых машин работающих параллельно.}}
  
−
==Нотация Грэхема==
+
{{Определение
−
Чтобы описать задачу на теорию расписаний требуется указать три поля.
+
|definition =
 +
'''Параллельные однородные машины''' (Uniform Machines, '''<tex>Q_{m}</tex>''') В системе находится m машин работающих параллельно. У машин разные скорости выполнения работ.}}
  
−
<tex> \alpha | \beta | \gamma </tex>. При этом
+
{{Определение
−
==Характеристика работ==
+
|definition =
 +
'''Параллельные несвязанные машины''' (Unrelated Machines, '''<tex>R_{m}</tex>''') В системе находится m машин работающих параллельно. У машин разные скорости выполнения разных работ.}}
  
−
<tex> \beta_1 {-}</tex> pmtn(premtion) - возможность остановить работу и продолжить ее позже. Работа может быть прервана несколько раз.
+
----
−
 
−
<tex> \beta_2 {-}</tex> precedence - работа может начаться только после завершения каких-то других работ. b2 удобно задавать графом.
 
−
prec - ациклический направленный граф, соответственно ребро (i, j), будет если j может начаться только после окончания i.
 
−
'''write about intree outtree '''
 
  
−
<tex> \beta_3 {-}</tex> означает, что работы появляются в определенное время (release time), задается множеством <tex> r_i </tex>.
+
{{Определение
 +
|definition =
 +
'''Job shop''' ('''<tex>J_{m}</tex>''') В системе находится m машин работающих параллельно. У машин разные скорости выполнения разных работ.}}
  
−
<tex> \beta_4 {-}</tex> время, которое нужно затратить станку на выполнение работы, задается множеством <tex> p_i </tex>.  
+
{{Определение
 +
|definition =
 +
'''Flow shop''' ('''<tex>F_{m}</tex>''') В системе находится m машин работающих параллельно. У машин разные скорости выполнения разных работ.}}
  
−
<tex> \beta_5 {-}</tex> дедлайны на работы, время к которому работы должны быть закончены, задается множеством <tex> d_i </tex>.
+
{{Определение
 +
|definition =
 +
'''Open shop''' ('''<tex>O_{m}</tex>''') В системе находится m машин работающих параллельно. У машин разные скорости выполнения разных работ.}}
  
−
<tex> \beta_6 {-}</tex> условие на пакеты. Означает, что некоторые работ объединены в группу, которая должна быть выполнена на одной машине.
+
----
 +
==Характеристики работ==
 +
{{Определение
 +
|definition =
 +
'''Время работы''' (Processing time, <tex>p_{i,j}</tex>) Если работа j выполняется на машине i, то <tex>p_{i,j}</tex> является временем обработке работы j на машине i}}
  
−
==Критерии оптимизации==
+
{{Определение
−
+
|definition =
−
<tex> C_i </tex> время окончания работы
+
'''Время появления''' (Release date, <tex>r_{j}</tex>) <tex>r_{j}</tex> является временем появления в системе работы j, минимальное время в которое можно начать обработку работы j}}
  
−
<tex> L_i = C_i - d_i </tex>
+
{{Определение
 +
|definition =
 +
'''Время окончания''' (Due date, <tex>d_{j}</tex>) <tex>d_{j}</tex> является временем до которого ожидается выполнения работы j. Если работа j была выполнена после <tex>d_{j}</tex>, то налагается штраф}}
  
−
<tex> T_i = max0, C_i - d_i</tex> '''Найти аккуратные максимум'''
+
{{Определение
 +
|definition =
 +
'''Дедлайн''' (Deadline, <tex>d_{j}</tex>) Тоже самое что и время окончания, но после дедлайна выполнять работу нельзя.}}
 +
 
 +
{{Определение
 +
|definition =
 +
'''Вес''' (Weigth, <tex>w_{j}</tex>) Величина отражающая значение работы j.}}
  
−
<tex> U_i = </tex>
+
{{Определение
−
<tex>  \Bigg\{  
+
|definition =
−
\begin{matrix}
+
'''Прерывание''' (Preemption, <tex>pmtn</tex>) Работа может быть прервана и продолжена позже.}}
−
    1,c_i > d_i \\
 
−
    0, c_i < p_i\\
 
−
\end{matrix}
 
−
</tex>
 
  
−
f_i(C_i) монотонно неубывающая функция  f_max = max f_i
+
{{Определение
 +
|definition =
 +
'''Зависимость между работами''' (Precedence Contraints, <tex>prec</tex>) {Работа может начаться только после выпонения некоторых других работ. Может быть представлено ввиде ориентированного графа. При этом каждой вершине соответствует работа и работа i выполняется перед работой j, если есть ребро из вершины i в j.
 +
*''chains'' <tex>{-}</tex> в каждую вершину входит не более одного ребра и выходит не более одного ребра
 +
*''intree'' <tex>{-}</tex> из вершины выходит не более одного ребра
 +
*''outtree'' <tex>{-}</tex> в вершину входит не более одного ребра
 +
}}
  
  
 +
==Критерий оптимизации==
  
−
==Тип обработки==
+
{{Определение
−
<tex> P_m {-}</tex> несколько одинаковых станков
+
|definition =
 +
'''Цель оптимизации''' минимизировать то или иной критерий.}}
  
−
<tex> Q_m {-}</tex> разные, но однородные станки(отличаются скорость).
+
{{Определение
 +
|definition =
 +
'''Время окончания работы''' (Completion time, <tex>C_{j}</tex>) Время окончания обработки работы j.}}
  
−
<tex> R_m {-}</tex> разные произвольные станки.
+
{{Определение
 +
|definition =
 +
'''Опоздание''' (Lateness, <tex>L_{j}</tex>) .<tex>L_{j}</tex> = <tex>C_{j}</tex> - <tex>d_{j}</tex>}}
 +
 
 +
{{Определение
 +
|definition =
 +
'''Опоздание''' (Tardiness, <tex>L_{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>}}

Версия 16:30, 4 июня 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] в вершину входит не более одного ребра


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

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


Определение:
Время окончания работы (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]L_{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]
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Классификация_задач&oldid=23727»