Изменения

Дано <tex>m</tex> станков, на которых нужно обработать <tex>n</tex> деталей. Каждую деталь нужно обработать по очереди на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть дедлайн <tex>d_i</tex> {{---}} время, до которого она должна быть закончена, и штраф <tex>w_i</tex>, который нужно будет выплатить в случае, если работа была закончена после <tex>d_i</tex>. Необходимо минимизировать суммарный штраф, который придется выплатить.

}}

Одним из наиболее известных алгоритмов решения этой задачи является эвристика Наваза, Энскора и Хама (Nawaz, Enscore, Ham)

Поместить требование <tex>i</tex> на позицию <tex>k \in [1 , i]</tex> которое минимизирует общее время обслуживания первых <tex>i</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> сводится к задаче <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>.