Оптимизация сетевых графиков

 

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

10.5.1. Оптимизация проекта по времени.Рассмотрим две постановкизадачи оптимизации проекта по времени с использованием дополнительных средств.

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

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

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

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

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

, (10.3)

при ограничениях:

(10.4)

(10.5)

(10.6)

(10.7)

(10.8)

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

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

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

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

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

(10.9)

при ограничениях

(10.10)

(10.11)

(10.12)

(10.13)

(10.14)

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

Пример 10.4. Пусть задан сетевой график, изображенный на рис.10.9. Критический путь L = 1-2-5, t_кр=90. Директивный срок выполнения проекта составляет 80 ед. Заданы технологические коэффициенты использования дополнительных средств, которое необходимо привлечь для выполнения работы (i, j): .

 

 

 

Рис. 10.9

 

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

Решение. Математическая модель задачи запишется в виде:

требуется найти количество дополнительных средств , при которых целевая функция

достигает минимального значения, и которые удовлетворяют системе ограничений:

- время завершения проекта не должно превышать директивное время:

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

- зависимости продолжительностей работ от вложенных средств:

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

;

- условия неотрицательности неизвестных: для всех дуг сетевого графика.

 

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

 

Пример 10.5. Пусть задан сетевой график, изображенный на рис 10.10.

 

 

 

Рис. 10.10

 

Критический путь L=1-3-5-6-7, = 23. Задан директивный срок выполнения проекта равный: . Для каждой работы известны продолжительности ее выполнения t_ij и минимально возможное время ее выполнения d_ij: d₁₂=4, d₁₃=2, d₁₄=8, d₂₅=5, d₃₅=9, d₄₆=7, d₅₆=5, d₆₇=2. Заданы технологические коэффициенты k_ij использования дополнительных средств: k₁₂=0,1; k₁₃=0,5; k₁₄=0,1; k₂₅=0,3; k₃₅=0,2; k₄₆=0,5, k₅₆=0,25, k₆₇=0,2.

Требуется определить:

1) количество дополнительных средств , которое необходимо вложить в работы , чтобы их сумма была минимальной;

2) время выполнения проекта не превосходило ;

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

Решение. Поскольку - дополнительные средства, которые необходимо вложить в работы , то целевая функция, определяющая эту сумму, должна стремиться к минимуму:

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

1) Условия ограничивающие время выполнения проекта:

.

2) Условия требующие выполнения каждой работы за время не меньше максимально возможного времени:

3) Условия, определяющие продолжительность работ от вложенных в них средств:

 

4) Условия, определяющие своевременность выполнения всех предшествующих работ:

 

 

5)Условия неотрицательности неизвестных: для всех дуг сетевого графика.

Решив задачу симплексным методом на ЭВМ, получим:

 

 

Пример 10.6.Проект представлен сетевым графиком, изображенным на рис. 10.11.

 

Рис. 10. 11

 

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

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

Решение. В силу условий задачи и особенностей сетевого графика целевая функция имеет вид: . Неизвестные величины должны удовлетворять следующим ограничениям.

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

2) Время выполнения каждой работы должно быть не меньше минимального времени:

3) Зависимость продолжительностей выполнения работ от вложенных средств удовлетворяет равенствам:

; ; ; ; ; ; .

4) Время выполнения каждой работы должно быть не меньше времени окончания непосредственно предшествующей ей работы:

5) Переменные величины должны быть неотрицательными:

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

Сформулированная линейная математическая модель содержит 20 неизвестных и 34 ограничений, может быть решена симплексным методом на ЭВМ.

????

 

 

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

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

1. Для каждой работы определяются ее ранние и поздние сроки начала и окончания и полные резервы времени:

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

П р е д в а р и т е л ь н ы й ш а г. Составляем линейный график Ганта выполнения проекта. На диаграмме каждая работа (i,j) изображается горизонтальным отрезком, длина которого в соответствующем масштабе равна времени ее выполнения. Начало каждой операции совпадает с ожидаемым сроком свершения ее начального события. Определяем по диаграмме критическое время t_кр и критический путь.

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

2. Определяем полные резервы времени R_n работ, расположенных над промежутком . Нумеруем эти работы в порядке возрастания их полных резервов. Работы с одинаковыми полными резервами времени нумеруем в порядке убывания интенсивностей потребления ресурсов.

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

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

О б щ и й ш а г. Предположим, что выполнено k шагов алгоритма и получен линейный график, момент которого является началом оставшейся части работ проекта.

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

2. Определяем полные резервы работ , расположенных над промежутком и номеруем их. Сначала нумеруем работы , начатые левее момента , согласно возрастанию разностей между полными резервами этих работ и длительностями от начала до момента (длительности работ обозначим ). Работы с одинаковыми разностями нумеруем в порядке убывания интенсивностей. Все остальные работы нумеруем в порядке возрастания их полных резервов, а с одинаковыми резервами - в порядке убывания интенсивностей.

3. Это действие выполняется так же, как и действие 3 первого шага. Однако следует иметь в виду, что если сдвигу подлежит работа , начатая левее , то сдвигаем всю работу, т.е. начало этой работы устанавливаем в момент .

4. Проверяем, все ли работы проекта рассмотрены. Если все, то решение закончено; если нет, то возвращаемся к п.1 общего повторяющегося шага.

 

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

Рис. 10.12

Известно, что в распоряжении руководителей работ имеется 30 человек. Требуется распределить трудовые ресурсы во времени, т.е. определить сроки начала и окончания работ так, чтобы с имеющимися трудовыми ресурсами выполнить работы в минимальный срок, равный критическому пути для графика: t_кр=16.

Решение. П р е д в а р и т е л ь н ы й ш а г. Расчет временных параметров сетевого графика по четырехсекторной схеме.

Критический путь: 1 – 3 – 4 - 6, t_кр=16. Используя формулы,

находим их значения.

Результаты расчетов сведем в таблицу:

№	()
	(1, 2)
	(1, 3)
	(2, 3)
	(2, 4)
	(3, 4)
	(3, 5)
	(4, 5)
	(4, 6)
	(5, 6)

Построим линейный график Ганта (рис.10.13) по ранним срокам начала и окончания работ: начало каждой работы совпадает с ожидаемым сроком свершения ее начального события. Над горизонтальными отрезками написано число исполнителей работы.

 

 

 

Рис. 10.13,

 

Рис. 10.13,

 

Строим эпюру интенсивности потребления без учета его ограниченности (рис 10.13,б). Найдем на диаграмме критический путь: работа (4,6) заканчивается позже всех, через 16 дней после начала выполнения проекта. Следовательно, она критическая и = 16. Работа (4,6) начинается в момент 11. Находим работы с конечным событием (4), которые заканчиваются в это же время. Имеется только одна такая работа (3,4). Следовательно, она критическая. Работе (3,4) предшествует критическая работа (1,3). Таким образом, =(1 – 3 – 4 – 6).

П е р в ы й ш а г.

1. Проектируем на ось времени t начала и окончания каждой работы. Определяем и (следующая проекция).

2. Над промежутком расположены работы (1, 2) и (1, 3). Так как сумма ресурсов для их выполнения 10+20=30 не превышает наличных ресурсов в 30 человек, то оставляем их в первоначальном положении. Так как =20 > > 10, то работе (1, 3) присваиваем номер 1, а работе (1, 2) номер 2.

3. Анализируем промежуток = (1, 3). Над ним работы (1,3), (2,3) и (2, 4). Сумма интенсивностей ресурсов 20 + 10 + 8 = 38 больше наличного ресурса в 30 единиц. Присваиваем номера работам. В первую очередь выполняются работы, начатые в промежутке = (0, 1) – это работа (1, 3).

Ее интенсивность = 20. Оставшиеся работы (2, 3) и (2, 4) упорядочим согласно возрастанию их полных резервов времени R_n(i,j): R_n(2, 3) = 1, R_n(2, 4) = 8. Следовательно, в момент = 1 начинаем выполнять работу (2, 3): + += 20 + 10 = 30, и присвоим ей номер 3. Начало работы (2, 4) сдвигаем к моменту = 3 . Результаты сдвига отражены на новой линейной диаграмме (рис.10. 14).

 

 

Рис. 10.14

 

 

4. Сдвинув работу (2, 4) к моменту = 3, замечаем, что в промежутке = (3, 4) интенсивность потребления ресурса = 38 > 30 превышает наличный ресурс в 30 единиц. Так как работы (1,3) и (2,3) начаты в предыдущих промежутках, то работу (2, 4) сдвигаем до момента = 4. В результате сдвига получаем новую линейную диаграмму (рис.10. 15).

 

Рис.10. 15

 

 

5. Начало нового промежутка совпадает с началом работы (2, 4), конец - с окончанием работы (1, 3). В промежутке = (4, 5) интенсивность потребления ресурса = 20+8 = 28 < 30. Следовательно, работе (2,4) присваиваем номер 4.

6. Начало нового промежутка совпадает с = 5, а конец = 6. При = 5 заканчивается работа (1,3) и начинаются работы (3,4) и (3,5). При = 6 заканчивается работа (2, 4).

В промежутке = (5, 6) интенсивность потребления ресурса превышает наличный запас ресурса: = 8+19+11 = 38 > 30. Так как работа (2, 4) начата в предыдущем промежутке, то выполнению в начале промежутка подлежат работы (3, 4) и (3,5). Их резервы времени: R_n(3, 4) = 0, R_n(3, 5) = 3. Следовательно, в момент = 5 нужно начать работу (3, 4). Ей присваиваем номер 5. Начало работы (3, 5) сдвигаем к моменту = 6. Результаты сдвига отображаем на новой линейной диаграмме, рис.10.16.

 

Рис. 10.16

 

7. На промежутке = (6, 11) интенсивность потребления + +=19+11=30 равна наличному запасу ресурса. Времена начала этих работ оставляем без изменения.

8. На промежутке интенсивность потребления = =18+16=34 > 30. Так как R_n(4, 6) = 0, R_n(5, 6) = 2, то следует сделать сдвиг работы (5, 6) до момента = 16. Однако это приведет к удалению общей продолжительности реализации работ до величины 16+3=19.

Можно поступить иначе. Работа (5, 6) имеет резерв времени 2 дня. Увеличим ее продолжительность с 3 до 4 дней, сократив количество человек, занятых ежедневно на этом участке до 12 (3∙16 = 4∙12). В результате получим окончательный линейный график и эпюру ежедневной потребности в трудовых ресурсах на рис. 10.17. Интенсивность использования трудовых ресурсов приведена в соответствие с ограничениями на ресурсы без изменения критического пути.

Рис. 10. 17,

 

Srij

t

 

Рис. 10. 17, . Эпюра ежедневной потребности в трудовых ресурсах.