Сетевое планирование и управление

1. Сетевая модель и ее основные элементы Работа (i, j): Действительная работа Ожидание Зависимая или фиктивная работа События – 1, 2, …N. Путь – L Максимальный путь - Lкр Продолжительность максимального пути - tкр 2. Правила построения сетевого графика 1. События правильно пронумерованы, т. е. для каждой работы (i, j) i < j. 2. Не должно быть «тупиковых» событий 3. Не должно быть «хвостовых» событий 4. Не должно быть замкнутых контуров и петель 5. События должны быть связаны не более чем одной работой. 3. Временные параметры сетевых графиков Событие i Ранний срок свершения события tр(i) Поздний срок свершения события tп(i) Резерв времени события R(i) tр(i) = max t(Lni ) tр(j) = max (tр(i) +t(i,j)) tп(i) = tкр – max t(Lci ) tп(i) = min (tп(j) – t(i,j)) R(i) = tп(i) - tр(i) Работа (i,j) Продолжительность работы t(i,j) Ранний срок начала работы tрн(i,j) Ранний срок окончания работы tро(i,j) Поздний срок начала работы tпн(i,j) Поздний срок окончания работы tпо(i,j) Полный резерв времени Rп(i,j) Частный резерв времени Rч(i,j) Свободный резерв времени Rс(i,j) tрн(i,j) = tр(i) tро(i,j) = tр(i) + t(i,j) tпо(i,j) = tп(j) tрн(i,j) = tп(j) - t(i,j) Резерв времени пути R(L) = tкр- t(L). Rп(i,j) = tп(j) - tр(i) - t(i,j) Rч(i,j) = tп(j) - tп(i) - t(i,j) Rс(i,j) = tр(j) – tр(i) - t(i,j) Условный перечень работ по закупкам Работа Содержание (1,2) Выбор перевозчика (1,3) Оформление заказа и его согласование (1,5) Оформление/продление договора с поставщиком (2,4) Выбор транспортного средства (2,6) Определение маршрута следования (3,5) Отправка заказа поставщику (3,6) Регистрация отправки заказа (4,8) Оформление товарно-сопроводительных документов (товарно-транспортные накладные, путевые листы) (5,6) Получение условий выполнения закупки (инвайса) от поставщика в ответ на отправленный заказ и их согласование (5,7) Выполнение обязательств по оплате заказа поставщику наряду с согласованием инвайса (6,8) Доставка товара на место назначения, указанное фирмой по договору (6,9) Отслеживание местонахождения груза в пути (7,10) Контроль счетов (финансовых потоков) в процессе выполнения условий договора (8,10) Прием заказа данной фирмой (9,10) Выставление претензий по факту отступления от условий договора в части нарушения местонахождения и времени доставки товара Ранние сроки i=1, tр(1) = 0 i=2, tр(2) = tр(1) + t(1,2) = 8 …………… i=5, tр(5) = max ( tр(3)+t(3,5); tр(1)+t(1,5))=max(2+7;0+6)=9 ……………… i=10, tр(10) = max (tр(7)+t(7,10); tр(8)+t(8,10); tр(9)+t(9,10)) =30. Поздние сроки i=10, tп(10) = tр(10) =30 i=9, tп(9) = tр(10) – t(9,10) = 26 ………………… i=6, tп(6) = min (tп(9) - t(6,9); tп(8) – t(6,8)) = 21 ………………… i=1, tп(1) = min (tп(2) - t(1,2); tп(3) – t(1,3); tп(5) – t(1,5) = 0. Номер события Сроки свершения события Резерв времени ранний поздний 1 2 3 4 5 6 7 8 9 10 Ранние сроки начала работ tрн(1,2) = tр(1) =0 …………………. tрн(1,5) = tр(1) =0 ……………….. Ранние сроки окончания работ tро(1,2) = tр(1) + t(1,2) = 8 ………………….. tро(1,5) = tр(1) + t(1,5) = 6 ………………… Поздние сроки начала работ tпн(1,2) = tп(2) - t(1,2) = 15-8=7 ………………… tпн(1,5) = tп(5) - t(1,5) = 3 ……………….. Поздние сроки окончания работ tпо(1,2) = tп(2) =15 ……………. tпо(1,5) = tп(5) = 9 Резервы времени Полный резерв Rп(1,2) = tп(2) - tр(1) - t(1,2)= 15-0-8=7 ……………… Rп(1,5) = tп(5) - tр(1) - t(1,5)=3 ……………… Частный резерв Rч(1,2) = tп(2) – tп(1) - t(1,2)= 15-0-8=7 ………….. Rч(1,5) = tп(5) – tп(1) - t(1,5)=3 …………… Свободный резерв Rс(1,2) = tр(2) - tр(1) - t(1,2)= 0 ………….. Rс(1,5) = tр(5) - tр(1) - t(1,5)=3 …………. Работа (i,j) Продол-жительность работы t(i,j) Сроки начала и окончания работы Резервы времени работы tрн(i,j) tро(i,j) tпн(i,j) tпо(i,j) Rп(i,j) Rч(i,j) Rс(i,j) (1,2) 8 8 7 12 7 7 (1,3) 2 2 2 (1,5) 6 6 3 9 3 3 3 4. Сетевое планирование в условиях неопределенности tср(i,j) = , 2(i,j) = В реальных проектах tср(i,j) = Оценка вероятности того, что срок выполнения проекта не превзойдет заданного директивного срока Т: P(tкр≤ T) = ½ + 1/2Ф(), Ф(z) – интегральная функция Лапласа σкр – среднее квадратическое отклонение длины критического пути 5. Анализ сетевых моделей Коэффициент напряженности Кн(i,j) = t(Lmax) – продолжительность максимального из некритических путей, проходящих через работу (i,j); tкр – длина критического пути; - длина отрезка рассматриваемого пути, совпадающего с критическим. L1 : 1 5 6 8 10, путь составляет 27 суток, L2 : 1 5 6 9 10, путь составляет 27 суток, L3 : 1 5 7 10, путь составляет 18 суток. К= =0,666… Кн(i,j) > 0,8 – критическая работа; 0,6 Кн(i,j) 0,8 – подкритическая работа; Кн(i,j) < 0,6 – резервная работа. 6. Оптимизация сетевого графика методом «время – стоимость» Продолжительностью времени работы (i, j) находится в пределах a(i, j) t(i, j) b(i, j) Изменение стоимости работы Δс(i, j) при сокращении ее продолжительности Δс(i, j) = h(i, j)(b(i, j)-t(i, j)), h(i, j) = tg α = . Проведем оптимизацию сетевой модели по планированию транспортировки. Предполагается, что все временные параметры найдены и найден критический путь. Работа Содержание работ (1,2) Принятие заказа (1,4) Заказ транспорта (2,3) Отправка счета на основании принятого заказа (2,4) Обработка принятого заказа (3,5) Получение и проверка оплаты по счету (4,5) Доставка товара получателю в момент оплаты Необходимые исходные данные представлены в таблице Работа (i,j) Продолжительность работы (сут.) Стоимость работ Коэфф. затрат на ускорение h(i, j) a(i, j) b(i, j) cmax(i, j) cmin(i, j) (1,2) 3 5 19 5 (1,4) 4 6 12 6 (2,3) 1 3 15 8 (2,4) 3 7 18 10 (3,5) 1 6 9 6 (4,5) 1 4 12 9 8. Оптимизация сетевых моделей по критерию «минимум исполнителей» График привязки отображает взаимосвязь выполняемых работ во времени и строится на основе данных либо о продолжительности работ либо о ранних сроках начала и окончания работ. На графике загрузки по горизонтальной оси откладывается время, например в днях, по вертикальной оси - количество человек, занятых работой в каждый конкретный день. Рассмотрим пример по оптимизации загрузки исполнителей. Исходные данные Название работы Продолжительность работы A 10 B 8 C 4 D 12 E 7 F 11 G 5 H 8 I 3 J 9 K 10 Упорядочение работ 1) Работы C, I, G являются исходными работами проекта, которые могут выполняться одновременно. 2) Работы E и A следуют за работой C. 3) Работа H следует за работой I. 4) Работы D и J следуют за работой G. 5) Работа B следует за работой E. 6) Работа K следует за работами A и D, но не может начаться прежде, чем не завершится работа H. 7) Работа F следует за работой J. Описание сетевой модели Номера событий Код работы Продолжительность начального конечного работы 1 2 (1,2) 4 1 3 (1,3) 3 1 4 (1,4) 5 2 5 (2,5) 7 2 6 (2,6) 10 3 6 (3,6) 8 4 6 (4,6) 12 4 7 (4,7) 9 5 8 (5,8) 8 6 8 (6,8) 10 7 8 (7,8) 11 Временные параметры рассчитаны и представлены в таблице. tрн(i,j) tрo(i,j) tпн(i,j) tпo(i,j) 1,2 4 4 3 7 3 1,3 3 3 6 9 6 1,4 5 5 5 2,5 7 4 11 12 19 8 2,6 10 4 14 7 17 3 3 3,6 8 3 11 9 17 6 6 4,6 12 5 17 5 17 4,7 9 5 14 7 16 2 5,8 8 11 19 19 27 8 8 6,8 10 17 27 17 27 7,8 11 14 25 16 27 2 2 Исходные данные для оптимизации загрузки Код работ Продолжительность работ Количество исполнителей (1,2) 4 6 (1,3) 3 1 (1,4) 5 5 (2,5) 7 3 (2,6) 10 1 (3,6) 8 8 (4,6) 12 4 (4,7) 9 2 (5,8) 8 6 (6,8) 10 1 (7,8) 11 3 Графики загрузки (а) и привязки (b) до оптимизации Графики загрузки (а) и привязки (b) после оптимизации Обоснование привлекательности проекта по выпуску продукции Рассмотрим пример по улучшению финансового состояния предприятия за счет выпуска конкурентоспособной продукции (мороженое). Для переоборудования цеха (участка) под выпуск этой продукции необходимо выполнить: 1) подготовку технического задания на переоборудование участка (30 дней), 2) заказ и поставку нового оборудования (60), 3) заказ и доставку нового электрооборудования (50), 4) демонтаж старого и установку нового оборудования (90), 5) …………………………………………. электрооборудования (80), 6) переобучение персонала (30), 8) испытание и сдачу в эксплуатацию оборудования для производства мороженого (20). Ожидается, что производительность после ввода новой линии составит 20т мороженного в смену. Прибыль от реализации 1т продукции составит 0,5 тыс. р. в смену. Деньги на покупку и переоборудование участка в размере 2 000 тыс. р. взяты в банке под 20% годовых (из расчета 1 500 тыс.р. на закупку оборудования и 500 тыс.р. на работы по демонтажу старого оборудования и установке нового). Затраты на проведение работ в нормальном и максимальном режимах указаны в таблице. Определить, через какое время может быть возвращен кредит в банк. Работа Нормальный режим Максимальный режим Продолжительность Затраты, тыс.р. Продолжительность Затраты, тыс.р. 1 30 20 25 30 2 60 40 45 60 3 50 30 40 40 4 90 70 70 100 5 80 60 65 70 6 30 25 20 25 7 20 20 17 25 Итого 360 265 282 350 1. Составим график проведения работ по пуску новой линии. Для проведения переоборудования необходимо 360 дней. Через 360 дней после выдачи банком кредита под 20% годовых долг предприятия составит_________________ Через 100 дней после начала выпуска продукции предприятия получит прибыль_____________________ Первоначальный вариант без преобразования сети. Погашение кредита через 603, 6 дней 2. График можно улучшить, выполняя некоторые работы параллельно. Через 360 дней после выдачи банком кредита под 20% годовых долг предприятия останется прежним_________________ Через 100 дней после начала выпуска продукции предприятия получит прибыль_____________________ Погашение кредита через 424 дня. 3. На основании метода «время-стоимость» график выполнения работ может быть сжат за счет выполнения некоторых операций в максимально интенсивном режиме. Учитывая коэффициент затрат для критического пути, строим новый сетевой график. Работа Коэффициент затрат 0,1 2 1.2 1,3 1,3 1 1,4 1,5 2,4 0,7 3,4 1 4,5 1,7 Через 360 дней после выдачи банком кредита под 20% годовых долг предприятия останется прежним_________________ Через 100 дней после начала выпуска продукции предприятия получит прибыль_____________________ Погашение кредита через 384 дня.