Хаустова Дарья Александровна

1. Планирование затрагивает долгий инвестиционный период (большая продолжительность периода планирования);
2. Жесткая регламентация работ (проектно-сметная документация);
3. Необходимость применения календарных методов планирования;
4. Высокая эффективность применения аналогового планирования.

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

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

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

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

Календарное планирование ресурсов используется для увязки сроков сетевого графика с ограниченным наличием ресурсов у предприятия.

Несмотря на то, что строительство каждого объекта в целом уникально, многие этапы работ по разным объектам могут совпадать или отличаться незначительно на вычисляемую величину (на определенный процент). Поэтому целесообразно применять так называемое аналоговое планирование. Например, при определении стоимости строительства жилого дома можно воспользоваться информацией о числе квартир в здании, стоимости квадратного метра площади в аналогичном доме, изменив эту величину на некоторый поправочный коэффициент.[1] За последние 30 лет для составления расписания строительного процесса применялись различные методы:

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

Планируемые практические результаты и прогнозируемые научные. Научная новизна

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

1. Просчитано время выполнения каждой номенклатуры;
2. Синхронизированы работы в пределах номенклатуры с учетом наложенных технологических ограничений при максимальной загрузке оборудования;
3. Получен оптимальный план выполнения работ;
4. Организована возможность перепланирования для поддержания плана в актуальном состоянии.

Цели и задачи работы

Цель магистерской работы - создание экспертной системы планирования и распределения строительных работ. Такая система должна составлять максимально точный календарный план для строительного предприятия. А также иметь возможность оперативного перепланирования для поддержания актуальности плана.

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

Обзор локально

В пределах кафедры АСУ построением календарного плана занималась Сергеева Елена Юрьевна в магистерской работе по теме: "Компьютеризированная подсистема календарного планирования на строительном предприятии". С реферативным содержанием работы можно ознакомиться здесь.

Обзор глобально

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

Алгоритмы построения расписаний без проведения полного или частичного перебора вариантов являются решающими эвристическими правилами и играют важную роль в прикладной теории расписаний. Однако эвристические алгоритмы основаны на приеме, который называется "снижением требований". Он заключается в отказе от поиска оптимального решения и нахождения вместо этого "хорошего решения" за приемлемое время. Методы, применяемые для построения алгоритмов такого типа, сильно зависят от специфики задачи. То есть универсального алгоритма не существует и использование того или иного эвристического правила нужно начинать после того, как конкретная производственная задача была решена разными методами и выбрано более подходящее решение, согласно экспертным оценкам с учетом требуемых ограничений и критериев оптимальности. [4]

Эволюционные и генетические алгоритмы.Ещё со времён Ламарка развитие живого мира рассматривается как процесс постоянного совершенствования (приспособления) особей под влиянием среды. Моделируя отбор лучших планов, как процесс эволюции в популяции особей, можно получить решение задачи оптимизации, задав начальные условия эволюционного процесса, населив виртуальную вселенную существами - носителями информации и указав цель эволюционного процесса.

Генетические алгоритмы, предложенные в начале 70-х годов, являются одним из самых распространённых вариантов реализации эволюционных алгоритмов. Генетические алгоритмы используют аналогию между естественным отбором и процессом выбора наилучшего решения из множества возможных. Носителями решений являются особи, в "хромосомах" которых закодированы те или иные существенные параметры. Ключевой момент здесь - возможность задать функции оценки приспособленности особей (fitness function), ответственной за "половой отбор" (эволюционная аналогия задачи оптимизации: наиболее привлекательная самка выбирает самого статусного самца).

Схема работы генетических алгоритмов выглядит следующим образом.

1. Задается способ кодирования параметров задачи в "хромосомах".
2. Создается исходная популяция (начальное решение).
3. Рассчитывается функция приспособленности каждой особи.
4. Для наиболее приспособленных особей производится "скрещивание" и рождение новых особей, содержащих признаки обоих родителей. При этом передача признаков осуществляется в соответствии с одним из выбранных способов "обмена участков хромосом". Наименее приспособленные особи "отмирают" и заменяются новорожденными.
5. Осуществляется мутация некоторой части особей добавлением в процесс поиска элемента случайности.
6. Шаги 2-5 итерационно повторяются заданное число раз.
7. Из оставшейся популяции выбираются лучшие особи, "хромосомы" декодируются, а получаемое таким образом решение соответствует локальному оптимуму.

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

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

Метод роящихся частиц (particle swarm). Это наиболее простой и, что удивительно, один из самых молодых методов эволюционного программирования, появившийся в середине 90-х годов. Группа исследователей, занимавшихся этологией птиц и рыб, их социальной организацией, пришла к выводу о возможности решения задач оптимизации с помощью моделирования поведения групп животных. В основу метода положен тот факт, что при формировании стаи птицы стремятся к некоторому центру "притяжения", постепенно замедляя скорость полёта.

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

Схема работы алгоритма выглядит следующим образом

1. Создаётся исходная "случайная" популяция частиц.
2. Для каждой частицы рассчитывается целевая функция.
3. Лучшая частица с точки зрения целевой функции объявляется "центром притяжения".
4. Векторы скоростей всех частиц устремляются к этому "центру", при этом чем дальше частица находится от него, тем большим ускорением она обладает.
5. Осуществляется расчёт новых координат частиц в пространстве решений.
6. Шаги 2-5 повторяются заданное число раз.
7. Последний "центр тяжести" объявляется найденным оптимальным решением.

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

Табуированный поиск (Tabu Search). Данная процедура представляет собой вариацию известного метода градиентного спуска с памятью. В процессе поиска ведётся список табуированных (запрещённых для перехода) позиций (из числа уже посещённых и рассчитанных). Критические параметры алгоритма - глубина списка за претов, определение текущего состояния, размер области вокруг текущего состояния. В процессе поиска осуществляются операции аспирации (включение в запрещённый список состояний вокруг текущего состояния) и диверсификации, которая добавляет фактор случайности в процесс поиска.

Моделирование отжига (Simulated Annealing). Метод, разработанный в 80-х годах, основан на аналогии с физическим процессом охлаждения металла и переходом его в состояние с минимальной энергией кристаллической решётки. Изначально он использовался для моделирования поведения системы атомов при разных температурах, но впоследствии был расширен для решения комбинаторных задач.

Схема применения метода достаточно проста.

1. Задается начальное условие.
2. Выбираются соседние состояния и определяется вероятность перехода в каждое из этих состояний, которая зависит от их "энергии".
3. Уменьшается температура (от нее зависит вероятность перехода в новое состояние).
4. Шаги 2-3 повторяются заданное число раз.[4]

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

Началось всё с изучения поведения реальных муравьёв. Эксперименты с Argentine ants, проводимые Госсом в 1989 и Денеборгом в 1990 году послужили отправной точкой для дальнейшего исследования роевого интеллекта. Исследования применения полученных знаний для дискретной математики начались в начале 90-х годов XX века, автором идеи является Марко Дориго из Университета Брюсселя, Бельгия. Именно он впервые сумел формализовать поведение муравьёв и применить стратегию их поведения для решения задачи о кратчайших путях. Позже при участии Гамбарделлы, Тайлларда и Ди Каро были разработаны и многие другие подходы к решению сложных оптимизационных задач при помощью муравьиных алгоритмов. На сегодняшний день эти методы являются весьма конкурентоспособными по сравнению с другими эвристиками и для некоторых задач дают наилучшие на сегодняшний день результаты.

Концепция муравьиных алгоритмов

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

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

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

Обобщённый алгоритм

1. Создаём муравьёв
2. Ищем решения
3. Обновляем феромон
4. Дополнительные действия {опционально}

1. Создаём муравьёв
   • Стартовая точка, куда помещается муравей, зависит от ограничений, накладываемых условиями задачи. Потому что для каждой задачи способ размещение муравьёв является определяющим. Либо все они помещаются в одну точку, либо в разные с повторениями, либо без повторений.
   • На этом же этапе задаётся начальный уровень феромона. Он инициализируется небольшим положительным числом для того, чтобы на начальном шаге вероятности перехода в следующую вершину не были нулевыми.
2. Ищем решения
   • Вероятность перехода из вершины i в вершину j определяется по следующей формуле
   
   

   Где

   - уровень феромона, d - эвристическое расстояние, , - константные параметры.

   
   При =0 выбор ближайшего города наиболее вероятен, то есть алгоритм становится жадным.
   При =0 выбор происходит только на основании феромона, что приводит к субоптимальным решениям. Поэтому необходим компромисс между этими величинами, который находится экспериментально.
3. Обновляем феромон
   • Уровень феромона обновляется в соответствии с приведённой формулой
   
   Где - интенсивность испарения, L(t) - цена текущего решения для k-ого муравья, а Q - параметр, имеющий значение порядка цены оптимального решения, то есть - феромон, откладываемый k -ым муравьём, использующим ребро (i,j).
   
4. Дополнительные действия
   • Обычно здесь используется алгоритм локального поиска, однако он может также появиться и после поиска всех решений.
   

Области применения и возможные модификации

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

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

Перспективными путями улучшения муравьиных алгоритмов являются различные адаптации параметров с использованием базы нечётких правил и их гибридизация, например, с генетическими алгоритмами. Как вариант, такая гибридизация может состоять в обмене через определённые промежутки времени текущими наилучшими решениями.[3]

Обзор нерешенных проблем и задач, сложности при реализации системы

После прорыва в компьютерных технологиях на смену небольшим разрозненным программам, решающим отдельные организационные задачи, пришли крупные программные комплексы, позволяющие решать очень широкий круг задач и создавать более благоприятные условия для пользователя. Появился новый вид программного продукта - автоматизированные рабочие мести (АРМы). Как правило, АРМы охватывают все основные задачи, решаемые соответствующим специалистом (бухгалтером, кладовщиком и проч.), однако они могут требовать привязки к условиям конкретной организации или обновления применительно к новому законодательству, новым нормам. Естественно, что такая доработка по трудоемкости несопоставимо меньше составления новых программ.

Проблемой также является создание на базе разрозненных АРМов единой информационной системы предприятия, охватывающей все основные сферы ее деятельности. Для использования такой системы компьютеры строительной организации, а иногда и связанных с нею сторонних организаций должны объединяться в единую компьютерную сеть. При этом программное обеспечение значительно усложняется, как и усложняется сама аппаратная часть, т.е. появляется множество дополнительных, устройств, связанных с хранением и передачей информации по различным каналам связи, а возникающие текущие задачи в любой сфере деятельности должны решаться с использованием данных всей информационной ("корпоративной") системы.

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

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

Выводы и заключения по работе и перспективы исследования

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

Литература

1. Штовба С.Д. Муравьиные алгоритмы Exponenta Pro. Математика в приложениях, 2003, №4, с.70-75.
2. www.construction-technology.ru
3. Муравьиный алгоритм Статья Чураков Михаил, Якушев Андрей, 2006
4. Планирование и оптимизация Статья Илья Маляренко Источник: КОРПОРАТИВНЫЕ СИСТЕМЫ PC WEEK/RE №27 25 июля, 2006
5. АНАЛИЗ СОВРЕМЕННЫХ МЕТОДОВ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА ПРИМЕНИТЕЛЬНО К ЗАДАЧАМ КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ Кузьменко В. М., Таран С. В. Источник: ВІСНИК Донбаської державної машинобудівної академії № 1Е(6), 2006
6. МакКоннелл Дж. Основы современных алгоритмов. - М.: Техносфера, 2004. - 368 с.
7. Thompson, Jonathan. Ant Colony Optimization.