В планировании магазина работы и граф чертеже , то алгоритм Коффмэны-Грэхэм является алгоритмом , названным в честь Эдварда Г. Coffman, младший и Рональд Graham , за организацию элементов частично упорядоченного множества в последовательность уровней. Алгоритм выбирает такую компоновку, что элемент, следующий за другим в порядке, назначается на более низкий уровень, и такой, что каждый уровень имеет количество элементов, которое не превышает фиксированной границы W ширины . Когда W = 2 , он использует минимально возможное количество различных уровней [1] и, как правило, он использует не более 2–2 /W раз больше уровней, чем необходимо. [2] [3]
Постановка проблемы и приложения
В версии задачи планирования рабочих мест, решаемой алгоритмом Коффмана – Грэма, каждому дается набор из n работ J 1 , J 2 , ..., J n вместе с системой ограничений предшествования J i < J j требуя, чтобы задание J i было завершено до начала задания J j . Предполагается, что каждое задание занимает единицу времени для завершения. Задача планирования состоит в том, чтобы назначить каждое из этих заданий временным интервалам в системе из W идентичных процессоров, минимизируя продолжительность выполнения задания (время от начала первого задания до завершения последнего задания). Абстрактно ограничения приоритета определяют частичный порядок на заданиях, поэтому проблему можно перефразировать как одно из присвоения элементов этого частичного порядка уровням (временным интервалам) таким образом, чтобы каждый временной интервал имел не более чем столько же заданий, сколько процессоров (не более W элементов на уровень), соблюдая ограничения приоритета. Это приложение послужило исходной мотивацией для Коффмана и Грэма при разработке своего алгоритма. [1] [4]
В структуре рисования многоуровневого графа, описанной Сугиямой, Тагава и Тода (1981) [5], входными данными является ориентированный граф , а рисование графа строится в несколько этапов: [6] [7]
- Множество дуги обратной связи выбирается, а ребра этого множества обратное, чтобы преобразовать входной сигнал в ориентированный ациклический граф .
- Вершинам графа задаются целые координаты y таким образом, что для каждого ребра начальная вершина ребра имеет более высокую координату, чем конечная вершина, причем не более W вершин имеют одну и ту же y- координату.
- Фиктивные вершины вводятся внутри каждого ребра, так что все разделенные ребра соединяют пары вершин, которые находятся на смежных уровнях чертежа.
- В каждой группе вершин с одинаковой координатой y вершины переставляются , чтобы минимизировать количество пересечений в результирующем чертеже, и вершинам назначаются координаты x в соответствии с этой перестановкой.
- Вершины и ребра графа нарисованы с назначенными им координатами.
В этой структуре назначение координаты y снова включает в себя группировку элементов частично упорядоченного набора (вершины графа с упорядочением достижимости на множестве вершин) в слои (наборы вершин с одинаковой координатой y ), что является проблема решается алгоритмом Коффмана – Грэма. [6] Хотя существуют альтернативные подходы, чем алгоритм Коффмана – Грэма к этапу наложения слоев, эти альтернативы в целом либо не могут включать ограничение максимальной ширины уровня, либо полагаются на сложные процедуры целочисленного программирования . [8]
Более абстрактно, обе эти проблемы могут быть оформлены в виде задачи , в которой входной сигнал состоит из частично упорядоченного множества и целого W . Желаемый результат - это присвоение целочисленных номеров уровней элементам частично упорядоченного набора таким образом, что, если x < y является упорядоченной парой связанных элементов частичного порядка, число, присвоенное x , меньше числа, присвоенного y , так что не более чем W элементам присваиваются одинаковые номера, и минимизирует разницу между наименьшим и наибольшим присвоенными номерами.
Алгоритм
Алгоритм Коффмана – Грэма выполняет следующие шаги. [6]
- Представьте частичный порядок его транзитивным отношением редукции или покрытия , ориентированный ациклический граф G, который имеет ребро от x до y всякий раз, когда x < y, и не существует никакого третьего элемента z частичного порядка, для которого x < z < y . В приложениях для рисования графов алгоритма Коффмана – Грэма результирующий ориентированный ациклический граф может не совпадать с нарисованным графом, а в приложениях планирования он может не иметь ребра для каждого ограничения приоритета входных данных: в обоих случаях , транзитивная редукция удаляет лишние ребра, которые не нужны для определения частичного порядка.
- Построить топологический порядок в G , в которой вершины упорядочены лексикографически по множеству позиций их входящих соседей. Для этого добавляйте вершины по одной в порядок, на каждом шаге выбирая вершину v для добавления так, чтобы все входящие соседи v уже были частью частичного упорядочения, и чтобы последний добавленный входящий сосед v предшествует последнему добавленному входящему соседу любой другой вершины, которая может быть добавлена вместо v . Если две вершины имеют одного и того же самого последнего добавленного входящего соседа, алгоритм прерывает ничью в пользу той, чей второй последний добавленный входящий сосед находится раньше, и т. Д.
- Назначьте вершины G уровням в порядке, обратном топологическому порядку, построенному на предыдущем шаге. Для каждой вершины v добавьте v к уровню, который по крайней мере на один шаг выше, чем самый высокий уровень любого исходящего соседа v , которому еще не назначены W элементов, и который является как можно более низким с учетом этих двух ограничения.
Анализ
Как первоначально доказали Коффман и Грэм (1972) , их алгоритм вычисляет оптимальное назначение для W = 2 ; то есть для планирования задач с заданиями единичной длины на двух процессорах или для задач рисования многоуровневого графа с максимум двумя вершинами на слой. [1] Тесно связанный алгоритм также находит оптимальное решение для планирования заданий с различной продолжительностью, позволяя упредить запланированные задания на двух процессорах. [9] Для W > 2 алгоритм Коффмана – Грэма использует количество уровней (или вычисляет расписание с периодом изготовления), который находится в пределах 2–2 / Вт от оптимального. [2] [3] Например, для W = 3 это означает, что он использует не более чем в 4/3 раза больше уровней, чем является оптимальным. Когда частичный порядок ограничений приоритета является интервальным порядком или принадлежит нескольким связанным классам частичных порядков, алгоритм Коффмана – Грэма находит решение с минимальным числом уровней независимо от его границы ширины. [10]
А также найти графики с небольшой makespan, алгоритм Кофман-Грэхемы (модифицированный из презентации здесь , так что она топологический заказывает обратный граф из G и место Вершины как можно раньше , а не как можно позже) минимизирует общее время потока двухпроцессорных расписаний - сумма времени выполнения отдельных заданий. Связанный алгоритм может использоваться для минимизации общего времени потока для версии задачи, в которой разрешено прерывание заданий. [11]
Коффман и Грэхем (1972) и Ленстра и Ринну Кан (1978) [12] утверждают, что временная сложность алгоритма Коффмана – Грэма для n -элементного частичного порядка равна O ( n 2 ) . Однако в этом анализе не учитывается время для построения транзитивной редукции, которая, как известно, не возможна в рамках этой границы. Сетхи (1976) показывает, как реализовать этап топологического упорядочения алгоритма за линейное время , основываясь на идее уточнения разбиения . [13] Сетхи также показывает, как эффективно реализовать этап присвоения уровня алгоритма, используя структуру данных с непересекающимися наборами . В частности, с версией этой структуры, опубликованной позже Gabow & Tarjan (1985) , этот этап также занимает линейное время. [14]
Рекомендации
- ^ a b c Коффман, EG, младший ; Грэхем, Р. Л. (1972), "Оптимальное планирование для систем двух процессоров" (PDF) , Acta , обработка данных , 1 : 200-213, DOI : 10.1007 / bf00288685 , МР 0334913.
- ^ а б Лам, Шуй; Сетхи, Рави (1977), " В худшем случае анализ двух алгоритмов планирования", SIAM журнал по вычислениям , 6 (3): 518-536, DOI : 10,1137 / 0206037 , МР 0496614.
- ^ а б Браски, Бертран; Trystram, Денис (1994), "Новое понимание алгоритма Коффмэны-Graham", SIAM журнал по вычислениям , 23 (3): 662-669, DOI : 10,1137 / S0097539790181889 , МР 1274650.
- ^ Люнг, Джозеф Ю.-Т. (2004), «Некоторые основные алгоритмы планирования», Справочник по планированию: алгоритмы, модели и анализ производительности , CRC Press, ISBN 978-1-58488-397-5.
- ^ Сугияма, Кодзо; Тагава, Сёдзиро; Toda, Мицухико (1981), "Методы визуального понимания иерархической структуры системы", IEEE Transactions по системам, человек, и кибернетики , SMC-11 (2): 109-125, DOI : 10,1109 / TSMC.1981.4308636 , МР 0611436.
- ^ а б в ди Баттиста, Джузеппе; Идс, Питер ; Тамассия, Роберто ; Толлис, Иоаннис Г. (1999), «Глава 9: Многослойные рисунки орграфов», Graph Drawing: Algorithms for the Visualization of Graph , Prentice Hall, pp. 265–302.
- ^ Бастерт, Оливер; Матушевский, Кристиан (2001), «Многослойные рисунки орграфов», у Кауфманна, Михаэля; Вагнер, Доротея (ред.), Рисование графиков: методы и модели , конспект лекций по информатике, 2025 г. , Springer-Verlag, стр. 87–120, doi : 10.1007 / 3-540-44969-8_5. Бастерт и Матушевски также включают описание алгоритма Коффмана – Грэма; однако они опускают этап транзитивной редукции алгоритма.
- ^ Хили, Патрик; Николов, Никола С. (2002), "Как наслоить направленный ациклический граф", Рисование графа: 9-й Международный симпозиум, GD 2001, Вена, Австрия, 23–26 сентября 2001 г., Revised Papers , Lecture Notes in Computer Science, 2265 , . Springer-Verlag, стр 16-30, DOI : 10.1007 / 3-540-45848-4_2 , МР 1962416.
- ^ Muntz, RR; Коффмэно, Е. (1969), "Оптимальное упреждающее планирование на системах с двумя процессоров", IEEE Transactions на компьютерах , 18 : 1014-1020, DOI : 10,1109 / TC.1969.222573.
- ^ Шардон, Марк; Moukrim, Азиз (2005), "Алгоритм Кофман-Graham оптимально решает задачи системы UET с overinterval заказов", SIAM журнал по дискретной математике , 19 (1): 109-121, DOI : 10,1137 / S0895480101394999 , MR 2178187.
- ^ Коффман, EG, младший ; Sethuraman, J .; Тимковский В.Г. (2003), "Идеальные преимущественные графики на двух процессорах", Acta Informatica , 39 (8): 597-612, DOI : 10.1007 / s00236-003-0119-6 , MR 1996238.
- ^ Lenstra, JK ; Rinnooy Кан, AHG (1978), "Сложность планирования под очередностью", исследование операций , 26 (1): 22-35, DOI : 10,1287 / opre.26.1.22 , ЛВП : 10338.dmlcz / 141477 , JSTOR 169889 , MR 0462553.
- ^ Sethi, Рави (1976), "Планирование графиков на двух процессорах", SIAM журнал по вычислениям , 5 (1): 73-82, DOI : 10,1137 / 0205005 , MR 0398156.
- ^ Габоу, Гарольд Н .; Тарьян, Роберт Эндре (1985), «Линейное время алгоритм для специального случая непересекающихся множества союза», журнал компьютерных и системных наук , 30 (2): 209-221, DOI : 10.1016 / 0022-0000 (85) 90014-5 , Руководство по ремонту 0801823.