Стоимостная оптимизация сетевого графика при нефиксированной величине критического пути

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

О работах, включённых в него в таблице 6.2, имеется следующая информация:

Таблица 6.2 – Данные для оптимизации сетевого графика

Работы	tij(1)	tij(0)	Cij(1)	Cij(0)
(1, 2)   (1, 3) (1, 4) (2, 5) (3, 4) (3, 6) (4, 5) (4, 6) (5, 7) (6, 7)					h13 = 0/0 – критическая h14 = 3 h25 = 7 h34 = 5 – критическая h36 = 0/0 h45 = 5 – критическая h46 = 0/0 h57 = 1 – критическая h67 = 3

Общая стоимость выполнения всего комплекса работ равна С=7∙30+4∙20+5∙10 + 6∙18 + 7∙40 + 4∙30 + 8∙25 + 6∙15+5∙18 + 6∙24 = 1372. Задачу решим следующим образом:

1. Выпишем критический путь сетевого графика.

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

3. Пересчитываем сеть. На критическом пути вновь находим критическую работу с наименьшим h_ij, допускающую ускорение, и сокращаем её.

4. Процедуру ускорения критических работ проводим до полного
завершения.

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

На приведённом сетевом графике имеются следующие полные пути:
1 – 3 – 4 – 5 – 7 продолжительность 24 ед. (критический путь)

1 – 2 – 5 – 7 18, резерв 24 – 18 = 6

1 – 4 – 5 – 7 18, резерв 24 – 18 = 6

1 – 4 – 6 – 7 17, резерв 24 – 17 = 7

1 – 3 – 4 – 6– 7 23, резерв 24 – 23 = 1

1 – 3 – 6 – 7 14, резерв 24 – 10 =14

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

Из таблицы 6.2 видно, что из четырёх критических работ работа (1,3) не может быть сокращена. Остальные работы (3,4), (4,5) и (5,7) имеют коэффициенты изменения стоимости h₃₄ = 5, h₄₅ = 5, h₅₇ = 1 соответственно. Следовательно, в первую очередь необходимо ускорить работу (5,7). Эта работа допускает сокращение на 2 единицы времени. Так как один из некритических путей имеет резерв времени, равный единице, ускорять работу (5,7) в большей степени не следует. При этом в сетевом графике образуется два критических пути – 1 – 3 – 4 – 5 – 7 и 1 – 3 – 4 – 6 – 7 продолжительностью в 23 ед. времени каждый (рисунок 6.7).

Рисунок 6.7 – Сетевой график после ускорения критических работ

Ускорение работы (5,7) на единицу времени приводит к возрастанию её стоимости и стоимости всего комплекса на единицу.

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

Рассмотрим коэффициенты h_ij критических работ. Наименьший коэффициент изменения стоимости имеет работа (5,7) (h₅₇ = 1). Но она лежит на одной из ветвей критического пути, и её ускорение не даёт желаемого результата. Поэтому нужно ускорить одновременно какую-либо работу на другой ветви критического пути. На участке (4,6) сокращать время нельзя, на участке (6,7) h₆₇ = 3. Следовательно, одновременное сокращение работ (5,7) и (6,7) на единицу времени приведёт к возрастанию обшей стоимости на 4 единицы. Сокращаем обе работы (5,7) и (6,7) на единицу, т.к. (5,7) на первом шаге уменьшили на единицу. Такое сокращение не приводит к возникновению нового критического пути, т.к. резервы на остальных путях больше.

Продолжаем рассматривать возможности дальнейшего сокращения критического пути. На его раздвоенной части можно сократить работы (4,5) и (6,7), принадлежащие различным ветвям, h₄₅= 5, h₆₇ = 3. При ускорении этих работ на единицу суммарное увеличение стоимости всех работ 5 + 3 = 8.

На общей части критического пути работа (3,4) имеет h₃₄ = 5. Следовательно, эту работу необходимо ускорить в первую очередь. Она может быть сокращена на две единицы времени. Поскольку резервы времени других путей заведомо больше, то такое сокращение допустимо. Стоимость всего комплекса работ возрастает на 10 единиц. При аналогичном сокращении работ (4,5) и (6,7) стоимость увеличилась бы на 2*8=16 единиц.

Продолжительность критического пути равна 20 единицам времени, а дальнейшее ускорение работ на нераздвоенном участке невозможно, т.к. работа (1,3) не допускает ускорения, а работа (3,4) ускорена на две единицы. На раздвоенной части критического пути работы (4,5) и (6,7) можно ускорить на единицу времени. После такого сокращения получили окончательный вариант сетевого графика, на котором критический путь сократился до допустимого предела (19 ед. времени), а общая стоимость выполнения всего комплекса работ возросла в минимально возможной степени:

(ед.), что составит

Date: 2015-10-18; view: 596; Нарушение авторских прав