37
правок
Изменения
Нет описания правки
Дано <tex>m</tex> станков, на которых нужно обработать <tex>n</tex> деталей. Каждую деталь нужно обработать по очереди на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть дедлайн <tex>d_i</tex> {{---}} время, до которого она должна быть закончена, и штраф <tex>w_i</tex>, который нужно будет выплатить в случае, если работа была закончена после <tex>d_i</tex>. Необходимо минимизировать суммарный штраф, который придется выплатить.
}}
==Эвристика NEH==
Одним из наиболее известных алгоритмов решения этой задачи является эвристика Наваза, Энскора и Хама (Nawaz, Enscore, Ham)
Первое что нужно сделать это упорядочить требования по <tex>\sum\limits_{j = 1}^n p_{i j}</tex> и пронумеровать их в соответствии с этим порядком. Затем нужно определить порядок обслуживания двух первых требований так, чтобы минимизировать время их обслуживания. После этого использовать алгоритм
'''for''' <tex> i = 3</tex> '''to''' <tex>m</tex> '''do'''
Поместить требование <tex>i</tex> на позицию <tex>k \in [1 , i]</tex> которое минимизирует общее время обслуживания первых <tex>i</tex> требований.
==Описание алгоритма==
==Источники информации==
* Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.
* Vladimír Modrák, R. Sudhakara Pandian. FLOW SHOP SCHEDULING ALGORITHM TO MINIMIZE COMPLETION TIME FOR -JOBS -MACHINES PROBLEM
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
