Алгоритм Коффмана – Грэма - Coffman–Graham algorithm

В планирование работы цеха и рисунок графика, то Алгоритм Коффмана – Грэма является алгоритм, названный в честь Эдвард Г. Коффман-младший и Рональд Грэм, для размещения элементов частично заказанный набор в последовательность уровней. Алгоритм выбирает такую ​​компоновку, что элемент, следующий за другим в порядке, назначается на более низкий уровень, и такой, что каждый уровень имеет количество элементов, не превышающее фиксированной границы ширины. W. Когда W = 2, он использует минимально возможное количество различных уровней,[1] и в целом он использует не более 2 − 2/W раз больше уровней, чем необходимо.[2][3]

Постановка проблемы и приложения

В версии задачи планирования рабочих мест, решаемой алгоритмом Коффмана – Грэма, каждому дается набор п рабочие места J1, J2, ..., Jпвместе с системой ограничений предшествования Jя < Jj требуя этой работы Jя быть завершенным перед работой Jj начинается. Предполагается, что каждое задание занимает единицу времени для завершения. Задача планирования состоит в том, чтобы назначить каждое из этих заданий на временные интервалы в системе W идентичные процессоры, сводя к минимуму готовность задания (время от начала первого задания до завершения финального задания). В абстрактном смысле ограничения приоритета определяют частичный порядок работ, поэтому проблему можно перефразировать как одно из присвоения элементов этого частичного порядка уровням (временным интервалам) таким образом, чтобы каждый временной интервал имел не более чем столько же работ, сколько процессоры (не более W элементов на уровень), соблюдая ограничения приоритета. Это приложение послужило исходной мотивацией для Коффмана и Грэма при разработке своего алгоритма.[1][4]

в рисование многослойного графика рамки изложены Сугияма, Тагава и Тода (1981)[5] вход - это ориентированный граф, а рисунок графика строится в несколько этапов:[6][7]

  1. А набор дуги обратной связи выбрана, и края этого набора перевернуты, чтобы преобразовать вход в ориентированный ациклический граф.
  2. Вершинам графа заданы целые числа у-координаты таким образом, что для каждого ребра начальная вершина ребра имеет более высокую координату, чем конечная вершина, с не более чем W вершины разделяют то же самое у-координат.
  3. Фиктивные вершины вводятся внутри каждого ребра, так что все разделенные ребра соединяют пары вершин, которые находятся на смежных уровнях чертежа.
  4. Внутри каждой группы вершин с одинаковыми у-координатные, вершины переставлен чтобы свести к минимуму количество переходов в получившемся чертеже, а вершинам присваивается Икс-координаты согласованы с этой перестановкой.
  5. Вершины и ребра графа нарисованы с назначенными им координатами.

В этом контексте уПрисвоение координат снова включает группировку элементов частично упорядоченного множества (вершины графа с достижимость упорядочение на множестве вершин) на слои (множества вершин с одинаковыми у-координата), что является проблемой, решаемой алгоритмом Коффмана – Грэма.[6] Хотя существуют альтернативные подходы к этапу наложения слоев, чем алгоритм Коффмана – Грэма, эти альтернативы в целом либо не могут включать ограничение максимальной ширины уровня, либо полагаются на сложную целочисленное программирование процедуры.[8]

Более абстрактно, обе эти проблемы можно формализовать как проблему, в которой входные данные состоят из частично упорядоченного набора и целого числа W. Желаемый результат - это присвоение целочисленных номеров уровней элементам частично упорядоченного набора так, чтобы, если Икс < у - упорядоченная пара связанных элементов частичного порядка, номер, присвоенный Икс меньше, чем номер, присвоенный у, такое что не более W элементам присваиваются одинаковые номера, что сводит к минимуму разницу между наименьшим и наибольшим присвоенными номерами.

Алгоритм

Алгоритм Коффмана – Грэма выполняет следующие шаги.[6]

  1. Представьте частичный порядок его переходная редукция или же покрывающее отношение, ориентированный ациклический граф грамм что имеет преимущество от Икс к у в любое время Икс < у и не существует третьего элемента z частичного заказа, для которого Икс < z < у. В приложениях для рисования графов алгоритма Коффмана – Грэма результирующий ориентированный ациклический граф может не совпадать с нарисованным графом, а в приложениях планирования он может не иметь ребра для каждого ограничения приоритета ввода: в обоих случаях , транзитивная редукция удаляет лишние ребра, которые не нужны для определения частичного порядка.
  2. Построить топологический порядок из грамм в котором вершины упорядочены лексикографически по набору позиций их входящих соседей. Для этого добавляйте вершины по одной в порядок, на каждом шаге выбирая вершину v добавить так, чтобы входящие соседи v все уже являются частью частичного упорядочивания и так, что последний добавленный входящий сосед v находится раньше, чем последний добавленный входящий сосед любой другой вершины, которая может быть добавлена ​​вместо v. Если две вершины имеют одного и того же самого последнего добавленного входящего соседа, алгоритм прерывает связь в пользу той, у которой вторым последним добавленным входящим соседом является более ранний, и т. Д.
  3. Назначьте вершины грамм на уровни в порядке, обратном топологическому порядку, построенному на предыдущем шаге. Для каждой вершины v, Добавить v на уровень, который как минимум на один шаг выше, чем самый высокий уровень любого исходящего соседа v, в котором еще нет W присвоенные ему элементы, и это минимально возможное количество с учетом этих двух ограничений.

Анализ

В качестве Коффман и Грэм (1972) первоначально доказанный, их алгоритм вычисляет оптимальное назначение для W = 2; то есть для планирования задач с заданиями единичной длины на двух процессорах или для задач рисования многоуровневого графа с не более чем двумя вершинами на слой.[1] Тесно связанный алгоритм также находит оптимальное решение для планирования заданий с различной продолжительностью, позволяя отказаться от запланированных заданий на двух процессорах.[9] За W > 2, алгоритм Коффмана – Грэма использует количество уровней (или вычисляет график с периодом изготовления), который находится в пределах коэффициента 2 − 2/W оптимального.[2][3] Например, для W = 3, это означает, что он использует не более 4/3 раз больше уровней, чем оптимально. Когда ограничения частичного порядка приоритета являются интервальный порядок, или принадлежит к нескольким родственным классам частичных порядков, алгоритм Коффмана – Грэма находит решение с минимальным числом уровней независимо от его ширины.[10]

Помимо поиска расписаний с малым временем выполнения, алгоритм Коффмана-Грэма (модифицированный из презентации здесь, так что он топологически упорядочивает обратный график из грамм и размещает вершины как можно раньше, а не как можно позже) минимизирует общее время потока двухпроцессорных расписаний - сумма времени выполнения отдельных заданий. Связанный алгоритм может использоваться для минимизации общего времени потока для версии задачи, в которой разрешено прерывание заданий.[11]

Коффман и Грэм (1972) и Ленстра и Риннуй Кан (1978)[12] указать временную сложность алгоритма Коффмана – Грэма на п-элемент частичного порядка, чтобы быть О(п2). Однако в этом анализе не учитывается время для построения транзитивной редукции, которая, как известно, не возможна в рамках этой границы. Сетхи (1976) показывает, как реализовать этап топологического упорядочивания алгоритма в линейное время, основанный на идее уточнение раздела.[13] Сетхи также показывает, как эффективно реализовать этап назначения уровня алгоритма с помощью непересекающаяся структура данных. В частности, с версией этой структуры, опубликованной позже Габоу и Тарджан (1985), этот этап также занимает линейное время.[14]

Рекомендации

  1. ^ а б c Коффман, Э. Г., мл.; Грэм, Р. Л. (1972), «Оптимальное планирование для двухпроцессорных систем» (PDF), Acta Informatica, 1: 200–213, Дои:10.1007 / bf00288685, МИСТЕР  0334913.
  2. ^ а б Лам, Шуй; Сетхи, Рави (1977), "Анализ наихудшего случая двух алгоритмов планирования", SIAM Журнал по вычислениям, 6 (3): 518–536, Дои:10.1137/0206037, МИСТЕР  0496614.
  3. ^ а б Браски, Бертран; Тристрам, Денис (1994), "Новое понимание алгоритма Коффмана-Грэма", SIAM Журнал по вычислениям, 23 (3): 662–669, Дои:10.1137 / S0097539790181889, МИСТЕР  1274650.
  4. ^ Люнг, Джозеф Ю.-Т. (2004 г.), «Некоторые основные алгоритмы планирования», Справочник по планированию: алгоритмы, модели и анализ производительности, CRC Press, ISBN  978-1-58488-397-5.
  5. ^ Сугияма, Кодзо; Тагава, Сёдзиро; Тода, Мицухико (1981), "Методы визуального понимания структур иерархических систем", IEEE Transactions по системам, человеку и кибернетике, СМЦ-11 (2): 109–125, Дои:10.1109 / TSMC.1981.4308636, МИСТЕР  0611436.
  6. ^ а б c ди Баттиста, Джузеппе; Идс, Питер; Тамассия, Роберто; Толлис, Иоаннис Г. (1999), "Глава 9: Многослойные рисунки орграфов", Рисование графиков: алгоритмы визуализации графиков, Prentice Hall, стр. 265–302..
  7. ^ Бастерт, Оливер; Матушевский, Кристиан (2001), «Многослойные рисунки диграфов», у Кауфманна, Михаэля; Вагнер, Доротея (ред.), Графики рисования: методы и модели, Конспект лекций по информатике, 2025, Springer-Verlag, стр. 87–120, Дои:10.1007/3-540-44969-8_5. Бастерт и Матушевски также включают описание алгоритма Коффмана – Грэма; однако они опускают этап транзитивной редукции алгоритма.
  8. ^ Хили, Патрик; Николов, Никола С. (2002), "Как наслоить ориентированный ациклический граф", Графический рисунок: 9-й Международный симпозиум, GD 2001 Вена, Австрия, 23–26 сентября 2001 г., Исправленные статьи, Конспект лекций по информатике, 2265, Springer-Verlag, стр. 16–30, Дои:10.1007/3-540-45848-4_2, МИСТЕР  1962416.
  9. ^ Muntz, R. R .; Коффман, Э. (1969), «Оптимальное упреждающее планирование в двухпроцессорных системах», Транзакции IEEE на компьютерах, 18: 1014–1020, Дои:10.1109 / T-C.1969.222573.
  10. ^ Шардон, Марк; Мукрим, Азиз (2005), "Алгоритм Коффмана-Грэма оптимально решает системы задач UET с порядками, превышающими интервалы", Журнал SIAM по дискретной математике, 19 (1): 109–121, Дои:10.1137 / S0895480101394999, МИСТЕР  2178187.
  11. ^ Коффман, Э. Г., мл.; Sethuraman, J .; Тимковский, В. Г. (2003), "Идеальные схемы с вытеснением на двух процессорах", Acta Informatica, 39 (8): 597–612, Дои:10.1007 / s00236-003-0119-6, МИСТЕР  1996238.
  12. ^ Ленстра, Дж. К.; Риннуй Кан, А. Х. Г. (1978), «Сложность планирования при ограничениях приоритета», Исследование операций, 26 (1): 22–35, Дои:10.1287 / opre.26.1.22, HDL:10338.dmlcz / 141477, JSTOR  169889, МИСТЕР  0462553.
  13. ^ Сетхи, Рави (1976), "Планирование графиков на двух процессорах", SIAM Журнал по вычислениям, 5 (1): 73–82, Дои:10.1137/0205005, МИСТЕР  0398156.
  14. ^ Габоу, Гарольд Н .; Тарджан, Роберт Эндре (1985), "Алгоритм линейного времени для частного случая несвязного объединения множеств", Журнал компьютерных и системных наук, 30 (2): 209–221, Дои:10.1016/0022-0000(85)90014-5, МИСТЕР  0801823.