Критический путь в графе

Критический путь в графе

Задача нахождения критического, (т. е. длиннейшего) пути в графе ― это задача, связанная с загрузкой станочного оборудования, сборки многозвенных изделий и т. д.

Сетевой график – необходимый элемент сложного производства, состоящего из нескольких связанных и зависящих друг от друга этапов. Выявление критического пути и временных резервов производства – основная задача, решаемая построением сетевого графика. Такие задачи могут быть представлены в виде графа и в виде отображающей его таблицы. Для нахождения критического пути (последовательности этапов работы, определяющих длительность всего проекта и не имеющих резерва по времени) применяются вычислительные методы. Одним из таких методов является табличный метод и применяется для данных, представленных в виде таблицы.

Проблема автоматизации расчёта сетевого графика является достаточно актуальной и важной. Вычисление критического пути с помощью ЭВМ поможет в несколько раз ускорить этот процесс, а при больших графиках – во много раз. Поэтому автоматизация расчёта сетевого графика может иметь большую практическую пользу.

Алгоритм нахождения длиннейшего пути в графе похож на алгоритм нахождения кротчайшего пути в графе (алгоритм Дикстры). Вместо кротчайших ребер в алгоритме нахождения кратчайшего пути выбираются длиннейшие.

Цели решения задачи

• Вычисление времени раннего начала работ каждого вида – минимального срока начала работы, считая от начала проекта.

• Вычисление времени раннего завершения работ каждого вида – минимального срока завершения работы, считая от начала проекта.

• Вычисление времени позднего начала работ каждого вида

– максимального срока начала работы, считая от начала проекта.

• Вычисление времени позднего завершения работ каждого вида – максимального срока завершения работы, считая от начала проекта.

• Вычисление полного резерва работ каждого вида – максимального запаса времени, на которое можно отсрочить начало работы.

Задача

Требуется найти такой путь на графе, который бы имел максимальную длину по сравнению со всеми возможными путями для данного графа.

Пусть существует ориентированный граф без циклов G.

Рёбра графа — выполнение работы. Рёбра имеют длину, обозначающую продолжительность работы и направление, обозначающее последовательность выполнение работы. Вершины — это факт начала и окончания работ.

(1, 3) — ребро с весом (длительностью работы) 6. 1 — начало работы. 3 — конец работы.

Ребро (2, 4) — фиктивная работа нулевой длительности.

— наиболее ранний срок начала работы для вершины.

— наиболее ранний срок окончания работы.

— максимальное время задержки между выполнениями работ.

Пример . Выполняется комплекс работ. Заданы работы (i, j), длительность их выполнения tij. В процессе решения необходимо:

  1. Составить экономическое содержание задачи и перечислить перечень работ.
  2. Построить сетевой график и определить критический путь.
  3. Рассчитать параметры сетевого графика и поздние сроки поступления событий, резервы времени.

Решение находим с помощью калькулятора.
Все вычисления будем заносить в таблицу.
Перечень работ и их продолжительность перенесем во вторую и третью графы. При этом работы следует записывать в графу 2 последовательно: сначала начиная с номера 1, затем с номера 2 и т.д.
Во второй графе поставим число, характеризующее количество непосредственно предшествующих работ (КПР) тому событию, с которого начинается рассматриваемая работа.
Так, для работы (3,4) в графу 1 поставим число 2, т.к. на номер 3 оканчиваются 2 работы: (1,3),(2,3).
Далее заполняем графы 4 и 5. Для работ, имеющих цифру 0 в графе 2, в графу 4 также заносятся нули, а их значения в графе 5 получаются в результате суммирования граф 3 и 4.
Для заполнения следующих строк графы 4, т.е. строк начиная с номера 2, просматриваются заполненные строки графы 5, содержащие работы, которые оканчиваются на этот номер, и максимальное значение переносится в графу 4 обрабатываемых строк.
Этот процесс повторяется до тех пор, пока не будет заполнена последняя строка таблицы.
Заполнение графы 4.
Рассмотрим события: (1,2): 3. Заносим значение 3 в графу.
Рассмотрим события: (1,3): 6;(2,3): 5. Максимальное значение: 6. Заносим его в графу.
Рассмотрим события: (1,4): 4;(3,4): 13. Максимальное значение: 13. Заносим его в графу.
Рассмотрим события: (2,5): 8;(3,5): 10. Максимальное значение: 10. Заносим его в графу.
Графы 6 и 7 заполняются обратным ходом, т.е. снизу вверх. Для этого просматриваются строки, оканчивающиеся на номер последнего события, и из графы 5 выбирается максимальная величина, которая записывается в графу 7 по всем строчкам, оканчивающимся на номер последнего события (т.к. tр(i)= tп(i)).
Процесс повторяется до тех пор, пока не будут заполнены все строчки по графам 6 и 7.
Заполнение графы 7.
Рассмотрим события:
(3,6): 10
(4,6): 19
(5,6): 12
Максимальное значение: 19. Записываем его в графу 7 по всем строчкам, оканчивающимся на номер последнего события 6.
Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 5. Для определения графы 7 этих строк просматриваются все строчки, начинающиеся с номера 5.
(5,6): 19 — 2 = 17;
Данное значение переносится в графу 7 по обрабатываемым строчкам.. В нашем случае это значение: 17.
Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 4. Для определения графы 7 этих строк просматриваются все строчки, начинающиеся с номера 4.
(4,6): 19 — 6 = 13;
Данное значение переносится в графу 7 по обрабатываемым строчкам.. В нашем случае это значение: 13.
Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 5. Для определения графы 7 этих строк просматриваются все строчки, начинающиеся с номера 5.
(5,6): 19 — 2 = 17;
Данное значение переносится в графу 7 по обрабатываемым строчкам.. В нашем случае это значение: 17.
Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 3. Для определения графы 7 этих строк просматриваются все строчки, начинающиеся с номера 3.
(3,4): 13 — 7 = 6;
(3,5): 17 — 4 = 13;
(3,6): 19 — 4 = 15;
В графу 6 среди них выбирается минимальная величина, которая переносится в графу 7 по обрабатываемым строчкам.. В нашем случае это значение: 6.
Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 4. Для определения графы 7 этих строк просматриваются все строчки, начинающиеся с номера 4.
(4,6): 19 — 6 = 13;
Данное значение переносится в графу 7 по обрабатываемым строчкам.. В нашем случае это значение: 13.
Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 3. Для определения графы 7 этих строк просматриваются все строчки, начинающиеся с номера 3.
(3,4): 13 — 7 = 6;
(3,5): 17 — 4 = 13;
(3,6): 19 — 4 = 15;
В графу 6 среди них выбирается минимальная величина, которая переносится в графу 7 по обрабатываемым строчкам.. В нашем случае это значение: 6.
Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 2. Для определения графы 7 этих строк просматриваются все строчки, начинающиеся с номера 2.
(2,3): 6 — 2 = 4;
(2,5): 17 — 5 = 12;
В графу 6 среди них выбирается минимальная величина, которая переносится в графу 7 по обрабатываемым строчкам.. В нашем случае это значение: 4.
Содержимое графы 8 равно разности граф 6 и 4 или граф 7 и 5.

Читайте также:  Программа для фитнес браслета хуавей
Работа (i,j) Количество предшествующих работ Продолжительность tij Ранние сроки: начало tij Р.Н. Ранние сроки: окончание tij Р.О. Поздние сроки: начало tij П.Н. Поздние сроки:окончание tij П.О. Резервы времени: полный tij П Резервы времени: свободный tij С.В. Резервы времени: событий Rj
(1,2) 3 3 1 4 1 1
(1,3) 6 6 6
(1,4) 4 4 9 13 9 9
(2,3) 1 2 3 5 4 6 1 1
(2,5) 1 5 3 8 12 17 9 2 7
(3,4) 2 7 6 13 6 13
(3,5) 2 4 6 10 13 17 7 7
(3,6) 2 4 6 10 15 19 9 9
(4,6) 2 6 13 19 13 19
(5,6) 2 2 10 12 17 19 7 7

Пример . Рассчитать параметры сетевого графика мероприятия по совершенствованию системы управления. Сетевая модель задана таблично. Продолжительность выполнения работ дана в виде минимальной и максимальной оценок. Требуется вычислить табличным методом все основные характеристики работ и событий, найти критический путь и его продолжительность.
Скачать

Суть алгоритма заключается в определении минимально возможного и максимально возможного времени начала выполнения узлов графа. В разработанных моделях используется следующий алгоритм определения критических путей (КП) в графе со взвешенными узлами и дугами, то есть с учетом времен обработки узлов графа задачи и передачи данных между узлами графа. Данный алгоритм, аналогично соответствующему алгоритму для графа без учета времени передачи по магистрали, основан на последовательном проходе по дереву графа от начальной вершины (вершин) к конечной и возврата к начальной вершине. При начальном проходе (рис. 1) определяется минимально возможное время начала выполнения каждого узла по формуле:

где s — число узлов-предшественников i-го узла;

Tmin i (j) — минимально возможное время начала выполнения i-го (j-го) узла;

t j — время выполнения j -го узла;

T ji — время передачи данных между узлами j и i, которому присваивается одно из значений множества <0, jiь 2ji > в зависимости от способа организации памяти, где ji — время передачи данных между узлами j и i, задаваемое на исходном графе задачи.

Читайте также:  Как поставить процент зарядки на андроиде

Рис. 1. Пояснения к определению критических узлов

При повторном анализе графа при проходе от конечной вершины к начальной определяется максимально возможное время начала выполнения узла по формуле

где v — число узлов-последователей i-го узла;

Tmax i (r) — максимально возможное время начала выполнения i-го (r-го) узла;

t i — время выполнения i-ro узла;

Tir — время передачи данных i-го узла узлу r, значение которому присваивается аналогично T ij

При этом для начальной вершины (вершин) Tmin i = 0, а для конечной вершины минимально возможное время начала ее выполнения совпадает с максимально возможным временем начала выполнения — Tmax i = Tmin i.

Критическим путем графа является множество последовательных узлов, начинающихся входной вершиной и заканчивающихся выходной вершиной, удовлетворяющих условию Tmax i = Tmin i, причем для каждой пары узлов принадлежащих КП соотношения (1) и (2) определяются соседней вершиной в паре.

Длина критического пути определяет минимальное возможное время выполнения графа задачи на МВС.

Граф задачи при выполнении ее на МВС с различной организацией может иметь различные критические пути вследствие изменения времени передач между узлами. Последнее определяется способом организации памяти. Например, в МВС только с общей памятью (без локальной памяти процессоров) при определении критического пути время передачи данных от j-ro узла i-му и от i-го узла r-му необходимо удваивать. Двойной учет этого времени происходит потому, что при передаче данных, во-первых, необходимо время ji, чтобы передать данные j-ro узла в общую память, и, во-вторых, время ji чтобы забрать данные из общей памяти и передать i -му узлу, даже в случае выполнения i -го и j -го узлов в одном процессоре. В МВС с распределенной памятью каждый процессор имеет локальную память, в которой могут храниться промежуточные результаты. При этом если узлы j и i обрабатываются одним процессором, то время обмена между ними считается равным 0 (то есть Tij = 0), если разными, то время обмена между узлами равно ji. Выполнение этих дополнительных условий должно учитываться при решении задачи назначения.

Рассмотрим пример поиска критического пути для графа задачи без учета времен передач (рис. 2). Цифра внутри каждого кружка (узел графа) — номер узла, цифра над кружком — время выполнения узла tj. Дуги графа не взвешены, следовательно, T ji = T ir = 0.

Основным допущением при поиске КП на графе является следующее; граф задачи реализуется на системе с неограниченными ресурсами, в данном случае на МВС с неограниченным числом процессоров.

Рис. 2. Определение критического пути для графа задачи без учета передач

При движении по графу от начальной вершины к конечной слева от узла записывается минимально возможное время начала выполнения этого узла Tmin i. Например, узел 6-может начать выполняться, когда выполнятся 2 и 3 узлы. Тогда Tmin 6 = 7, так как минимально возможное время начала выполнения 6-го узла является максимальным из времен окончания 2-го (Tmin 2 + t 2) и 3-го (Tmin 3 + t 3) узлов.

При движении по графу назад от конечной вершины к первой, справа от узла записывается максимально возможное время начала выполнения этого узла Tmax i . Например, для узла 2 по формуле (2) находим

Таким образом, для графа, изображенного на рис.2, имеются два критических пути: и . При этом путь не является критическим, в частности, потому что для пары узлов 2 и 9 соотношения (1) и (2) не определяются соседним в паре узлом. Например, Tmin 9 определяется не узлом 2, а узлом 6, аналогично и Tmax 2 не определяется узлом 9 , т.е.

Следовательно, для данной прикладной задачи Tmin = 23, Тmах = 48.

Рассмотрим теперь пример определения КП для графа среднесвязанной задачи с учетом передач (рис. 3). Дуги графа задачи взвешены числами, соответствующими временам занятости шины.

Поиск критического пути на графе, а следовательно, и минимального времени его выполнения с учетом времени передач данных от узла к узлу, в общем случае, сводится к задаче полного перебора. Тем не менее, вводя ряд ограничений на условие передачи данных, а они связаны с организацией обменов между процессорами и памятью, можно предложить алгоритмы, сокращающие полный перебор и дающие искомый результат.

Сделаем следующие допущения.

Граф задачи реализуется на системе с неограниченными ресурсами.

Каждый узел графа может передавать данные по всем выходящим ветвям параллельно и принимать данные по всем входящим ветвям параллельно.

При этих условиях Tmin определяется, как было указано выше, в зависимости от способа организации памяти, поскольку этим, в частности, определяются времена передачи между узлами.

Читайте также:  Всегда использовать gpu для композиции экрана

Для случая МВС с общей памятью времена передачи данных удваиваются.

Рассматривая рис. 3, можно сделать вывод, что критический путь графа с учетом передач изменился — , а Tтin = 46.

Рис. 3. Определение критического пути для графа задачи с учетом передач на МВС с общей памятью

Рассмотрим теперь алгоритм поиска КП для графа задачи с учетом передач на МВС с распределенной памятью (рис. 4). Отметим, что рассматриваемая задача аналогична задаче, граф которой приведен на рис.3. Следует обратить внимание на то, что целью вычисления КП при реализации задачи на МВС с распределенной памятью является определение среди узлов-последователей (r=1. v) (см. рис. 1) узла, который назначается на процессор, выполняющий узел-предшественник. В этом случае данные от узла-предшественника не передаются узлу-последователю (Тjr приравнивается к нулю).

Следующие допущения являются основными при реализации графа задачи на МВС с распределенной памятью.

Граф реализуется на системе с неограниченными ресурсами.

От каждого узла графа данные могут передаваться параллельно по исходящим ветвям.

Каждый узел графа может принимать данные параллельно по входящим ветвям.

Каждый узел графа может иметь не больше одной входящей и не больше одной исходящей ветви, времени передачи по которой в результате поиска КП присваивается значение равное нулю.

Алгоритм определения КП для графа задачи, выполняемой на МВС с распределенной памятью, состоит в том, что при вычислении по формуле (1) минимально возможного времени начала выполнения i-гo узла Тmin i определяется одна из входящих в него ветвей, времени передачи по которой присваивается значение равное нулю. При этом это должна быть такая ветвь, которая вносит максимальный эффект в уменьшении Тmin i.

Рис. 4. Определение критического пути для графа задачи с учетом передач на МВС с распределенной памятью

Очевидно, что не всегда с первой же попытки можно определить Тmin i. Например, определив ветвь di, входящую в i-й узел, обуславливающую Тmin i необходимо провести анализ узла d, из которого исходит эта ветвь. Если у этого узла уже есть одна исходящая ветвь, которой присвоено значение Tdk=0 (т.е. определен k-й узел — последователь d-гo узла, и, следовательно, процессор оставил необходимые данные для выполнения к-го узла в своей локальной памяти), то ветвь di из рассмотрения исключается. Находится следующая по значению эффективности ветвь, входящая в i-й узел и т.д.

Если у d-гo узла нет исходящей ветви, которой присвоено значение равное нулю, то для этого d-гo узла определяется присутствие такой ветви, у которой dk > di. Если такая ветвь есть, то i-й узел исключается из рассмотрения до тех пор, пока не будет принято решение о присвоении или не присвоении ветви dk значения Tdk=0. Если такой ветви нет, то Tdi присваивается значение, равное нулю, и уже с учетом этого определяется Тmin i.

Следует обратить внимание на следующее. Если k-й узел расположен на более низком ярусе графа чем i-й узел, то при нахождении Tmin k анализируются все пути от вершины d к вершине к, а значение 0 может быть присвоено ( или не присвоено) в соответствии с правилами, изложенными выше для узла i, одной из ветвей, исходящих из узла d (необязательно для ветви dk).

Максимально возможное время начала выполнения узла Тmax i вычисляется по формуле (2) при обратном движении по графу уже с учетом определенных выше нулевых ветвей. Данные ветви помечены на рис. 4 стрелкой (например, 30). В приведенном примере граф задачи имеет единственный КП 1-4-10-11—12, длина которого равна Тmin =27.

Из рассмотренных примеров видно, что длина критического пути (Тmin) является основным параметром, характеризующим информационно-логическую структуру вычислительного процесса (ВП), реализующего решение заданной прикладной задачи. В случае учета времени передачи данных от одного узла к другому при решении задачи в МВС с ограниченными ресурсами, значение минимального времени ее выполнения увеличивается и определяется характеристиками реальной структуры МВС. Очевидно, что это увеличение будет тем меньше, чем удачнее распределены узлы графа по процессорам МВС.

Таким образом, возникает задача построения оптимального расписания (назначения готовых к исполнению узлов ВП на свободные процессоры).

Ссылка на основную публикацию
Крепление к мокрому фасаду
Система «мокрого» фасада была разработана в 50-х годах 20 века в Германии. Оригинальное название WDVS (Wärmedämmverbundsystem) или система термоизоляции. В...
Компьютер не видит принтер кэнон
Практически каждый из нас может сталкиваться с такой проблемой, когда компьютер вдруг перестает видеть принтер, а иногда компьютер не видит...
Компьютер не видит радар детектор sho me
Проверьте, что устройство подключено. А как? Один из часто возникающих вопросов: «Всё настроено, как описано, но не видит радара, пишет...
Крепление телевизора на стену своими руками чертежи
Одним из вариантов размещения плоских телевизоров является их крепление на стену. Такое решение позволяет сэкономить место, при этом все выглядит...
Adblock detector