Сетевая модель и ее основные элементы

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. Анализ сетевых моделей Коэффициент напряженности Кн(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 – резервная работа. 5. Оптимизация сетевого графика методом «время – стоимость» Продолжительностью времени работы (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) после оптимизации