37
правок
Изменения
Нет описания правки
Одним из наиболее известных алгоритмов решения этой задачи является эвристика Наваза, Энскора и Хама (Nawaz, Enscore, Ham)
Первое что нужно сделать это упорядочить требования по <tex>\sum\limits_{j = 1}^n p_{i j}</tex> и пронумеровать их в соответствии с этим порядком. Затем нужно определить порядок обслуживания двух первых требований так, чтобы минимизировать время их обслуживания. После этого использовать алгоритм
|statement=Существует оптимальное расписание, в котором каждая работа делается непрерывно.
|proof=
Рассмотрим расписание, в котором есть работы, которые делаются не непрерывно. Рассмотрим самый ранний разрыв: работа <tex>i</tex> делалась в моменты <tex>t(i), t(i)+1, \ldots, t(i)+k</tex>, где <tex>k<m</tex>, но не делалась в момент времени <tex>t(i)+k+1</tex>. Докажем, что в момент времени <tex>t(i)+k+1</tex>, <tex>k+1</tex>-й станок простаивает и можно продолжить делать <tex>i</tex>-ю работу.
Пусть в момент времени <tex>t(i)+k+1</tex> на <tex>k+1</tex>-м станке делается работа <tex>j</tex>. В <tex>t(i)+k</tex>-й момент времени <tex>k</tex>-й станок был занят выполнением <tex>i</tex>-й работы, а значит, не мог выполнять <tex>j</tex>-ю. Значит, разрыв был раньше, что противоречит тому, что был выбран самый ранний разрыв. Значит, в <tex>t(i)+k+1</tex>-й момент <tex>k+1</tex>-й станок свободен и туда можно поставить <tex>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>1 \mid p_i = 1 \mid \sum w_i U_i</tex>, мы найдем времена, в которые нужно начинать выполнять работы. По утверждению выше, работы можно выполнять непрерывно.
==Сложность алгоритма==
Задача <tex>F \mid p_{iji j} = 1 \mid \sum w_iu_i</tex> за <tex>O(n)</tex> сводится к задаче <tex>1 \mid p_i = 1 \mid \sum w_iu_iw_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>.
==См. также.==
