Метод критического пути

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

Исходными данными являются только длительности отдельных работ комплекса и последовательность их запуска. Последняя графически задается в виде ориентированного графа, где дугами графа обозначается место работы в комплексе, а вершинами — события, моменты начала и окончания работ (рис. 4.13).

Графическое представление работы

Рис. 4.13. Графическое представление работы

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

События, определяющие последовательность выполнения работ

Рис. 4.14. События, определяющие последовательность выполнения работ

Существует хотя бы одна работа, событие начала которой не совпадает с событием окончания любой другой работы в заданном комплексе работ. Это начальное событие всего комплекса работ. Все такие работы имеют совпадающие события своего начала.

Существует хотя бы одна работа, событие окончания которой не совпадает с событием начала любой другой работы в заданном комплексе работ. Это конечное событие всего комплекса работ. Все такие работы имеют совпадающие события своего окончания.

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

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

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

Часть графа описания последовательности выполнения работ

Рис. 4.15. Часть графа описания последовательности выполнения работ

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

Фиктивная работа

Рис. 4.16. Фиктивная работа

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

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

Последовательный граф

Рис. 4.17. Последовательный граф

Если обрабатывается партия деталей (возможно, разных), когда имеется возможность последовательной обработки каждой детали на отдельной технологической линии параллельно с обработкой других деталей, то граф описания комплекса работ будет последовательно-параллельным (рис. 4.18). Этот граф можно рассматривать как совокупность последовательных графов. Выбирая последовательный граф с максимальным временем выполнения его работ, можно определить время выполнения всего комплекса работ.

Последовательно-параллельный граф

Рис. 4.18. Последовательно-параллельный граф

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

Последовательная смесь графов

Рис. 4.19. Последовательная смесь графов

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

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

Граф комплекса из восьми работ

Рис. 4.20. Граф комплекса из восьми работ

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

Предварительный этап методики заключается в присвоении каждому событию комплекса работ порядкового номера. Обычно нумерация осуществляется естественным образом, в порядке возрастания. Если рассматривать граф комплекса работ не как сеть работ, а как сеть событий, то номер предшествующего события всегда меньше номера последующего события. Это называется естественной нумерацией событий. Используя нумерацию событий для идентификации работ комплекса (указывая номера события начала и события окончания работы), можно получить естественную нумерацию работ. Нумерация событий и работ необходима для их идентификации при проведении расчетов, особенно в матричной форме. Естественность нумерации не является обязательным условием применения метода критического пути и влияет только на порядок перебора событий и на форму матрицы длительности работ, которая будет построена в численном примере. Нумерация может начинаться с любого номера, но обычно это 1.

Алгоритм индексации событий является итерационным, поэтому рассмотрим только одну отдельную итерацию. Процедура нумерации событий связана с осуществленными событиями, когда выполнены все работы, имеющие это событие как событие своего окончания. Алгоритм индексации строится на последовательном выполнении (имитационном) работ, и нумерацию получают только осуществленные события. Предположим, что к этой итерации уже пронумерованы первые i событий. Следует отметить, что в начале индексации существует событие, которое уже осуществлено к этому моменту. Это начальное событие комплекса работ.

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

Алгоритм заканчивается, когда будет присвоен номер для конечного события комплекса работ.

Рассмотрим граф, приведенный на рис. 4.20. Здесь сразу можно пронумеровать начальную вершину.

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

Граф комплекса работ после первой итерации

Рис. 4.21. Граф комплекса работ после первой итерации

На второй итерации вычеркиваем четыре дуги, исходящие из вершин 2 и 3 (рис. 4.22). Появляется вершина без входящих работ, соответствующая осуществленному событию, которой присваиваем очередной индекс 4.

Граф комплекса работ после второй итерации

Рис. 4.22. Граф комплекса работ после второй итерации

Результат полной индексации приведен на рис. 4.23.

Граф комплекса с индексированными вершинами

Рис. 4.23. Граф комплекса с индексированными вершинами

Для формального описания метода критического пути введем следующие обозначения:

  • Uf — множество событий, которые являются событиями начала всех работ, имеющих событием окончания событие i;
  • Uj — множество событий, которые являются событиями начала всех работ, имеющих событием окончания событие j.

Эти множества наглядно представлены на рис. 4.24.

Графическое представление множеств U[ и Uj

Рис. 4.24. Графическое представление множеств U[ и Uj

Длина критического пути складывается из длительностей работ, входящих в критический путь. Определив множество работ, входящих в критический путь, можно определить длину критического пути и время, необходимое для выполнения всего комплекса работ. Известны длительности всех работ комплекса. Пусть т^ — длительность работы, имеющей индексы событий начала и окончания ij.

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

Пусть tj — наиболее ранний момент времени, при котором возможно осуществление события j = 1, ..., Р. Наиболее рационально предположить, что ранний момент времени осуществления комплекса в целом совпадает с моментом времени осуществления конечного события tp, т.е. это момент времени окончания выполнения последней работы и комплекса работ в целом. Задавая значение наиболее раннего момента осуществления начального события комплекса работ tx, можно определить время выполнения всего комплекса работ как tP- t{.

Определение величин tp j = 1,Р, начинается с известного значения t{. Пусть tx = 0. Тогда можно использовать рекуррентные соотношения

Эти рекуррентные соотношения формально описывают определение осуществленного события, приведенное ранее, и указывают на необходимость завершения всех работ, имеющих событие, для которого рассчитывается этот временной показатель, как событие окончания работы. На рис. 4.25 приведено графическое описание применимости приведенных рекуррентных соотношений. Событие j является событием окончания четырех работ, которые имеют событием начала работы события ц, i2, г3, i4. Для этих событий известны рассчитанные ранее наиболее ранние моменты времени. Работы, имеющие эти события событиями начала работы, могут начать выполняться с этих моментов времени.

Определение наиболее раннего момента осуществления события j

Рис. 4.25. Определение наиболее раннего момента осуществления события j

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

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

Пусть t* — наиболее поздний момент осуществления события г, при котором сохраняется возможность выполнения всего комплекса за наименьшее время tP. Исходя из рационального предположения t*p = tp, для расчета наиболее поздних моментов осуществления других событий комплекса работ можно предложить следующее рекуррентное соотношение:

Событие i должно совершиться не позже момента ?*, когда должна начаться самая длинная цепочка работ, исходящая из рассматриваемого события, чтобы завершиться в момент tP.

На рис. 4.26 приведено графическое описание расчета наиболее позднего момента осуществления события г, которое является событием начала четырех работ с событиями окончания Наиболее поздние моменты

этих работ известны. Рассматриваемые работы должны быть выполнены до этих моментов времени.

Определение наиболее раннего момента осуществления события i

Рис. 4.26. Определение наиболее раннего момента осуществления события i

Величины ti, t*, i = l,...,P, позволяют рассчитать предельные резервы времени выполнения по каждой работе (/, j), увеличение длительности которой в пределах найденного значения не приводит к увеличению длины критического пути (но может измениться множество работ, входящих в критический путь). Можно утверждать, что выполнение работы (ij) может начаться нс раньше tx и должно закончиться не позже ?*, т.е. эта работа должна выполниться в течение промежутка времени t* -tx. Резерв времени, на который может увеличиться длительность выполнения работы без увеличения времени выполнения всего комплекса работ, равен

Работы, лежащие на критическом пути, не имеют резерва времени (Tjj =0), т.е. ресурс времени совпадает с продолжительностью выполнения работ (тij = t* -tt). События, лежащие на критическом пути, обладают свойством tj = t*.

Обратите внимание!

Длина критического пути совпадает с длиной максимального полного пути.

Длина критического пути совпадает с временем, минимально необходимым для выполнения комплекса работ.

Пример 4.1

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

Граф комплекса работ для примера 4.1

Рис. 4.27. Граф комплекса работ для примера 4.1

Таблица 4.4

Длительности работ комплекса

Работа

Длительность

1

11

2

5

3

4

4

8

5

7

6

10

7

3

8

5

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

При расчете наиболее раннего момента времени осуществления события необходимо, чтобы к этому моменту были известны эти значения для всех предшествующих событий. Поэтому сначала мы можем определить наиболее ранний момент осуществления события только для события 2 (рис. 4.28). Только потом — для событий 3, 4 и остальных (рис. 4.29).

Начало расчета наиболее ранних моментов осуществления событий на графе комплекса работ (для события 2)

Рис. 4.28. Начало расчета наиболее ранних моментов осуществления событий на графе комплекса работ (для события 2)

Расчет наиболее ранних моментов осуществления событий на графе

Рис. 4.29. Расчет наиболее ранних моментов осуществления событий на графе

комплекса работ (события 3 и 4)

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

Длина критического пути совпадает с наиболее ранним моментом осуществления конечного события комплекса работ: вершина 5, значение 16. Рационально предполагая, что временные характеристики конечного события совпадают, рассчитаем наиболее поздние моменты осуществления всех остальных событий комплекса работ. В отличие от расчета наиболее ранних моментов осуществления событий, где последовательность расчетов осуществляется от начального события комплекса работ к конечному событию, последовательность расчета наиболее поздних моментов осуществляется от конечного события к начальному. Сначала можно рассчитать значения для событий 3 и 4 (рис. 4.30), только потом — для события 2 и остальных (рис. 4.31). Для расчета наиболее поздних моментов осуществления события необходимо иметь рассчитанные значения для всех непосредственно последующих событий из множества UJ.

Начало расчета наиболее поздних моментов осуществления событий на графе комплекса работ (события 3 и 4)

Рис. 4.30. Начало расчета наиболее поздних моментов осуществления событий на графе комплекса работ (события 3 и 4)

Расчет наиболее поздних моментов осуществления событий

Рис. 4.31. Расчет наиболее поздних моментов осуществления событий

на графе комплекса работ

Результаты расчета резервов времени работ комплекса представлены на рис. 4.32. Здесь последовательность расчетов не играет существенной роли.

Расчет резервов времени работ на графе комплекса работ

Рис. 4.32. Расчет резервов времени работ на графе комплекса работ

Результаты, представленные на рис. 4.32, позволяют выделить работы, лежащие на критическом пути: 4—7—8. У этих работ нулевые резервы времени.

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

Графическая форма метода является наглядным инструментом решения поставленной задачи. Но в задачах большой размерности практичнее использовать матричную форму реализации метода критического пути.

Комплекс работ задается квадратной матрицей с размерностью, совпадающей с количеством вершин графа (табл. 4.5). В матрице указываются длительности работ на перенесении строки с номером события начала работы и столбца с номером события окончания работы. Естественная нумерация событий и работ позволяет получать треугольную матрицу с непустыми ячейками над главной диагональю. Непустыми должны быть и ячейки для работ с нулевой длительностью.

Таблица 4.5

Матричная форма задания комплекса работ для данных примера 4.1

События

События

1

2

3

4

5

1

8

11

10

2

4

3

7

3

5

4

5

5

К матрице комплекса работ добавляется столбец с рассчитываемыми значениями наиболее ранних моментов осуществления событий, совпадающих по номеру с номером соотвествующей строки матрицы (табл. 4.6). Значение первого элемента — 0.

Пунктирной линией выделены значения, которые используются в рекуррентных соотношениях (4.1) для расчета наиболее раннего момента осуществления события 4. Это столбец 4 матрицы с длительностями работ, для которых событие 4 является событием окончания работ, и столбец со значениями наиболее ранних моментов осуществления событий, предшествующих (меньше по номеру) событию 4. Пустые ячейки выделенного столбца матрицы и соответственно столбца наиболее ранних моментов не участвуют в процедуре, так как таких работ нет.

Таблица 4.6

Расчет наиболее ранних моментов осуществления событий комплекса работ (событие 4)

Строка наиболее поздних моментов осуществления событий добавляется снизу к матрице длительностей работ (табл. 4.7). Значения строки соответствуют моментам событий по номеру элемента (номеру столбца). Последний элемент строки наиболее поздних моментов осуществления событий равен но значению последнему элементу столбца наиболее ранних моментов осуществления событий. Пунктирной линией выделены элементы, которые необходимы для расчета наиболее позднего момента осуществления события 2 в соответствии с рекуррентными соотношениями (4.2). Это строка 2 матрицы с длительностями работ, для которых событие 2 является событием начала, и значения наиболее поздних моментов осуществления событий, последующих рассчитываемому событию. Пустые ячейки выделенной строки матрицы и соответственно строки наиболее ранних моментов не участвуют в процедуре, так как таких работ нет.

Таблица 4.7

Расчет наиболее поздних моментов осуществления событий комплекса работ (событие 2)

Матрица резервов времени работ комплекса организована аналогично матрице длительностей и добавляется снизу к уже имеющемуся построению (табл. 4.8). Порядок расчета несущественен. Пунктирной линией выделены элементы матрицы длительностей работ, столбца наиболее ранних моментов и строки наиболее поздних моментов осуществления событий, необходимых для расчета в соответствии с формулой (4.3) резервов времени работы с событием начала 2 и событием окончания 4. Это работа с номером 7.

Таблица 4.8

Расчет резервов времени комплекса работ

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

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

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

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

  • [1] В качестве одной из первых реализаций алгоритма еще на алгоритмическом языкеАЛГОЛ можно привести работу: Романовский И. В. Вычисление ранних начал в сетевом графике // Алгол-процедуры. 1971. № 7.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >