Содержание к диссертации
Введение
1. Состояние вопроса. Постановка задачи 9
1.1. Некоторые свойства задач теории расписаний 9
1.2. Составление графика движения бригад по объектам 24
1.3. Календарное планирование строительно-монтажных работ на основе нечетких временных отношений 35
1.4 Цель и задачи исследования 46
2. Методологические подходы к составлению расписаний выполнения строительно-монтажных работ 48
2.1 Алгоритм составления расписания для различных исполнителей с минимальной длительностью выполнения множества работ 48
2.2. Минимаксный алгоритм составления расписания строительно-монтажных раб от 60
2.3. Выводы по главе 69
3. Модели распределения ресурсов при организации строительно го производства 71
3.1. Модель вертикального агрегирования ресурсов при планировании строительно-монтажных работ 71
3.2. Алгоритм решения обратной задачи распределения неоднород ных ресурсов
3.3 Выводы по главе 84
4. Формирование оптимальной производственной программы строительного предприятия 86
4.1. Модель выбора рационального варианта технологического про цесса строительного производства 86
4.2. Определения рационального совмещения работ при поточном методе строительства 98
4.3. Выбор рационального варианта строительного производства с учетом совмещений работ по времени 106
4.4. Выводы по главе 109
Заключение 111
Список литературы
- Календарное планирование строительно-монтажных работ на основе нечетких временных отношений
- Минимаксный алгоритм составления расписания строительно-монтажных раб
- Алгоритм решения обратной задачи распределения неоднород ных ресурсов
- Определения рационального совмещения работ при поточном методе строительства
Календарное планирование строительно-монтажных работ на основе нечетких временных отношений
Исследуются свойства наиболее ранних и максимально возможных (поздних) времен начала выполнения операций расписаний фиксированной длины. На их основе строятся математические модели в виде задач целочисленного линейного программирования с булевыми переменными существенно меньшей размерности, чем это было известно ранее. Предлагаются алгоритмы решения методами последовательных приближений.
Организационно – технологическая модель строительства объекта предусматривает формирование решения по возведению зданий, которое рассматривается в составе организации и технологии выполнения процессов при строительстве. Имеется в виду, что организация характеризует последовательность, направление развития и продолжительность процессов, в результате которых создаются разные виды конструкций, а технология определяет для каждого из этих процессов схему производства, методы использования машин, состав оборудования и потребность в рабочих, а также температурный, влажностный и другие режимы.
Организация строительства зданий проектируется с применением в настоящее время нескольких расчетных методов. Система потока, которая по существующей методике проектируется на основе выбора из нескольких наиболее целесообразных, с точки зрения проектировщика, вариантов с оценкой их по показателям качества потока или оптимальному расходу ресурсов [12]. Оба эти способа не предусматривают рассмотрения многих возможных технических решений, не анализируют условия размещения конструкций, изменение в последовательности проведения и направлении развития процессов при возведении конструкций и частей здания. В результате этого не всегда выбирается наиболее рациональный из возможных вариантов, тем более, что общепринятые показатели определяют каждое из качеств в отдельности и не предназначены для комплексной оценки решения.
Для планирования строительных процессов и управления их выполнением наряду с потоком применяется метод сетевого планирования [15]. Применение сетевых моделей в строительстве позволяет контролировать и корректировать выполнение совокупности процессов по. временным или ресурсным оценкам. Полученные данные обосновывают необходимость изменений в технологии возведения зданий, позволяют сократить объем оперативной информации и вскрывают потенциальные трудности, которые могут возникнуть при дальнейшем осуществлении строительства.
Однако сетевые методы, определяя критический путь, далеко не всегда дают возможность установить, какой план в зависимости от технического решения будет лучшим, и в ряде случаев не показывают способов эффективного его обеспечения. В последнее время этот недостаток во многом компенсируется использованием математического программирования [13, 14]. Важным этапом в совершенствовании организации возведения объектов явилась разработка кибернетических систем управления производством и строительством [15, 16]. Однако аналитический метод расчета оптимума с использованием средств математического анализа и достижений кибернетики не получил еще необходимого применения. Строительство крупных гражданских зданий, сблокированных промышленных корпусов или других сложных объектов непосредственно связано с комплексным решением ряда многовариантных задач по выбору номенклатуры процессов, условий их развития, членения здания на части и другие, что обосновывает необходимость разработки способа, с помощью которого может выбираться наиболее рациональное решение по организации возведения здания.
Технологию строительных процессов проектируют, применяя систему потока и принципы комплексной механизации [20, 21]. При применении системы потока обеспечивается целесообразная увязка процессов во времени, а методами комплексной механизации определяются эффективные средства труда. Однако каждый из этих способов не предусматривает совместного решения обеих задач, что необходимо для выбора общего оптимума.
В последнее время для расчета процессов предложен энергетический метод, основанный на использовании закономерностей взаимодействия рабочих органов оборудования с перерабатываемой ими продукцией [22]. Однако и этот метод не охватывает вопросов технологии возведения и в принятой интерпретации не предусматривает выбора оптимальных решений. Ни один из указанных методов не содержит многовариантного анализа решений с комплексной оценкой затрат времени, мощности и стоимости производства. Между тем в заводской технологии для этой цели уже используются экономико-математические модели [23]. Далеко не полно применяется такой анализ и в проектировании процессов строительного производства. Основные задачи технологии процессов принято решать способами, в большинстве из которых используется метод выбора проектного решения путем технико-экономической оценки ряда вариантов. Следовательно, для проектирования технологии выполнения процессов, так же, как и для их организации, необходимо разработать практически удобный способ выбора оптимального варианта. Это даст возможность в дальнейшем находить наиболее эффективное общее решение по возведению объекта и учитывать его в системе управления строительством.
Минимаксный алгоритм составления расписания строительно-монтажных раб
В теории расписаний часто рассматриваются алгоритмы, основанные на уровневом разбиении графов [19, 26]. Известно, что алгоритмы HLF (higher level is first) и LLL (lower level is last), являющиеся оптимальными для деревьев - при одинаковых длительностях исполнения работ (вершин графа), и алгоритм, предложенный в [22], оптимальный для случая двух исполнителей и ациклического графа при одинаковых длительностях работ, являются уров-невыми алгоритмами.
В [38] показано, что для трех исполнителей может быть построен граф, для которого отношение длины расписания t, построенного по «наилучшему» уровневому алгоритму, к длине оптимального расписания tmin составит 5/4 при условии одинаковой длительности исполнения каждой работы. Для любого числа исполнителей может быть построен граф предшествования, для которого указанное выше отношение при том же условии будет: tмин 2m +1 где m — число исполнителей. Конструкция такого графа представлена на рис. 2.1. Согласно уровневому алгоритму в таком графе первые m-1 тактов расписания будут заняты выполнением работ множества А. Затем в течение m тактов будут выполняться не более, чем по две работы: по одной из множеств В и С, и, наконец, в течение m тактов будут выполняться работы множества D и последняя работа множества В. Длина оптимального расписания, в котором первые m тактов выполняется по (m-1)-й работе множества А п по одной работе множества А, составляет: A + В + С + \D\
Приведенный пример указывает пределы совершенствования уровне-вых алгоритмов. Естественно возникает желание рассмотреть другие возможные методы построения расписаний и сравнить их с уровневыми, с тем, чтобы в дальнейшем при конструировании эвристических алгоритмов использовать комбинации различных методов.
Оптимальным является алгоритм, в котором очередность назначения работ на исполнение зависит от числа подчиненных работ. При этом важно, что назначение работ производится не по уровневому принципу. Поэтому есть основания надеяться на то, что алгоритмы, построенные по новому методу, будут «ошибаться» на графах, на которых уровневый метод будет работать хорошо, и наоборот. При этом, например, можно пользоваться следующей простейшей комбинацией: для заданного множества работ расписания по различным методам и выбирать из них меньшее по длине.
Задача 2.1. Имеется множество работ S={Jh..., Jn}, на котором задано отношение предшествования , такое, что если J,—Jj, то невозможно J,— Ju т. е. предшествование задано ациклическим графом. На множестве S задана весовая функция f(Jj)=w, определяющая длительность исполнения работы Jt одним исполнителем. Имеется m одинаковых исполнителей. Требуется построить расписание минимальной длительности выполнения множества работ S, такое, чтобы были выполнены следующие ограничения. 1. Если работа Ji предшествует работе Jj (Ji Jj), то выполнение работы Jj не может начаться раньше, чем завершится выполнение работы Ji. 2. Выполнение начатой работы не прерывается. 3. Одновременно на исполнении может находиться не более, чем m работ. В качестве важного частного случая задачи 2.1 можно рассмотреть задачу 2.2, в которой предполагается, что все работы требуют одинакового времени исполнения, равного единице. Еще одной интересной подзадачей является задача 2.3, в которой в качестве дополнительного ограничения относительно задачи 2.2 предполагается, что граф предшествования является деревом.
Деревом называется граф, на вершинах которого задано такое отношение предшествования, что одна вершина графа не может непосредственно предшествовать более, чем одной другой вершине. Вершина Ji называется непосредственно предшествующей вершине Jj, если в графе не существует вершины Jk, для которой одновременно выполнялось бы JiJk и JkJj. «Обращенным» деревом будем называть граф, в котором каждой вершине может непосредственно предшествовать не более, чем одна другая вершина.
Алгоритм решения задачи 3 будем называть алгоритмом 1. Для алгоритма 1 требуется, чтобы все вершины ациклического графа были помечены следующим образом. 1. Всем работам, которые не предшествуют ни одной другой работе, присваивается пометка h(Ji). 2. Для работы Jj, которая непосредственно предшествует работам Jj1,...,JjE, при условии, что пометка этих вершин уже произведена, h(Jj)=wj+max{h(Jjk)}. Здесь h(Jj1),..., h(JjE) соответствуют работам Jj1,...,JjE. Если не помечена хотя бы одна из работ Jih...,JiE, пометка работы пока не производится, переходим к другой работе. 3. П.2 повторяется до тех пор, пока не будут помечены все работы.
Согласно алгоритму 1 расписание составляется следующим образом: как только какой-либо исполнитель освобождается, ему на исполнение назначается работа, все предшественники которой уже выполнены и которая имеет максимальное значение h(J) среди работ, еще не назначенных на исполнение; если имеется несколько работ с одинаковыми значениями пометки, то среди них выбирается произвольная работа; если одновременно освобождается несколько исполнителей, первыми получают работу исполнители с меньшими порядковыми номерами.
Величина h(Jj) определяется максимальной длиной (длительностью исполнения) цепочки от работы Jj до работы, которая не предшествует ни одной другой работе. Если Wj не одинаковы для всех работ, уровневый метод трансформируется в метод «критического пути». Предлагаемый алгоритм 2 работает с пометками n(J), которые для каждой работы J определяются числом последующих работ.
Алгоритм решения обратной задачи распределения неоднород ных ресурсов
Пусть имеется одна бригада и п работ, которые выполняются ей. Длительность выполнения у-ой работы определяется выражением: где т — время перемещения бригады при переходе от обслуживания /-ой работы ку-ой, х. — время выполнения у-ой работы. Требуется определить последовательность выполнения работ, при которой максимальное время выполнения каждой отдельной работы минимально. Рассмотренная задача сводится к известной задаче о коммивояжере в минимаксной ее постановке.
Математически задача может быть представлена в следующем виде. Требуется определить: / = minmax/x (2.6) при ограничениях: ІЛ = Ї ЇХ = W = 6ІЯ j, (2-7) 2=0 ]=0 Ut - U}. +{n + 1)JC.. n,i,j = Ъла,1Ф у, (2.8) x. e{0,l};z,y = 0 7,z y, (2.9) где: Uj 0; U 0 — дополнительные переменные, t — время выполнения j-ой работы, если она выполняется первой о=мо, tio — время перемещения бригады в исходное состояние, если і-ая работа выполняется последней (/: = \jl).
Ограничения (2.6) — (2.9) являются типовыми для задачи о коммивояжере. Условие (2.6) определяет минимаксный характер рассматриваемой задачи.
Практические задачи, которые сводятся к (2.6) — (2.9), могут иметь самый различный физический смысл. Например, к (2.6) — (2.9) сводится задача минимизации расхода ресурса систем при контроле параметров [48].
Для решения задачи (2.6) — (2.9) может быть использован метод ветвей и границ [18]. При этом необходимо определить способ оценки нижней границы и условия построения дерева возможных вариантов.
Обозначим: U — множество переменных х S{ = {х ,х = l} — множество фиксированных переменных, входящих в отдельные ветви дерева возможных вариантов; / = 0,и — количество переменных х фиксированных на единице и включенных в множество S, (при 1=0,S0 фф), Esi ={х,х =0}— множество переменных х., фиксированных на нуле, введение которых в множество S{
приводит к нарушению ограничений (2.7) — (2.9) или неоптимальному результату, Gsl=U\ (S{ uEsl) — множество свободных переменных, из которых производится выбор на очередном шаге решения для включения в множество S{;
Tsl — нижняя граница для целевой функции ветви дерева возможных вариантов, составленной из переменных х є S,,Tsl(x )— нижняя граница для целевой функции, если ху = 0.
Предположим, что 1=0 и S0 0. Найдем в каждой строке и каждом столбце исходной матрицы \\tt..\\so минимальные элементы tih(i = (\n) и t (j = 0, и). Тогда нижняя граница решения может быть определена с помощью выражения: TSo = msx{tih;tRj)h;k = Qji. (2.10)
Для увеличения вероятности отсечения бесперспективных ветвей во множество S0, целесообразно вводить переменную xih или X (i;j = 0;nj Ф j), которая приводит к максимальному увеличению нижней границы при условии, что переменная xjh=0 или xR]=0. Подставляя в матрицу tt.. so tih =00, определяем величину TSo{xih) = ti = min которая характери зует нижнюю границу для целевой функции, если переменная xih (xih = 0) в множество S0, не вводится. С помощью условия: TSo(x1 ) = max [ TSo(xlhy,Tso(xRJ)\ (2.11) определяем переменную х , которая вводится в множество S0. Для исключения изG5o, переменных х єя в матрице t \\ so вычеркиваем строку / и столбец/, соответствующие переменной х , и подставляем t ,t, = оо. На всех последующих шагах вычислительного процесса нижняя граница для целевой функции Ta{l = \ji) и выбор переменной для включения в множество S{ производится с помощью выражений, аналогичных (2.10),
Учитывая, что должны выполняться условия TSi TSi ,TSi ( ) TSi, для определения нижней границы и выбора переменной х можно использовать следующие выражения: i,j=o7n Последовательно используя условия (2.12), (2.13), строим ветвь дерева возможных вариантов, в которую входят переменные xij Sl При L=n получаем первое рекордное решение t0 =TSn , которое используется для отсечения бесперспективных ветвей путем проверки неравенства:
Допустим, что неравенство (2.14) не выполняется при l = n - 1,n - 2,...,L +1 и выполняется при l=L. Так как все ветви дерева вариантов, для которых неравенство (2.14) не выполняется, являются бесперспективными, то для их отсечения в матрице tij Sl вместо элемента, соответ- ствующего переменной xij , введенной в множество Sl , подставим С помощью условий (2.12), (2.13) определяем нижнюю границу для целевой функции и выбираем новую переменную xij для включения в множество Sl . При построении новой ветви дерева возможных вариантов проверяем выполнение неравенства:
Если неравенство (2.15) выполняется при l=n, то получаем новое рекордное решение TSn , которое используется в дальнейшем для проверки неравенства (2.14), (2.15). Вычислительный процесс заканчивается, если условие (2.14) не выполняется при l=n—1,n—2,...,0. В этом случае последнее рекордное решение t0 и соответствующее ему множество переменных Sn является оптимальным.
Определения рационального совмещения работ при поточном методе строительства
Наиболее прогрессивным методом строительства в настоящее время является поточный, основанный на применении принципов непрерывности и равномерности развития технологических процессов. Для создания строительного потока необходимо выполняемый комплекс работ расчленить на составляющие технологические процессы (специализированные по видам работ потока), разделить работы между исполнителями согласно этой специализации, рассчитать производственный ритм развития потока с выделением фронта работ для каждого исполнителя, необходимого для максимально возможного совмещения во времени и пространстве выполнения специализированных потоков.
Построенный таким образом строительный поток (рис. 4.2) обеспечивает сокращение продолжительности всего комплекса работ, и минимизацию простоев фронтов работ, а следовательно, повышение ритмичности выполнения всего строительного процесса.
Последнее обстоятельство во многом зависит от своевременного включения в общий поток каждого очередного технологического процесса. Эта своевременность определяется выполнением необходимого задела работ на предыдущем из двух смежных технологических процессов, открывающего фронт работ последующему. Таким образом, для построения строительного потока на объекте, обеспечивающего совмещение работ исполнителей, необходимо уметь рассчитывать задел по каждому технологическому процессу, обеспечивающий возможность начала работ для следующего исполнителя. Величина этого задела может выражаться либо объемом выполненных работ, либо временем опережения предыдущего смежного процесса.
Предлагаемая методика количественного обоснования размеров рационального технологического совмещения работ при сооружении отдельного объекта предусматривает следующую последовательность расчетов: — определение необходимого фронта работ для каждого технологиче ского процесса; — расчет требуемого количества рабочих для каждого технологического процесса; — расчет продолжительности технологических процессов в зависимости от назначенного числа исполнителей; — определение времени сдвига последующего технологического процесса в зависимости от размера фронта работ; - проверка достаточности резервируемой общей продолжительности технологического цикла для планируемого совмещения работ отдельных технологических процессов.
Определение необходимого нормативного фронта работ для одного исполнителя (рабочего) основано на использовании зависимости между выработкой и конструктивной характеристикой возводимого им конструктивного элемента здания или сооружения. Причем под фронтом работ в данном случае понимается участок здания или сооружения, выделяемый исполнителю (рабочему) и обеспечивающий нормальный технологический процесс в течение не менее смены без переходов его на другой объект или сооружение.
Процесс возведения сооружения, как известно, состоит из ряда технологических циклов, соответствующих определенным видам работ. Каждый технологический цикл в свою очередь состоит из определенного числа технологически связанных процессов (укрупненных работ). Как смежные циклы, так и работы могут выполняться последовательно, параллельно и совмещено относительно друг друга.
Если принять, что интенсивность смежных технологических процессов в потоке должна удовлетворять условие то требуемый фронт работ для каждого i-го процесса, при условии, что i = 1,n, может быть определен следующими соотношениями: где Ji — интенсивность каждого i-го технологического процесса, измеряемая количеством труда в единицу времени; J = (4.7) Тг — трудоемкость каждого технологического процесса; ti — продолжительность соответственно каждого технологического процесса; Фmp — требуемый фронт работы бригады, выполняющей технологический
Пользуясь соотношениями (4.6), нетрудно определить необходимое число исполнителей пЪв — число рабочих в звене выполняющем і-й технологический процесс; т — число звеньев в бригаде, выполняющей і-й технологический процесс. Тогда расчетная продолжительность ti каждого і-го, специализированного технологического процесса в потоке будет равна Vt — объем работ і-го технологического процесса; вт — плановая выработка одного рабочего в смену на і-м технологическом процессе, исчисляемая в тех же единицах, что и объем работ.