Изменения

<tex> \alpha </tex> | <tex> \mid \beta </tex> | <tex> \mid \gamma </tex>

'''Одна машина''' (англ. ''Single machine'', '''<tex>1'</tex>'') . В системе находится одна машина.}}

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

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

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

'''Job shop''' ('''<tex>J_{m}</tex>''') . В системе находится <tex>m </tex> машин , работающих параллельно. У каждой работы свой упорядоченный список машин разные скорости выполнения разных работ, на которых они должны быть выполнены.}}

'''Flow shop''' ('''<tex>F_{m}</tex>''') . В системе находится <tex>m </tex> машин , работающих параллельно. У машин разные скорости выполнения разных работМашины упорядочены. Работы должны выполняться сначала на первой машине, потом на второй и так далее до последней.}}

'''Open shop''' ('''<tex>O_{m}</tex>''') . В системе находится <tex>m </tex> машин , работающих параллельно. У машин разные скорости выполнения разных работКаждая работа должна быть выполнена один раз на каждой машине.Порядок не важен}}

'''Время работы''' (англ. ''Processing time'', ''<tex>p_{i,j}</tex>'') . Если работа <tex>j </tex> выполняется на машине <tex>i</tex>, то <tex>p_{i,j}</tex> является временем обработке работы <tex>j </tex> на машине <tex>i</tex>}}

'''Время появления''' (англ. ''Release date'', ''<tex>r_{j}</tex>'') является временем появления в системе работы <tex>r_{j}</tex> является временем появления в системе работы j, минимальное время в которое можно начать обработку работы <tex>j</tex>}}

'''Время окончания''' (англ. ''Due date'', ''<tex>d_{j}</tex>'') является временем до которого ожидается выполнения работы <tex>d_{j}</tex> является временем до которого ожидается выполнения работы j. Если работа <tex>j </tex> была выполнена после <tex>d_{j}</tex>, то налагается штраф}}

'''Дедлайн''' (англ. ''Deadline'', ''<tex>d_{j}</tex>'') Тоже {{---}} тоже самое что и время окончания, но после дедлайна выполнять работу нельзя.}}

'''Вес''' (Weigthангл. ''Weight'', ''<tex>w_{j}</tex>'') Величина {{---}} величина, отражающая значение работы <tex>j</tex>.}}

'''Прерывание''' (англ. ''Preemption'', ''<tex>pmtn</tex>'') . Работа может быть прервана и продолжена позже.}} ==Зависимость между работами==Работа может начаться только после выполнения некоторых других работ. Зависимость между работами может быть представлена в виде [[Основные определения теории графов#oriented_grath|ориентированного графа]]. При этом каждой вершине сопоставляется работа таким образом, что если <tex>i</tex> выполняется перед <tex>j</tex>, то существует ребро из вершины <tex>i</tex> в <tex>j</tex>. {{Определение|definition ='''Prec''' {{---}} произвольный ациклический граф зависимостей.}} {{Определение|definition ='''Chains''' {{---}} ациклический граф зависимостей, причём в каждую вершину входит не более одного ребра и выходит не более одного ребра.}}

'''Зависимость между работамиIntree''' (Precedence Contraints, <tex>prec</tex>) {Работа может начаться только после выпонения некоторых других работ. Может быть представлено ввиде ориентированного графа. При этом каждой вершине соответствует работа и работа i выполняется перед работой j, если есть ребро из вершины i в j. *''chains'' <tex>{---}</tex> в каждую вершину входит не более одного ребра и выходит не более одного ребра*''intree'' <tex>{-}</tex> дерево зависимостей, из каждой вершины которого выходит не более одного ребра.*''outtree'' <tex>{-}</tex> в вершину входит не более одного ребра }}

'''Цель оптимизации''' {{---}} минимизировать то тот или иной критерий.}}

'''Время окончания работы''' (Completion time, <tex>C_{j-}</tex>(англ. ''None'') Время окончания обработки работы j. Цель {{---}} просто сделать.}}

'''ОпозданиеВремя окончания работы''' (Latenessангл. ''Completion time'', ''<tex>L_C_{j}</tex>'') .<tex>L_{j{---}</tex> = <tex>C_{j}время окончания обработки работы </tex> - <tex>d_{j}</tex>.}}

'''Опоздание''' (Tardinessангл. ''Lateness'', ''<tex>L_{j}</tex>'') .<tex>T_L_{j}</tex> = <tex>max(L_C_{j} - d_{ij}, 0)</tex>.}}

'''ШтрафМедлительность''' (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 .}}

'''ОпозданиеШтраф''' (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] [[Категория:Алгоритмы и структуры данных]][[Категория:Теория расписаний]]