1632
правки
Изменения
м
===Эвристика 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> требований.
==Алгоритм сведения==
rollbackEdits.php mass rollback
==Алгоритм==
===Описание алгоритма===
После устранения каждого разрыва получим расписание без разрывов, в котором каждая работа заканчивает выполняться не позже, чем в изначальном.
}}
В [[Flow shop|flow shop]] показано как можно получить оптимальное расписание сведя задачу <tex> 1 \mid p_{ij} = 1 \mid ? </tex> к <tex>F \mid p_{ij} = 1 \mid ?</tex> , теперь рассмотрим как <tex>F \mid p_{ij} = 1 \mid \sum w_iu_i</tex> сводится к <tex> 1 \mid p_{ij} = 1 \mid w_iu_i</tex>.
По этому утверждению, если работу <tex>i</tex> начали делать в <tex>t(i)</tex>, то закончена она будет в <tex>t(i) + m</tex>. Найдем время <tex>d'_i</tex> такое, что начав выполнять в него работу <tex>i</tex>, мы успеем выполнить ее до <tex>d_i</tex>: <tex>d'_i = d_i - m</tex>. Таким образом, вычтя из всех <tex>d_i</tex> число <tex>m</tex>, мы свели задачу к <tex>1 \mid p_i = 1 \mid \sum w_i U_i</tex>.
===Сложность алгоритма===
Задача <tex>F \mid p_{i j} = 1 \mid \sum w_iu_i</tex> за <tex>O(n)</tex> сводится к [[1pi1sumwu|задаче <tex>1 \mid p_i = 1 \mid \sum w_i u_i</tex>]]. Задача <tex>1 \mid p_i = 1 \mid \sum u_iw_i</tex> решается за <tex>O(n \log n)</tex>. После решения этой задачи, нужно вывести ответ, имеющий размер <tex>O(nm)</tex>. Значит, итоговая сложность алгоритма {{---}} <tex>O(n \log n + nm)</tex>.
==См. также.==
