6
правок
Изменения
м
<tex> '''Цель оптимизации''' {{---} </tex> (None) Цель - просто сделать} минимизировать тот или иной критерий.}}
'''Время окончания работы''' (Completion time, <tex>C_{j-}</tex>(англ. ''None'') Время окончания обработки работы <tex>j</tex>. Цель {{---}} просто сделать.}}
Определение Open shop машин -> машине
==Нотация Грэхема==
<tex> \alpha </tex> | <tex> \mid \beta </tex> | <tex> \mid \gamma </tex>
Поле <tex> \alpha </tex> описывает тип обработки. Задается одним значением.
{{Определение
|definition =
'''Open shop''' (''<tex>O_{m}</tex>''). В системе находится <tex>m</tex> машин, работающих параллельно. Каждая работа должна быть выполнена один раз на каждой машинмашине. Порядок не важен}}
==Характеристики работ==
|definition =
'''Прерывание''' (англ. ''Preemption'', ''<tex>pmtn</tex>''). Работа может быть прервана и продолжена позже.}}
==Зависимость между работами==
Работа может начаться только после выполнения некоторых других работ. Зависимость между работами может быть представлена в виде [[Основные определения теории графов#oriented_grath|ориентированного графа]]. При этом каждой вершине сопоставляется работа таким образом, что если <tex>i</tex> выполняется перед <tex>j</tex>, то существует ребро из вершины <tex>i</tex> в <tex>j</tex>.
{{Определение
|definition =
'''Prec''' {{---}} произвольный ациклический граф зависимостей.
}}
{{Определение
|definition =
'''Зависимость между работамиChains''' (англ. ''Precedence Contraints'', ''<tex>prec</tex>''). Работа может начаться только после выпонения некоторых других работ. Может быть представлено в виде ориентированного графа. При этом каждой вершине соответствует работа и работа <tex>i</tex> выполняется перед работой <tex>j</tex>, если есть ребро из вершины <tex>i</tex> в <tex>j</tex>. *''chains'' {{---}} ациклический граф зависимостей, причём в каждую вершину входит не более одного ребра и выходит не более одного ребра.*''intree'' {{---}} из вершины выходит не более одного ребра*''outtree'' {{---}} в вершину входит не более одного ребра*''prec'' {{---}} произвольный ациклический граф зависимостей }}
{{Определение|id =intree|definition =Критерий оптимизации=='''Intree''' {{---}} дерево зависимостей, из каждой вершины которого выходит не более одного ребра.}}
{{Определение
|definition =
'''Цель оптимизацииOuttree''' минимизировать тот или иной критерий{{---}} дерево зависимостей, в каждую вершину которого входит не более одного ребра.}} ==Критерий оптимизации==
{{Определение
|definition =
{{Определение
|definition =
{{Определение
|definition =
'''ОпозданиеВремя окончания работы''' (Latenessангл. ''Completion time'', ''<tex>L_C_{j}</tex>'') .<tex>L_{j{---}</tex> = <tex>C_{j}время окончания обработки работы </tex> - <tex>d_{j}</tex>.}}
{{Определение
|definition =
'''Опоздание''' (Tardinessангл. ''Lateness'', ''<tex>T_L_{j}</tex>'') .<tex>T_L_{j}</tex> = <tex>max(L_C_{j} - d_{ij}, 0)</tex>.}}
{{Определение
|definition =
'''ШтрафМедлительность''' (Unit penaltyангл. ''Tardiness'', ''<tex>U_T_{j}</tex>'') . Если <tex>C_T_{j}</tex> > <tex>d_= \max(L_{ji}</tex>, то <tex>U_{j}0)</tex> = 1, иначе <tex>U_{j}</tex> = 0 .}}
{{Определение
|definition =
'''ОпозданиеШтраф''' (Tardinessангл. ''Unit penalty'', ''<tex>L_U_{j}</tex>'') .Если <tex>T_C_{j} > d_{j}</tex> , то <tex>U_{j} = 1</tex>max(L_, иначе <tex>U_{ij}, = 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=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]
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Теория расписаний]]
