Этап II. Оптимизация сетевой модели

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

На каждом шаге оптимизации мы снимаем ресурсы с одной некритической работы и передаем их одной или нескольким критическим. Работу, отдающую ресурсы, будем называть донором, а работу, принимающую ресурсы — акцептором.[1] При этом справедлив своеобразный закон сохранения — сколько ресурсов отдал донор, ровно столько и получили акцепторы. Очевидно также, что длительность работы-донора увеличивается, а работы-акцептора соответственно уменьшается.

При этом справедливы следующие формулы пересчета, которыми мы будем пользоваться без доказательства:

¾ новая длительность работы-донора: ,

¾ новая длительность работы-акцептора: ,

Здесь , -коэффициенты пересчета ресурсов донора и акцептора соответственно.

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

¾ во-первых, мы не можем взять у донора больше ресурсов, чем он имеет, поэтому ;

¾ во-вторых, мы можем маневрировать ресурсами только в пределах имеющихся резервов времени, иначе работа-донор настолько растянется, что сама начнет сдерживать выполнение всего комплекса работ[2]. В результате получаем: Þ Þ . Здесь -резерв времени донора, который равен резерву времени того пути, котором он принадлежит.

1 шаг.На первом шаге выбираем путь с наименьшими резервами времени. В нашем случае это четвертый путь. На нем лежат две некритические работы a₅ и a₆ , каждую из которых мы можем выбрать в качестве донора. Остановим наш выбор на работе a₆ (установка оборудования).

Наша цель— «выровнять» длины второго, третьего и четвертого пути, поэтому в качестве акцептора логично выбрать работу, принадлежащую как второму, так и третьему пути. Пусть это будет работа a₄ (завоз товара).

Изобразим это схематично на временной диаграмме:

Рис 3. Перенос ресурсов на 1 шаге оптимизации

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

(1)

Ограничения имеют вид: (2)

Решаем полученную систему уравнений, учитывая соотношения, полученные на этапе I:

Таким образом, снимаем 6,25 ед. ресурсов с работы a₆ и передаем их работе a₄. При этом ограничения (2) выполнены. В противном случае необходимо было бы искать другой вариант переноса ресурсов.

Вычисляем новую длительность работы a₆:

Вычисляем новую длительность работы a₄:

Вычисляем новые длительности путей:

Находим новые ресурсы работы-донора и работы-акцептора:

Строим новую таблицу:

Содержание работы	Обозначение работы	Опорные работы	Выделенные ресурсы bi	Длительность работ ti
Заказ на оборудование	а1	-	5	8
Разработка системы учета спроса	а2	-	5	15
Отбор товаров и выписка счетов	а3	а1	5	6
Завоз товара	а4	а3	16,25	1,125
Завоз оборудования	а5	а1	10	4
Установка оборудования	а6	а5	3,75,	8,125
Выкладка товара	а7	а4	10	5
Учет наличия товара	а8	а4	5	5
Оформление зала	а9	а6, а7	5	3
Изучение документов	а10	а2, а8	5	3
Репетиция	а11	а9, а10	10	2
Проведение ярмарки	а12	а11	20	1

Строим новую временную диаграмму:

Рис. 4. Результаты 1 шага оптимизации

2 шаг.Как следует из рис.4., по итогам первого шага оптимизации остался только один некритический путь (Путь 1) и только одна некритическая работа a₂ (разработка системы учета спроса). Для того, чтобы «уравнять» длины всех путей, необходимо снять допустимую часть ресурсов с работы a₂ и передать их работе или работам, лежащим на остальных путях. Следовательно, на этом шаге донора выступает работа a₂.

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

Изобразим это схематично на временной диаграмме:

Рис 5. Перенос ресурсов на 2 шаге оптимизации

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

(3)

Ограничения имеют вид: (4)

Решаем полученную систему уравнений:

Таким образом, снимаем 1,114 ед. ресурсов с работы a₂ и передаем их работе a₁. При этом ограничения (4) выполнены. В противном случае необходимо было бы искать другой вариант переноса ресурсов.

Вычисляем новую длительность работы a₂:

Вычисляем новую длительность работы a₁:

Вычисляем новые длительности путей:

Находим новые ресурсы работы-донора и работы-акцептора:

Строим новую таблицу:

Содержание работы	Обозначение работы	Опорные работы	Выделенные ресурсы bi	Длительность работ ti
Заказ на оборудование	а1	-	6,114	6,218
Разработка системы учета спроса	а2	-	3,886	18,342
Отбор товаров и выписка счетов	а3	а1	5	6
Завоз товара	а4	а3	16,25	1,125
Завоз оборудования	а5	а1	10	4
Установка оборудования	а6	а5	3,75,	8,125
Выкладка товара	а7	а4	10	5
Учет наличия товара	а8	а4	5	5
Оформление зала	а9	а6, а7	5	3
Изучение документов	а10	а2, а8	5	3
Репетиция	а11	а9, а10	10	2
Проведение ярмарки	а12	а11	20	1

Строим новую временную диаграмму:

Рис. 6. Оптимальная временная диаграмма

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

Экономия времени по сравнению с исходным вариантом распределения ресурсов составила 28-24,342=3,658 дн.

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