Построение модели организации технологических операций

2                   Построение модели организации технологических операций

2.1 Сетевые графики

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

Итак, сетевой график – есть математическая модель упорядочивания проектных работ типа "Сигнальный граф" (см. пример на рис.2.1). Любой сигнальный граф состоит только из двух элементов: дуг и вершин. В контексте сетевого планирования, дугами являются отдельные работы, изображаемые на сетевом графике в виде стрелок так, что начала стрелок, соответствует началам выполнения работ, концы стрелок – их завершению. Вершинами сигнального графа являются так называемые события, которые изображаются на сетевом графике в виде кружков, с порядковыми номерами в нижних квадрантах. Как раз события сетевого графика и служат для целей упорядочивания проектных работ, которое заключается в том, что исходящая из некоторого события работа не может начаться, пока не завершаться все входящие в него работы.

Существует масса правил, узаконенных стандартом, придерживаться которых необходимо при построении сетевых графиков. Наиболее важные из них:

−       Любой сетевой график должен иметь начальное событие, работы из которого только исходят, и конечное событие, в которое они только входят;

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

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

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

ранние и поздние сроки наступления событий;

−       ранние и поздние сроки начала и окончания работ;

−       резервы времени работ и событий.

Ранний срок наступления события – это минимально возможный срок, необходимый для выполнения всех работ, предшествующих данному событию. Расчёт ранних сроков наступления событий ведут в порядке – от начального события проекта (с номером 0) до завершающего. При расчёте принимают, что ранний срок наступления начального события равен 0. Для определения раннего срока наступления -го события пользуются правилом, математически записываемым так:

 , (2.1)

где  –ранний срок наступления рассматриваемого события, ;

– номер рассматриваемого события;

– номера предшествующих событий, соединенных с рассматриваемыми работами;

 – ранний срок наступления -го предшествующего события, ;

 – длительность работы, соединяющей -е предшествующее событие с рассматриваемым, .

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

Поздний срок наступления события – это максимально допустимый срок наступления рассматриваемого события, определяемый из условия, что после наступления этого события в свой поздний срок остаётся достаточно времени, чтобы выполнить следующие за ним работы. Расчёт поздних сроков наступлений событий ведут в обратном порядке – от завершающего события проекта до начального (с номером 0). При расчёте принимают, что поздний срок наступления завершающего события совпадает с его ранним сроком наступления. Для расчёта позднего срока наступления -го события пользуются правилом, математически записываемым так:

, (2.2)

где  – поздний срок наступления рассматриваемого события, ;

 – номер рассматриваемого события;

 – номера последующих событий, соединённых с рассматриваемым работами;

 – поздний срок наступления -го последующего события, ;

 – длительность работы, соединяющей -е последующее событие с рассматриваемым,

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

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

, (2.3)

где  – резерв времени рассматриваемого события, .

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

Ранний срок начала работы совпадает с ранним сроком наступления её начального события, а ранний срок окончания работы превышает его на величину продолжительности этой работы:

; (2.4)

, (2.5)

где  – ранний срок начала работы, исходящей из -го события и входящей в -е событие, ;

 – ранний срок окончания данной работы, ;

 – длительность этой работы, ;

 – раннее начало события, из которого исходит рассматриваемая работа, ;

Поздний срок окончания работы совпадает с поздним сроком наступления её конечного события, а поздний срок начала работы меньше на величину продолжительности этой работы:

; (2.6)

, (2.7)

 – поздний срок окончания работы, исходящей из -го события и входящей в -е событие, ;

 – поздний срок начала данной работы, ;

 – длительность этой работы, ;

 – позднее окончание события, в которое входит рассматриваемая работа, .

Полный резерв времени некоторой работы – это максимальное время, на которое можно отсрочить её начало или увеличить продолжительность, не изменяя директивного срока наступления завершающего события сетевого графика:

, (2.8)

где  – полный резерв времени работы, исходящей из -го события и входящей в -е событие, .

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

, (2.9)

где  – свободный резерв времени работы, исходящей из -го события и входящей в -е событие, .

В качестве примера, который потребуется и в дальнейшем, основные рассмотренные параметры сетевого графика рассчитаны для случая, представленного на рисунке 2.1. Здесь, длительности работ, являющиеся исходными данными для расчёта, выбраны произвольным образом. Параметры работ обозначены соответствующими символами возле стрелок. Параметры событий отражены в трёх квадрантах соответствующих кружков. В левых квадрантах отражены значения ранних сроков свершения событий. В правых – значения поздних сроков свершения событий. В верхних – значения резервов времени событий.

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

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

Начнём с доказательства методики поиска критического пути сетевого графика. Для этого рассмотрим ряд вспомогательных теорем.

Теорема 3.1 – Для того, чтобы некоторый путь сетевого графика был бы критическим, необходимо и достаточно, чтобы полные резервы времени всех входящих в него работ были бы равны нулю.

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

Докажем это утверждение методом от противного.

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

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

Достаточность – Если все работы некоторого пути имеют нулевые полные резервы времени, то этот путь обязательно является критическим.

Если некоторый путь имеет работы только с нулевыми полными резервами времени, то это означает, что ни одну работу, указанного пути, нельзя увеличить по длительности без изменения срока свершения завершающего события сетевого графика. Это возможно, только когда сумма длительностей работ, рассматриваемого пути равна сроку свершения завершающего события, то есть длительности критического пути. Тогда, рассматриваемый путь и является критическим, в силу того, что он равен критическому пути по длительности. Утверждение доказано.

Теорема 3.2 – Если в некоторое событие сетевого графика входит работа с нулевым полным резервом времени, то среди всех исходящих из данного события работ, обязательно найдётся хотя бы одна, имеющая также нулевой резерв времени. То есть, работы с нулевыми резервами времени следуют друг за другом непрерывно.

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

Докажем теорему методом от противного.

Пусть для работы, входящеё в событие 2, полный резерв времени . Предположим противное – среди всех работ, исходящих из события 2, нет ни одной работы с нулевым полным резервом времени.

Для начала найдём, чему равен поздний срок свершения события 2. Он, в соответствии с формулой (2.2), определяется как минимальное время позднего начала работы среди всех работ, исходящих из рассматриваемого события. Пусть поздний срок свершения события 2 равен позднему началу работы, входящей, например, в событие 4:

,

или, в соответствии с выражением (2.8) для полного резерва времени,

.(2.10)

Теперь рассмотрим, какое может иметь значение полный резерв времени работы, исходящей из события 1 и входящей в событие 2. В соответствии с формулой (2.8):

 (2.11)

Из формулы (2.11) видно, что минимально возможное значение полного резерва времени работы, исходящей из события 1 и входящей в событие 2, достигается тогда, когда величина  достигает своего максимального значения. Из правила определения раннего срока свершения события, задаваемого формулой (2.1), следует, что максимальное значение этой величины может быть равно только раннему сроку свершения события 2, когда ранний срок окончания рассматриваемой работы самый большой из всех ранних сроков окончания работ, входящих в событие 2. Тогда, минимально возможное значение полного резерва времени работы, исходящей из события 1 и входящей в событие 2 равно:

,

или, исходя из формулы (2.11):

  (2.13)

Поскольку мы предположили от противного, что среди всех исходящих из события 2 работ нет работ с нулевым полным резервом времени, то отсюда сразу вытекает, что и работа, исходящая из события 1 и входящая в событие 2, также не может иметь нулевой полный резерв времени, уж если его минимальное значение заведомо неравно нулю, в соответствии с полученным равенством. Последнее противоречит условию теоремы. Из этого противоречия следует то, что невозможна ситуация, когда при нулевом резерве времени работы, входящей в событие 2, все исходящие из этого события работы имели бы ненулевые резервы времени. Если бы это имело место, то в соответствии с приведённым доказательством, работа, входящая в событие 2 также бы имела ненулевой полный резерв времени. Но ведь это не так по условию теоремы. Тогда для работ, исходящих из события 2 остаётся другая возможная ситуация – хотя бы одна из них имеет также нулевой полный резерв времени. Теорема доказана.

Из доказанных выше теорем, непосредственно, следует методика поиска критического пути, приводимая ниже.

Рациональная методика поиска критического пути сетевого графика: