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

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

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

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

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

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

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

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

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

                                                            (3.1)

Рекомендуемые материалы

                                                                    (3.2)

                               (3.3)

                                     (3.4)

;                                                    (3.5)

.                            (3.6)

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

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

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

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

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

Пример 1.

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

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

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

Решение

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

                   .

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

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

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

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

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

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

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

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

Рис. 3.7. Форма для ввода данных примера 1.

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

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

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

Ответ:

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

Б. Оптимизация комплекса операций по стоимости при фиксированном сроке выполнения проекта

Рассмотрим частный случай оптимизации комплекса операций по стоимости (затратам). Будем предполагать, что затраты на выполнение отдельных операций находятся в обратной зависимости от продолжительности их выполнения. Коэффициент дополнительных затрат (КДЗ)  этой зависимости для операции     вычисляется по формуле

           ,                                                  (3.7)

где  – срочный режим выполнения операции (наименьшая продолжительность),  которому соответствуют   наибольшие затраты   ;  – нормальный режим выполнения операции (наибольшая продолжительность),  которому соответствуют минимальные затраты  .

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

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

Рассмотрим более общий случай,  когда   .

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

           (3.8)

где   .  Учитывая,  что величины    известны, раскроем  скобки в правой части (3.8) и обозначим через  сумму . В результате получим  . Здесь время выполнения операции   равно разности между временем ее окончания    и временем начала   .

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

         .

На неизвестные величины задачи налагаются следующие ограничения:

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

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

                   ;

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

 ;    - номер завершающего события;

переменные должны быть неотрицательными:

;    для всех   ,   при этом    , .

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

Пример 2.

Исходные данные комплекса операций, представленного сетевым графиком     (рис. 3.8),    приведены   в  Табл. 3.2. Требуется оптимизировать сетевой график по стоимости при    .

Рис. 3.8. Сетевой график примера 2.

Таблица 3.2.

Решение

Запишем , для всех , принадлежащих сетевому графику:

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

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

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

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

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

Рис. 3.9. Форма для ввода данных примера 2.

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

В результате решения получим ответ:

Таким образом, при заданном сроке выполнения  проекта  минимальная стоимость его реализации составляет 170 д.е.