Сетевое планирование и управление. Оптимизация по времени, ресурсам и стоимости товара

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

2.1 Оптимизация сетевой модели по ресурсам

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

Пример1. Оптимизировать сетевой график по ресурсам. Наличный ресурс равен 10 единицам.

 

 

 

 

 

 

 

 

 

Рисунок 3 –Сетевой график для примера 1

Первое число, приписанное стрелке графика, означает время выполнения работы, а второе – требуемое количество ресурса для выполнения работы. Работы не допускают перерыва в их выполнении.

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

Справа для каждой работы укажем требуемое количество ресурса. По графику Ганта строим график ресурса. На оси абсцисс мы откладываем время, а на оси ординат – работы

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 4 –График Ганта

Ресурсы складываются по всем работам, выполняемым одновременно. Также проведем ограничительную линию по ресурсу (в нашем примере это y 10).

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 5 –Ограничительная линия

Из графика мы видим, что на отрезке от 0 до 4, когда одновременно выполняются работы B, A, С, суммарная потребность в ресурсах составляет 3 + 4 + 5 = 12, что превышает ограничение 10. Так как работа С – критическая, то мы должны сдвинуть сроки выполнения или A, или B.

Запланируем выполнение работы B с 6-го по 10-й день. На сроках выполнения всего проекта это не скажется и даст возможность остаться в рамках ресурсных ограничений.

 

 

 

 

 

 

 

 

 

 

 

Рисунок 6 –Окончательный график выполнения работ

2.2 Оптимизация сетевой модели по времени

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

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

Оптимизация сетевого графика по времени может проводиться с привлечением дополнительных средств и с использованием внутренних резервов.

Приведем математическую формулировку процесса оптимизации по времени.

Пусть задан сетевой график выполнения комплекса операций. Время выполнения каждой операции равно tij. Пусть также вложение xij дополнительных средств в операцию (i,j) сокращает время выполнения с tij до t’ij<tij. Естественно, для каждой операции существует минимально возможное время ее выполнения, равное dij. Требуется определить время начала Tijn и Tijo окончания  выполнения операций, а также величину дополнительных средств xij, которые необходимо вложить в каждую из операций(i,j), чтобы общее время выполнения комплекса операций было минимальным. При этом сумма вложенных дополнительных средств не должна превышать заданной величины C, а время выполнения каждой операции должно быть не меньше минимально возможного времени dij.

Математически условия задачи можно записать следующим образом:

 

 (1)

  (2)

 (3)

 (4)

 (5)

  (6)

 

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

Ограничения равенства (4) показывают зависимость продолжительности выполнения операций от вложенных средств. Ограничения (5) обеспечивают выполнение условий предшествования операций в соответствии с топологией сети (время начала выполнения каждой операции должно быть не меньше времени окончания непосредственно предшествующей ей операции).

Критический путь в данной задаче является функцией от объемов дополнительно вкладываемых средств xij.

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

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

Пример 2.

Рассмотрим сетевой график, представленный на рисунке

Рисунок 7-Сетевой график для примера 2

Цифры, приписанные дугам, означают соответственно продолжительность tij. и минимально возможное время dij. выполнения операций (в днях).

Продолжительность выполнения операций зависит линейно от дополнительно вложенных средств и выражается соотношением

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

Решение

Добавив на сетевом графике фиктивную операцию (5,6), запишем целевую функцию в виде

 

 

Запишем ограничения задачи:

• сумма вложенных средств не должна превышать наличного их количества

 

 

• время выполнения каждой операции должно быть не меньше минимально возможного времени

 

 

• зависимость продолжительностей операций от вложенных средств дает ограничения-равенства

 

 

• время начала выполнения каждой операции должно быть не меньше времени окончания непосредственно предшествующей ей операции (моменты времени

 

 

• условие неотрицательности неизвестных

 

 

для всех дуг сетевого графика.

Создадим на рабочем листе Excel форму для ввода данных, необходимых для решения задачи (Рисунок 8).

Рисунок 8– Форма для ввода данных примера 2

Введем обозначения для переменных согласно Рис. 3.7, и отведем под расчетные значения X1-X20 диапазон ячеек A8:T8. Далее, введем формулы для расчета функций-ограничений в соответствии с таблицей 1.

Таблица 1

Ячейка	Формула	Ячейка	Формула
C9	=D8-C8	K13	=A8+0,1*O8
E9	=F8-E8	K14	=B8+0,4*P8
G9	=H8-G8	K15	=D8-C8+0,6*Q8
I9	=J8-I8	K16	=F8-E8+0,42*R8
K9	=L8-K8	K17	=J8-I8+0,64*S8
M9	=N8-M8	K18	=L8-K8+0,12*T8
C13	=C8-A8
C14	=E8-A8	G22	=O8+P8+Q8+R8+S8+T8
C15	=I8-B8
C16	=I8-D8	O14	=N8
C17	=G8-B8
C18	=G8-D8
C19	=K8-F8
C20	=K8-H8
C21	=M8-J8
C22	=M8-L8

 

Целевой ячейкой является O14.

Вызываем Поиск решения и вводим все необходимые ограничения.

Ответ

Таким образом, чтобы выполнить комплекс операций за 29,65 дней, необходимо вложить в операцию (1,3) 0,88 д.е., в операцию (2,3) 3,92 д.е., в (2,4) 0,83 д.е., и в операцию (3,5) - 9,38 д.е.

2.3 Оптимизация сетевой модели по стоимости проекта.

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

Пример 3

Исходные данные приведены в таблице 2.

Требуется оптимизировать сетевой график по стоимости при То=34

Рисунок 9-Сетевой график для примера 3

Таблица 2

Параметры	Операции
	(1,2)	(1,3)	(2,3)	(2,5)	(3,4)	(3,5)	(4,5)
	9	10	0	3	4	5	8
	11	15	0	5	7	8	10
	2	5	-	5	4	10	3
	20	40	-	30	45	50	25

 

Решение

Запишем Сij, для всех (i,j), принадлежащих сетевому графику

;

;

;

;

;

;

 

При записи функции принято, что

 

 

Так как при параметрах t”ij tкр=32 меньше То=34, то оптимизация возможна за счет всех операций сетевого графика.

Запишем ограничения по времени выполнения операций

 

 

 

Ограничения по предшествованию в выполнении операций:

 

 

Все неизвестные должны быть неотрицательными, т.е.

 

 для всех операций  (i,j) сети.

 

Проведем решение задачи в Excel. Введем данные на рабочий лист в соответствии с рисунком 10.

Для расчетных значений переменных X1-X12 отведем диапазон ячеек A5:L5.

Далее, введем функции-ограничения и формулу для целевой функции в ячейки в соответствии с приводимой ниже таблицей.

 

 

Рисунок 10 – Форма для ввода данных примера 3

Таблица 3

Ячейка	Формула	Ячейка	Формула
C6	=D5-C5	C16	=C5-A5
E6	=F5-E5	C17	=E5-A5
G6	=H5-G5	C18	=I5-B5
I6	=J5-I5	C19	=I5-D5
K6	=L5-K5	C20	=G5-B5
B12	=F5	C21	=G5-D5
B13	=J5	C22	=K5-H5
B14	=L5
J19 (целевая функция)	=-2*A5-5*B5-5*F5+5*E5-4*H5+4*G5-10*J5+10*I5-3*L5+3*K5+430

 

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

Таблица 4

$A$5<=$A$10	$E$6<=$E$10	$H$5>=14	$C$16>=$E$16
$A$5>=$A$8	$E$6>=$E$8	$I$5>=10	$C$17>=$E$17
$B$5<=$B$10	$G$6>=$G$8	$J$5>=15	$C$18>=$E$18
$B$5>=$B$8	$G$5>=10	$I$6<=$I$10	$C$19>=$E$19
$C$5>=9	$G$6<=$G$10	$I$6>=$I$8	$C$20>=$E$20
$C$6>=$C$8	$F$5<=34	$K$6<=$K$10	$C$21>=$E$21
$D$5>=9	$J$5<=34	$K$6>=$K$8	$C$22>=$E$22
$E$5>=9	$L$5<=34