Оптимизация критического пути

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

Оптимизация может производиться с различными целями:

1. Если критический путь со временем превышает заданные сроки , то оптимизация по времени заключается в сокращении критического пути.

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

Дадим математическую постановку каждой из поставленных задач:

Задача 1. Известен критический путь , причём

,

(1)

где – распространяется только на критические работы;

– заданный (директивный) срок выполнения работ.

Для сокращения критического пути, естесственно, имеет смысл форсировать критические работы. Их можно ускорить, например:

1. За счёт дополнительных сил и средств;

2. За счёт переброски сил и средств с некритических работ на критические.

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

1. Допустим, что при вложении дополнительных средств в работу , сокращает время выполнения этой работы до времени

.

(2)

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

,

(3)

где – распространяется по всем критическим работам нового критического пути (после распределения средств);

и чтобы при этом общая сумма дополнительных средств

,

(4)

была минимальной.

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

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

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

Обозначим: – количество подвижных средств перебрасываемых с работы ( берётся отрицательным, если с работы перебрасываются средства).

Естесственно, что сумма средств, снимаемых с каких-то работ, должна быть равна сумме средств, добавляемых другим работам, т.е.

.

(5)

Величины должны удовлетворять ограничениям:

или .

(6)

Известно:

1. Если количество средств снимается с работы , то время её выполнения возрастает:

;

(7)

2. Если количество средств вкладывается в работы , то время её выполнения уменьшается:

.

(8)

При таких обозначениях общий срок выполнения всех работ (новый критический путь) будет:

,

(9)

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

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

Задача 2. Известен критический путь

.

(10)

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

.

(11)

Требуется выбрать такие значения неотрицательных переменных , чтобы общая сумма критических времён

,

(12)

при которых сумма высвободившихся средств

,

(13)

достигала максимума.

Эта задача так же относится к задачам нелинейного программирования. В случаях, когда увеличение срока работ малό, удаётся свести эту задачу к методу линейного программирования.

Определение времени отдельных работ

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

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

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

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

В этом случае продолжительность работы вычисляют по формуле:

.

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

.

Дата добавления: 2015-04-29