1outtreesumwc
Содержание
Постановка задачи
Мы должны составить расписание с произвольными временами обработки на одном станке. Минимизировать нужно взвешенную сумму времен завершения работ. Зависимости между работами заданы исходящим деревом — работа, которая соответствует корню, доступна в начале, все другие работы зависят от одной работы — отца в дереве. Тривиальным примером подобной задачи является демонтаж сложного механизма.
Свойства оптимального расписания
Докажем некоторые свойства оптимального расписания, которые мы будем использовать в доказательстве корректности алгоритма.
Введем некоторые обозначения для удобства. За
обозначим список всех ребёр дерева. Для всех работ обозначим обозначим за всех потомков в дереве зависимостей, включая саму работу , введём новый парамерт работы .Для подмножества работ
определим:
Два непересекающихся множества работ
будем называть параллельными , если для всех выполняется: не является ни предком, ни потомком . Если множества состоят из одной работы , будем писать . Каждое расписание представлено перестановкой .Лемма: |
Пусть — оптимальное расписание, и — два таких параллельных блока (множества работ, выполняемых последовательно) из , что выполняется сразу после . Пусть — расписание, полученное из перестановкой и . Тогда выполяются следующие пункты:
Если и , то — оптимальное расписание. |
Доказательство: |
Пусть . Так как — оптимальное расписание, то . Таким образом:
Поделим на :Если , то , следовательно расписание оптимально. |
Теорема: |
Пусть работы такие, что — потомок , и . Тогда существует оптимальное расписание, в котором работа идёт сразу после работы |
Доказательство: |
Каждое расписание может быть представлено последовательностью работ в порядке, в котором они выполняются. Пусть будет оптимальной такой последовательностью со свойством, что количество работ между и равное было бы минимальным. Можно считать, что . Тогда расписание можно представить следующим образом://TODO: картинка i ... k j Рассмотрим 2 случая. Случай 1: Работа лемме , а по условию выбора имеем , значит, . Опять же из леммы следует, что работы и можно поменять местами, не ухудшив расписание. Это противоречит тому, что мы выбрали минимальное . не является потомком работы , иначе у неё было бы предка. Следовательно, . ПоСлучай 2: Работа Пусть будет последней работой в расписании между и включая работу , которая принадлежит , то есть для всех работ в множестве назначенных между и имеем, что . Так как наш граф зависимостей работ является исходящим деревом и , то любой предок работы также является и предком работы . Поэтому никакая работа из не является предком иначе бы она не смогла стоять после или потомком, значит, . Из этого следует, что . не является потомком какой-либо работы . В противном же случае получалось, что , значит, является не последней работой из между и . Поэтому , откуда тут же следует, что . По определению имеем, что , следовательно . По лемме мы можем поменять блоки и не нарушив оптимальности расписания. |
Алгоритм
Доказанная в предыдущем пункте теорема уже даёт основную идею алгоритма: взять работу , отличную от корня дерева, с максимальным значением и поставить её в расписании сразу после своего непосредственного предка . Так как существует оптимальное расписание, в котором работа идёт сразу после , то мы можем объедить вершины графа в одну вершину , которая представляет собой последовательность . Все сыновья работы станут сыновьями новой вершины .
Будем повторять процесс слияния вершин, пока не останется всего одна вершина.
Таким образом каждая вершина
представляется множеством работ и соответствующей этому множеству последовательностью . На очередном шаге алгоритма мы находим вершину , отличную от корня, с максимальным значением . Пусть — непосредственный предок работы . Тогда нам надо найти такую вершину , что . После этого мы объединяем обе вершины, заменяя и на и , где — это конкатенация последовательностей и .Детали описаны в алгоритме ниже, в котором
- обозначает последнюю работу в последовательности
- обозначает предка в графе зависимостей, а после слияния с какой-то вершиной — предыдущую работу в последовательности .
w[root] =for i = 1..n: E[i] = {i}, J[i] = {i}, q[i] = w[i] \ p[i] L = {1, ... , n} while L {root}: // пока в списке работ не останется только корень Найти работу j L с маскимальным значением q[j] par = P[j] Найти i, что par J[i] w[i] += w[j] p[i] += p[j] q[i] = w[i] / w[j] // пересчитаем значения в вершине P[j] = E[i] // предком работы j теперь будет последняя работа в E[i] = E[j] // последней работой в теперь будет последняя работа в J[i] = J[i] J[j] L = L \ {j}
Вначале делаем присваивание
, чтобы корень никогда не выбрался на шаге выбора вершины с максимальным значением . В реализации же можно просто дополнительно проверять на равенство с корнем, чтобы избежать переполнений или испортить значение .После завершения этой процедуры оптимальное расписание можно восстановить с конца, зная
и массив .Если для получения работы
с минимальным значением использовать очередь с приоритетами, а для поиска родителям вершины использовать систему непересекающихся множеств, то время работы алгоритма будет .Доказательство оптимальности алгоритма
Теорема: |
Алгоритм строит оптимальное расписание. |
Доказательство: |
Доказательство проведём по индукции. Очевидно, что для одной вершины алгоритм построит оптимальное расписание. Пусть теперь он может составить оптимальную последовательность назначенных работ числом меньше . Пусть также работы — работы, которые объединяться на первом шаге алгоритма. Тогда оптимальное расписание можно представить следующим образом:
После объединения работ и в одну расписание примет такой вид:
где . Обозначим за целевые функции для последовательностей и соответственно. Тогда
Следовательно, расписание будет оптимальным тогда и только тогда, когда расписание будет оптимальным. А по предположению индукции наш алгоритм составит оптимальное расписание для последовательности .Теперь разделим обе части равенства на . Получим, что расстояние между целевыми функциями равноЭто расстояние минимально (по модулю), так как мы выбирали работу с максимальным значением . Из этих утверждений и следует оптимальность построенного алгоритмом расписания. |
Литература
- P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 73 - 78