Изменения

Перейти к: навигация, поиск

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

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

Навигация