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

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

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

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

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

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

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

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

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

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 тыс. р. при максималь­ном режиме.