Глава 30. СЕТЕВЫЕ МОДЕЛИ

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

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

Основные понятия сетевой модели

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

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

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

Фиктивная работа — это связь между результатами работ (событиями), не требующая затрат времени и ресурсов.

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

Путь — это любая непрерывная последовательность (цепь) работ и событий.

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

При построении сетевых моделей необходимо соблюдать следующие правила.

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

2. Два соседних события могут объединяться лишь одной работой. Для изображения параллельных работ вводятся про­межуточное событие и фиктивная работа (рис. 30.1).

3. В сети не должно быть тупиков, т.е. промежуточных событий, из которых не выходит ни одна работа (рис. 30.2).

4. В сети не должно быть промежуточных событий, кото­рым не предшествует хотя бы одна работа (рис. 30.3).

5. В сети не должно быть замкнутых контуров, состоя­щих из взаимосвязанных работ, создающих замкнутую цепь (рис. 30.4). Для правильной нумерации событий поступают следующим образом: нумерация событий начинается с исход­ного события, которому дается номер 1. Из исходного собы­тия 1 вычеркивают все исходящие из него работы, на остав­шейся сети вновь находят событие, в которое не входит ни одна работа. Этому событию дается номер 2. Затем вычеркивают работы, выходящие из события 2, и вновь находят на остав­шейся части сети событие, в которое не входит ни одна работа, ему присваивается номер 3, и так продолжается до заверша­ющего события. Пример нумерации сетевого графика показан на рис. 30.5.

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

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

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

Расчет временных параметров сетевого графика

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

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

Рассмотрим прямой проход:

t_i^р.н. — ранний срок начала всех операций, выходящих из события i.

Если i = 0, то t₀^р.н. = 0;

t_j^р.н. — ранний срок начала всех операций, входящих в j.

Тогда

где t_ij — продолжительность операции (i,j);

Прямой проход закончился, начинаем обратный:

t_i^п.o — поздний срок окончания всех операций, входящих в событие i.

Если i = п, где п — завершающее событие сети, то t_n^п.o = t_n^р.н. и является отправной точкой обратного прохода;

t_i^п.о = (t_j^п.о - t_i,j) для всех операций (i,j);

Используя результаты вычислений при прямом и обрат­ном проходах, можно определить операции критического пу­ти. Операция (i, j) принадлежит критическому пути, если она удовлетворяет условиям:

Для рассматриваемого примера критический путь включа­ет операции (0,2), (2,3), (3,4), (4,5), (5,6).

Операции связаны еще с двумя сроками:

t_ij^п.н. — поздний срок начала работы. Он является наибо­лее поздним (максимальным) из допустимых моментов начала данной работы, при котором еще возможно выполнение всех последующих работ в установленный срок:

t_ij^р.o — ранний срок окончания работы. Он является наибо­лее ранним (минимальным) из возможных моментов окончания работы при заданной продолжительности работ:

Различают два вида резервов времени: полный резерв (r_п) и свободный резерв (r_св).

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

Свободный резерв времени — максимальное время, на ко­торое можно отсрочить начало или увеличить продолжитель­ность работы при условии, что все события наступают в ран­ние сроки:

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

Построение сетевого графика и распределение ресурсов

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

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

На рис. 30.8 показана потребность в рабочей силе при усло­вии выбора в качестве календарных сроков некритических опе­раций начала их ранних сроков, на рис. 30.9 — потребность в рабочей силе при выборе наиболее поздних сроков.

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

Оптимальное решение задачи равномерного использования ресурсов (минимизация максимальной потребности в ресур­сах) представлено на рис. 30.10, уточненный график выпол­нения работ указан на рис. 30.11.

Учет стоимостных факторов при реализации сетевого графика

Стоимостные факторы при реализации сетевого графика учитываются путем определения зависимости "затраты-продолжительность" для каждой операции. При этом рассматри­ваются прямые затраты, а косвенные типа административных или управленческих расходов не принимаются во внимание.

На рис. 30.12 показана линейная зависимость стоимости операции от ее продолжительности. Точка (D_B, С_B), где D_B — продолжительность операции, а С_B — ее стоимость, соответ­ствует нормальному режиму выполнения операции. Продолжи­тельность операции можно уменьшить (сжать), увеличив ин­тенсивность использования ресурсов, а следовательно, увели­чив стоимость операции. Однако существует предел, называе­мый минимальной продолжительностью операции. За точкой, соответствующей этому пределу (точка максимально интен­сивного режима), дальнейшее увеличение интенсивности ис­пользования ресурсов ведет лишь к увеличению затрат без со­кращения продолжительности операции. Этот предел обозна­чен на рис. 30.12 точкой А с координатами (D_A,С_A).

Линейная зависимость "затраты-продолжительность" принимается из соображений удобства, так как ее можно определить для любой операции по двум точкам нормального и максимально интенсивного режимов, т.е. по точкам А и В.

Использование нелинейной зависимости "затраты-продолжительность" существенно усложняет вычисления. Поэтому иногда нелинейную зависимость можно аппроксимировать ку­сочно-линейной (рис. 30.13), когда операция разбивается на части, каждая из которых соответствует одному линейному отрезку. Следует отметить, что наклоны этих отрезков при переходе от точки нормального режима к точке максимально интенсивного режима возрастают. Если это условие не выпол­няется, то аппроксимация не имеет смысла.

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

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

Обоснование привлекательности проекта по выпуску продукции

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

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

1) подготовку технического задания на переоборудование участка (30 дн.);

2) заказ и поставку нового оборудования (60 дн.);

3) заказ и поставку нового электрооборудования (50 дн.);

4) демонтаж старого и установку нового оборудования (90 дн.);

5) демонтаж старого и установку нового электрооборудо­вания (80 дн.);

6) переобучение персонала (30 дн.);

7) испытания и сдачу в эксплуатацию оборудования для производства мороженого (20 дн.).

Ожидается, что производительность после ввода новой ли­нии составит 20 т мороженого в смену. Прибыль от реализации 1 т продукции составит 0,5 тыс. р. в смену. Деньги на покуп­ку и переоборудование участка в размере 2000 тыс. р. взяты в банке под 20% годовых (из расчета 1500 тыс. р. на закупку оборудования и 500 тыс. р. на работы по демонтажу старого оборудования и установке нового оборудования). Затраты на проведение работ в нормальном и максимальном режимах ука­заны в табл. 30.3.

Определить, через какое время может быть возвращен кре­дит в банк.

Решение. 1. Составим график проведения работ по пуску новой линии:

На проведение переоборудования необходимо

2. График можно улучшить, выполняя некоторые работы параллельно. Получим график (рис. 30. 14).

На этом графике обозначены работы:

0,1 — подготовка технического задания;

1,2 — заказ и поставка нового оборудования;

1,3 — заказ и поставка нового электрооборудования;

2,4 — установка нового оборудования;

3,4 — установка нового электрооборудования;

1,4 — переобучение персонала;

4,5 — сдача в эксплуатацию новой линии.

По графику путь (0,1), (1,2), (2,4), (4,5) имеет продолжи­тельность 200 дн.; (0,1), (1,3), (3,4), (4,5) — 180 дн.; (0,1), (1,4),(4,5) - 80дн.

Критическим путем графика является путь, на котором на­ходятся работы (0,1), (1,2), (2,4), (4,5) продолжительностью

30 + 60 + 90 + 20 = 200 дн.

График улучшился на 360 — 200 = 160 дн.

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

Через 200 дн. после начала работ предприятие истратит 1 500 тыс. р. на приобретение оборудования (согласно условию примера) и 265 тыс. р. на его установку и сдачу в эксплу­атацию (см. табл. 30.3, столбец "Затраты" при нормальном режиме). В наличии у предприятия останется

2 000 - 1500 - 265 = 235 тыс. р.

Построим графики изменения кредита в зависимости от времени получения прибыли предприятием — от выпуска мо­роженого (рис. 30.15).

Для построения графика изменения кредита в зависимос­ти от времени составим уравнение. Через 360 дн. после выда­чи банком кредита под 20% годовых долг предприятия соста­вит 2 400 тыс. р. Поэтому известны две точки этой прямой: А (0, 2000), B (360, 2400). Согласно уравнению прямой, прохо­дящей через две точки:

Решая уравнение, получим

Найдем уравнение прибыли предприятия. Известно, что че­рез 200 дн. после начала работ у предприятия осталось от кре­дита 235 тыс. р. Через 100 дн. после начала выпуска продукции предприятие получит прибыль

и у него будет в наличии

Таким образом, для нахождения уравнения прибыли имеем две точки: С (200, 235), D (300, 1235). Тогда

Решая совместно уравнения (30.1) и (30.2), определим вре­мя, когда кредит может быть возвращен в банк:

Откуда получаем у = 2471, х = 423,6 ≈ 424 дн.

3. График выполнения работ может быть сжат за счет вы­полнения некоторых операций в максимально интенсивном ре­жиме.

Вычислим наклоны кривой "затраты-продолжительность" для каждой операции. Результаты расчетов даны в табл. 30.4.

Учитывая наклоны кривой, производим сжатие операций (0,1), (2,4), (3,4), (4,5), получим сетевой график (рис. 30.16).

Новый график имеет 2 критических пути: (0,1), (1,2), (2,4), (4,5) и (0,1), (1,3), (3,4), (4,5) с продолжительностью 157 дн.

Таким образом, критический путь сокращен с 200 до 157 дн., а это означает, что предприятие начнет производить мороженое через 157 дн. после начала работ.

Определим, сколько предприятию придется заплатить за "сжатие" критического пути (см. табл. 30.3):

Таким образом, "сжатие" работ (0,1), (1,2), (2,4), (3,4), (4,5) обойдется предприятию в

График изменения кредита в зависимости от времени оста­ется прежним (см. рис. 30.15). Его вид определяет уравнение

Найдем уравнение прибыли.

Через 157 дн. после начала работ у предприятия осталось от кредита

Через 100 дн. после начала выпуска продукции предприя­тие получит прибыль

и у него будет в наличии

Таким образом, для нахождения уравнения прибыли пред­приятия имеем две точки:

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

Решая совместно уравнения (30.1) и (30.3), определим вре­мя, когда кредит может быть возвращен в банк:

Таким образом, через 384 дн. предприятие может вернуть кредит в банк. По сравнению с предыдущим случаем (см. п. 2) предприятие вернет в банк деньги раньше на 424 — 384 = 40 дн.

При нормальном режиме работ критический путь состав­ляет 200 дн., стоимость работ — 265 тыс. р.

Критический путь уменьшен до 157 дн., минимальная сто­имость работ составляет 265 + 75 = 340 тыс. р. при максималь­ном режиме.

Минимизация сети

Задача минимизации сети состоит в нахождении ребер, со­единяющих все узлы сети и имеющих минимальную суммар­ную длину (рис. 30.17).

На ребрах, соединяющих узлы 1, 2, 3, указаны длины. Узел 3 соединен с узлами 1 и 2 минимальной длиной 4 + 6 = 10. Если соединить узлы 1 и 2, то возникает цикл и получающаяся сеть не будет минимальной. Отсутствие циклов в минимальной сети дало ей название "минимальное дерево-остов".

Алгоритм решения

Начнем с любого узла и соединим его с ближайшим уз­лом сети. Соединенные два узла образуют связное множество, а остальные — несвязное. Далее в несвязном множестве выбе­рем узел, который расположен ближе других к любому из узлов связного множества. Скорректируем связное и несвязное мно­жества и будем повторять процесс до тех пор, пока в связное множество не попадут все узлы сети. В случае одинаково уда­ленных узлов выберем любой из них, что указывает на неодно­значность (альтернативность) "минимального дерева-остова".

Пример 2. Телевизионная фирма планирует создание кабель­ной сети для обслуживания 5 районов-новостроек. Числа на ребрах указывают длину кабеля (рис. 30.18). Узел 1 — телеви­зионный центр. Отсутствие ребра между двумя узлами означа­ет, что соединение соответствующих новостроек либо связано с большими затратами, либо невозможно.

Найти такое соединение кабелем районов-новостроек, что­бы длина его была минимальной.

Решение. Минимальная длина кабеля: 1 + 3 + 4 + 3 + 5 = 16 (рис. 30.19).

Пример 3. На рис. 30.20 указаны длины коммуникаций, свя­зывающих 9 установок по добыче газа в открытом море с рас­положенным на берегу приемным пунктом. Поскольку скважи­на 1 расположена ближе всех к берегу, она оснащена необходи­мым оборудованием для перекачки газа, идущего с остальных скважин в приемный пункт.

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

Решение. Минимальная длина труб: 5 + 6 + 4 + 3 + 7 + 5 + 6 + 5 = 41 (рис. 30.21).

Нахождение кратчайшего пути

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

Введем обозначения:

d_ij — расстояние на сети между смежными узлами i и j;

U_j — кратчайшее расстояние между узлами i и j, U₁ = 0.

Формула для вычисления U_j:

Из формулы следует, что кратчайшее расстояние U_j до уз­ла j можно вычислить лишь после того, как определено крат­чайшее расстояние до каждого предыдущего узла i, соединен­ного дугой с узлом j. Процедура завершается, когда получено U_i последнего звена.

Определить кратчайшее расстояние между узлами 1 и 7 (рис. 30.22).

Решение. Найдем минимальные расстояния:

Минимальное расстояние между узлами 1 и 7 равно 13, а соответствующий маршрут: 1-2-5-7.

Задача замены автомобильного парка

Фирма по прокату автомобилей планирует замену автомо­бильного парка на очередные 5 лет. Автомобиль должен про­работать не менее 1 года, прежде чем фирма поставит вопрос о его замене. На рис. 30.23 приведены стоимости замены авто­мобилей (усл. ед.), зависящие от времени замены и количества лет, в течение которых автомобиль находился в эксплуатации.

Определить план замены автомобилей, обеспечивающий при этом минимальные расходы.

Решение. Найдем минимальные расстояния:

Кратчайший путь 1-2-5 со стоимостью 12,1 усл. ед. Это означает, что каждый автомобиль заменяется через 2 года, а через 5 — списывается.

УПРАЖНЕНИЯ

30.1. Составить сетевой график выполнения работ и рассчи­тать временные параметры по данным, представленным в табл. 30.5.

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

30.3. Постройте график работ, определите критический путь и стоимость работ при нормальном режиме, критический путь и минимальную стоимость работ при максимальном режиме. Необходимые исходные данные приведены в табл. 30.7.

30.4. Для улучшения финансового состояния фирме необхо­димо увеличить спрос на выпускаемый цемент марки М400 и расширить потребительский рынок. Фирма считает целесо­образным размещать цемент в специализированной таре. Для переоснащения цеха необходимо установить оборудование по производству специализированной тары. Предполагается вы­полнить следующее:

1) подготовку и выпуск технического задания на переобо­рудование цеха (20 дн.);

2) разработку мероприятий по технике безопасности (25 дн.);

3) подбор кадров (10 дн.);

4) заказ и поставку необходимого оборудования (30 дн.);

5) заказ и поставку электрооборудования (40 дн.);

6) установку оборудования (50 дн.);

7) установку электрооборудования (45 дн.);

8) обучение персонала (15 дн.);

9) испытание и сдачу в эксплуатацию линии (25 дн.).

Ожидается, что производительность вводимой линии по производству тары составит 1 000 мешков в день при односмен­ном режиме работы. Стоимость 1 мешка — 25 р., выручка от реализации тары в смену составит 25 тыс. р., из которых чис­тая прибыль фирмы равна 50 тыс. р. Деньги на покупку обору­дования и переоснащение цеха в размере 5 500 тыс. р. взяты в банке под 30% годовых из расчета 5000 тыс. р. на оборудование и 500 тыс. р. на его установку.

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

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

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

30.5. Автотранспортному предприятию предстоит освоить но­вый маршрут между городами А и В. На рис. 30.24 представ­лены различные маршруты следования из А в В, проходящие через несколько других поселков. Расстояния указаны (числа­ми в километрах) около стрелок.

Определить кратчайший маршрут следования автобусов из го­рода А в город В.

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

30.7. Строительной фирме необходимо проложить водопровод­ные трубы к 9 объектам, на которых она ведет строительство. Числа на ребрах указывают длину труб в метрах. Узел 1 — подсоединение к водопроводной трассе (рис. 30.26).

Отсутствие ребра между двумя узлами означает, что со­единение соответствующих объектов невозможно.

Найти такое соединение узла 1 с объектами строительства, чтобы суммарная длина трубопроводов была минимальной.

30.8. Фирма по прокату видео- и стереокассет планирует их замену на очередные 5 лет. Партия кассет должна эксплуа­тироваться не менее одного года, прежде чем ее заменяют. На рис. 30.27 приведены стоимости замены партии кассет (в тыс. р.), зависящие от времени замены и числа лет, в течение которых кассеты находятся в эксплуатации.

Определить план замены кассет, обеспечивающий фирме ми­нимальные расходы.

Часть 7. ПРИНЯТИЕ РЕШЕНИЙ И ЭЛЕМЕНТЫ ПЛАНИРОВАНИЯ

Поиск по сайту: