Определение оптимальной очередности строительства объектов в потоке

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

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

Алгоритм

Постановку задачи в общем случае можно сформулировать следующим образом. Даны n объектов, по которым известны продолжительности выполнения основных строительно-монтажных работ

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

Решение задачи состоит из ряда этапов.

1. Фиксируется произвольная исходная очередность возведения объектов и определяется общая продолжительность строительства при этой очередности:

, 1.6

где

τ_{j = ; 1.7}

Символ δj означает, что суммируются только положительные значения

2. Определяются все возможные комбинации попарного возведения
объектов в очередности i—>к (i k). Очевидно, что общее количество таких
комбинаций будет равно n (n-1).

3. Рассчитываются показатели продолжительности цикла для каждой
пары объектов при очередности i —> k и k -> i.

Продолжительность возведения пары объектов в очередности i —> k определяется по формуле

1..8.

То же при очередности k i:

1.9

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

4. Строится вспомогательная матрица, размерностью n х n
Элементами этой матрицы являются числа 0 и 1. При этом, если Т < T , то на пересечение строки 1 и столбца 1с заносится 1, а на пересечение строки k и столбца i - 0. В случае Т = T , в обе клетки заносится 1.

5. На основе вспомогательной матрицы строятся все полные
допустимые последовательности объектов.

Последовательность объектов i , i ,…, i называет допустимой, если для любой пары смежных объектов i i элемент вспомогательной матрицы в клетке (k, 1) равен 1. Таким образом, переход с объекта к на объект 1 разрешается, если Т < Т . Последовательность объектов является полной, если она содержит все n объектов без повторений.

Полные допустимые последовательности объектов строятся путем последовательного "считывания" вспомогательной матрицы.

6. Среди всех полных допустимых последовательностей объектов
выбирается последовательность, соответствующая минимальной общей
продолжительности строительства.

ПРИМЕР. Рассмотрим алгоритм решения задачи на методическом примере. Заданы четыре объекта, возводимые одним объектным потоком. Исходные данные представлены в табл. 4.

Таблица 4

Матрица исходных данных

i/j

Общая продолжительность строительства при исходной очередности 1-2-3-4 согласно 1.6 составит То= 21+16+6=43

Количество вариантов попарного возведения объектов (т.е. объекта i за объектом к, i k) равно n*(n-1) =4*3=12.

Рассчитаем показатели продолжительности цикла для каждой пары объектов при очередности i —>k и k —> i по формулам 1.8 и 1.9. Расчеты производятся непосредственно на матрице исходных данных.

Т =2+21+2=25

Т =9+14+3=26

Т =1+21+6=28

Т =6+16+3=25

Т =3+14+6=23

Т =2+6+2=20

Т =3+21+8=32

Т =3+19+3=25

Т =4+14+8=26

Т =1+19+2=22

Т =1+19+6=26

Т =0+16+8=24

Результаты расчетов используем для построения вспомогательной матрицы (табл. 5)

Таблица 5

Вспомогательная матрица

Поскольку Т < Т , то в клетку (1,2) заносится 1.

Клетки (1,3) и (1,4) заполняются нулями, так как Т > Т и Т >Т .

Все элементы второй строки матрицы равны 0, так как Т > Т , Т >Т и Т >Т .Аналогично заполняются третья и четвертая строки матрицы.

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

Сначала пытаемся построить такую последовательность, которая начинается с первого объекта. Просмотр первой строки матрицы показывает, что с первого объекта можно перейти на второй объект, так как остальные показатели первой строки равны 0. Таким образом, ни одной допустимой последовательности объектов, начинающейся с первого объекта, в данном случае не существует. Аналогичный результат получается и при попытке построить такую последовательность, начиная со второго объекта.