Математическая модель

системы планирования и управления производства.

1.    Правила построения сетевого графика.

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

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

Сетевой график является не только графической, но и математической моделью планируемого комплекса. Чтобы в этом убедиться, рассмотрим конкретный пример сетевого графика комплекса работ по подготовке самого обычного чаепития, сформулированного в виде следующей таблицы.

На рисунке 1. приведен сетевой график подготовки соответствующего чаепития:

Рис.1.

Здесь полный  путь l₁ проходит через события 1, 2, 3, 9;  l₂ – через события 1, 2, 3, 5, 6, 9; l₃ – через  события 1, 4, 5, 6, 9; l₄ – через события 1, 7, 8, 9, а их продолжительность  по времени ( t(l_i)) , будет:

 t(l₁)=2+10+2=14;t(l₂)=2+10+2+5+1=20;t(l₃)=1=2+5+1=9; t(l₄)=3+2=5.

Сравнивая все  t(l_i) убеждаемся, что самый длинный по времени, полный путь от 1-го события до 9-го, равняется 20у.е., а самый короткий- 5у.е.

Какой из них наиболее выгодный? Дилетант скажет- самый короткий, а мы скажем- нет, ведь за 5 у.е. даже вода в чайнике не закипит. Какое уж тут чаепитие!

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

Скажем путь, для которого t(l₄)=5 имеет резерв по сравнению с критическим t(l₂)=20,  15у.е. и  потому забота о нем- это иная забота. Она должна быть направлена на заполнение  резерва с пользой для дела. (Например, можно успеть купить к чаю варенье, печенье и т.д., или сэкономить на рабочей силе, а стол накроет хозяйка между дел, чисто интуитивно, без всяких сетей).

Пример такой сети- планирование чаепития, мы привели лишь для того, чтобы легче постичь «азы» СПУ. Здесь мы без труда нашли с помощью интуиции и критический путь, и вникли в его практическую сущность. Имея же дело с заводом-гигантом, одной интуиции руководителя недостаточно; для успешной работы нужно уметь строить сеть.

2.    Расчет сетевых графиков.

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

Значит, задача отыскания критического пути свелась к тому, чтобы найти для каждого события резерв времени, т.е. к  расчету сети. Для ее решения сначала кружки событий (рис.1) делят на четыре сектора (рис.2), затем в нижний сектор записывают номер соответствующего события, в верхний- найденный резерв времени, а в левый и правый секторы записывают, так называемые временные оценки, соответственно, прямую и обратную

Что касается прямой  временной  оценки данного события, то ей придают смысл полного времени свершения этого события. Оно, очевидно, должно совпадать с суммарным временем выполнения всех предшествующих работ. Например, в событие 7 входит одна работа, продолжительностью 3у.е., а в событие 8 (через событие7) – входит две работы общей продолжительностью (3+2)=5у.е.. Найденное полное время свершения каждого события записано в левых секторах. Некоторое недоумение может вызвать событие 5, где в левом секторе записано 14 вместо, казалось бы 3. Это объясняется тем, что  в событие 5 входит две работы- одна из события 4 с суммарным временем (1+2)=3, другая из события 3 с суммарным временем 2+10+2=14. Выбирают большее из чисел (3; 14),так как меньшее уже свершится за это время. То же следует сказать о левом секторе события 9, куда входят две работы.

Особо надо остановиться на событии 1- оно исходное (начальное), значит, по  времени оно начинается с нуля, и потому в его левый сектор записано число 0.

Рис.2.

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

Начнем с события 9 – оно завершающее, и потому в нем нет резерва времени, т.е. для него резерв времени равен нулю. Запишем этот резерв в верхний сектор события 9, а в правый сектор пишем обратную временную оценку, совпадающую с прямой (ведь резерв равен нулю).

Если теперь из обратной временной оценки в 20у.е. вычесть продолжительность предшествующей работы, то получится (20-1)=19 – обратная временная оценка события 6. А если (20-0)=20 – обратная временная оценка события 8. Они записаны в правых секторах соответствующих событий. Аналогично найдены обратные временные оценки всех других событий, а потом и резервы времени – как разности между обратной и прямой временной оценкой каждого события. Соединив те события сети, для которых резерв времени равен нулю, находим критический путь.

3.Оптимизация сети.

а) Оптимизация сети за счет перераспределения ресурсов с некритических работ на выполнение критических работ.

Рассмотрим следующую производственную сеть (рис.3)

Рис.3.

и будем ее оптимизировать с помощью следующей таблицы:

По условию работу (2-4), лежащую не на критическом пути (1;2;4;6) могут выполнить 60 человек за 5 дней, а работу (3-4), лежащую на критическом пути (1;3;4;6) – 10 человек за 8 дней. Если с работы 2-4 снять всего лишь 10 человек, то  картина совершенно изменится, что видно из таблицы.

Теперь скажем, что некритический путь через события (1-2-4-6) увеличился с 17 дней (2+5+10) до 18 дней (2+6+10), а критический – уменьшился с 24+6+8+10 до 20=6+4+10.

б) Оптимизация сетевого графика по времени за счет расчленения работ и их запараллеливания.

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

Рис.4.

Работы (3-4’-4) и (4-6’-6) будут выполняться параллельно. Теперь критический путь сократиться с 24 дней (6+8+10) до 19 дней (6+4+4+5).

В заключении скажем, что резерв времени – это время, заложенное в сеть и, следовательно, так или иначе затраченное. Но как? Либо на дело, если резерв используется; либо впустую, если  резерв остается  резервом до конца. Отсюда возникает естественное стремление уменьшить этот резерв, чтобы таким путем сократить общий срок работ. В известных пределах так поступать и разумно и заманчиво, ведь это ведет к непрерывной загрузке и людей и оборудования, а в итоге – к сокращению срока работ. Но чем резерв меньше, тем сеть «жестче» и тем меньше условий для маневрирования. Ведь если не хватает резервов на данной цепочке, можно прибегнуть к соседним, но если резервов нет нигде, срыв практически неизбежен.

Таким образом оптимизационные  задачи в системе СПУ намного сложнее оптимизационных задач, например, линейного программирования, где есть индексная строка, которая диктует нам, что дальше оптимизировать не надо; что данный очередной опорный план уже  является оптимальным. При оптимизации же сети специалист по СПУ должен обладать  особым талантом, чтобы найти «золотую середину» в борьбе с резервами времени. Он вынужден, подобно политику, идти узкой тропой между западнями «переупрощения» и болотами «переусложнения».