Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Метод оценки и проверки планов (PER T) и метод критического пути (CPM) были разработаны в 1950–х годах для управления сложными проектами. CPM появился в 1957 г. для организации строительства и ремонта химических заводов Дюпона. PER T разрабатывался независимо для нужд военно-морского флота и появился в 1958 г.
Алгоритм методов CPM и PER T:
1) определить основные работы по проекту и их продолжительность;
2) установить связи между работами;
3) вычертить сеть, содержащую все работы;
4) рассчитать критический путь (самый продолжительный).
Главное различие в методах состоит в том, что в CPM продолжительность работы детерминированная величина, а в PER T – случайная.
В PER T используется три временных оценки для каждой работы: пессимистическая (t п), наиболее вероятная (t нв) и оптимистическая (t о). Тогда ожидаемая продолжительность работы определяется как:
.
Отклонение времени выполнения работы:
.
Сетевой график (сеть) состоит из дуг и узлов (вершин). Дуге соответствует выполняемая работа (обозначается стрелкой); вершине – событие, то есть состояние перед и после работы (обозначается кружком).
Исходные данные, необходимые для составления сети, представляют в форме таблицы, которая включает последовательность работ и продолжительность выполнения каждой работы (табл. 4.7).
Таблица 4.7
Работа | Содержание работы | Следует после работ | Продолжительность | Обозначение |
a1 a2 a3 a4 a5 | Закупка и доставка оборудования Разработка технологии Монтаж и наладка оборудования Обучение рабочих–операторов Пуск линии в эксплуатацию | – – a1 a1 a2, a4 | 1–2 1–3 2–3 2–4 3–4 |
Таблица 4.8
Событие | Время наступления |
Начало работ Оборудование получено Технология разработана, оборудование отлажено Персонал обучен, производство запущено | Т1 Т2 Т3 Т4 |
По исходным данным табл. 4.7 строится сетевой график (рис. 5.6). На рис. 5.6 сети числа над дугами показывают продолжительность каждой работы. События будем обозначать порядковыми номерами. Два события отметим особо: начальное – состояние, с которого начинается весь комплекс работ; конечное – состояние, которым завершается комплекс работ.
Работу будем обозначать двумя индексами i – j, где i – номер события, после которого начинается работа, j – номер события, которым заканчивается работа (рис. 4.6 и последнюю графу табл. 4.8).
Последовательность работ, в которой конец предыдущей работы совпадает по времени с началом последующей, называется путем (табл. 4.9).
Таблица 4.9
Путь | Последовательность работ | Продолжительность |
1–2–4 | 1 + 3 = 4 | |
1–2–3–4 | 1 + 4 + 6 = 11 | |
1–3–4 | 2 + 6 = 8 |
Путь наибольшей продолжительности называют критическим (в примере – второй). На критическом пути лежат работы 1–2; 2–3; 3–4.
Увеличение продолжительности работ критического пути приводит к более позднему наступлению конечного события.
Работы, не лежащие на критическом пути, могут быть позже начаты или позже окончены, или иметь б о льшую продолжительность без изменения срока окончания всех работ.
Величину, на которую можно увеличить продолжительность выполнения такой работы без увеличения времени наступления конечного события, называют резервом.
n Если руководитель следит за выполнением всех работ в срок, то он должен четко знать и особо контролировать работы критического пути.
В нашем примере критический путь был найден простым перебором всех возможных путей. Исследование модели было словесным, без математической формулировки. Это необходимо для уяснения смысла, но недостаточно для сложных сетей.
Перейдем к формализации. В нашем примере время наступления каждого события может быть найдено по зависимостям
Т1 = 0;
Т2 = Т1 + t 12 = 0 + 1 = 1.
Так как третье событие может наступить после выполнения работ 2–3 и 1–3, запишем:
значит Т3 = 5.
Аналогично найдем время наступления последнего события:
значит Т4 = 11.
Окончательно время наступления событий будут равны Т1 = 0; Т2 = 1; Т3 = 5; Т4 = 11 (рис. 5.7).
Из рис. 5.7 видно, что резерв работы 1–3, который будем обозначать D13 = 5–2 = 3. Значит работа 1–3 может быть начата не в начальный момент времени, а спустя 3 ед. времени, или продолжаться на 3 ед. больше, чем первоначально предполагалось, то есть может длиться 2 + 3 = 5 ед. без увеличения момента наступления конечного события “4”.
Аналогично D24 = Т4 – (Т2 + t 24) = 11–(1 + 3) = 7, то есть продолжительность работы 2–4 может быть увеличена на 7 ед. Очевидно, что для работ критического пути резерв времени равен 0, то есть D12 = D23 = D34 = 0.
Для третьего события можно записать
Т3 = Т1 + t 13 + D13. Отсюда (Т3 – Т1) – D13 = t 13.
Выражение (Т3 – Т1) записано в скобках, чтобы было наглядно видно, что это интервал времени между двумя последовательными событиями. И этот интервал за вычетом резерва D13 равен продолжительности работы 1–3. В этой зависимости нам задана продолжительность работы t 13 = 2 (правая часть уравнения), остальные величины – искомые переменные. Если их обозначить:
Т3 = x 3; D13 = x 13; Т1 = x 1; t 13 = b 13, то можно записать:
(x 3 – x 1) – x 13 = b 13 и получить линейное уравнение с тремя неизвестными.
Если записать аналогичные зависимости для всех событий и работ, входящих в нашу сеть, то получим систему:
Эта система описывает топологию (структуру) нашей сети. Следовательно, сеть может быть представлена не только графически, но и в виде аналитических уравнений, которые можно ввести в ПЭВМ.
Если вместо tij подставить их известные (заданные) значения, получим:
Эта система структуры сети содержит пять линейных уравнений с девятью неизвестными. Значит, она имеет бесчисленное множество решений. Чтобы ее решить надо добавить граничные условия и целевая функция.
При этом возможны две постановки задач оптимизации.
Первая постановка: задаемся временем начала работ, то есть значением Т1, например, Т1 = 0, и стремимся закончить комплекс работ как можно раньше:
Вторая постановка: задан срок завершения всех работ, например, Т4 = 15 и нас интересует как можно позже начать работы, но чтобы непременно уложиться в срок:
Обе постановки – это задачи линейного программирования, которые можно решить (табл. 4.10)
Таблица 4.10
Постановка | Целевая функция | Граничные условия | Т1 | Т2 | Т3 | Т4 | D12 | D13 | D23 | D24 | D34 |
T4® min | T1 = 0 | ||||||||||
T1® max | T4 = 15 |
на + 4 больше, чем в 1-й постановке
Из таблицы видно, что резерв D ij не зависит от постановки задачи. Времена же окончания работ в первой постановке и начала работ во второй постановке определяются заданными граничными условиями.
Теперь перейдем к определению критического пути и других параметров сети, заданной в общей постановке.
В общем виде топология сети запишется:
(*) (Т j – T i) – D ij = tij (для всех i, j).
Если обозначить S – число событий, R – число работ, то, как видно из (*), система, описывающая сеть, будет включать n переменных, где n = S + R, так как каждому i -му событию соответствует неизвестная T i, а каждой i, j -й работе – неизвестная D ij. А число ограничений m = R, то есть каждой работе соответствует ограничение.
Поэтому в начальных сетях одна строка (*) превращается в систему линейных уравнений, содержащую сотни, а может быть и тысячи неизвестных и ограничений.
Тогда общие постановки запишутся:
где T1 пл, T n пл – заданные плановые сроки начала и окончания работ сети.
Например, для графика (рис. 4.8) из 11 событий и 20 работ (всего лишь) первая постановка при Т1 = 0 будет иметь вид:
В результате решения задачи на ПЭВМ определены критический путь, сроки начала работ и событий, резервы работ, приведенные под стрелками. Решение этой задачи вручную очень трудоемко!
Рис. 4.8
Дата публикования: 2015-01-10; Прочитано: 630 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!