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