Содержание к диссертации
Введение
Глава I. Задачи распределения ресурсов при выполнении проектных работ 13
1.1. Основные понятия и определения 13
1.2. Постановка проблемно-ориентированных задач 17
1.3. Механизмы распределения ресурсов 20
1 АЭвристические алгоритмы распределения ресурсов 31
1.5. Выводы и постановка задач исследования 39
Глава II. Модели и методы ресурсного планирования комплексов работ 40
2.1. Методы решения многоэкстремальных задач распределения ресурсов 40
2.2. Метод дихотомического программирования 59
2.3. Распределение ресурсов методом дихотомического программирования в общем случае 64
Глава III. Модели и методы формирования производственной программы проектной организации 68
3.1. Оптимальное размещение единиц проектирования во времени 68
3.2. Задача оптимизации объема субподрядных работ 73
3.3. Оптимальное размещение работ между подразделениями проектной организации 89
3.4. Задача совмещения проектных работ 99
Глава IV Формирование оптимальной производственной программы проектно-строительного предприятия 116
4.1 Финансовое состояние ООО УК «Жилпроект» 116
4.2. Распределение единиц проектирования во времени 120
4.3 Определение плана работы структурных подразделений 128
Заключение 132
Литература 133
Приложения 150
- Постановка проблемно-ориентированных задач
- Метод дихотомического программирования
- Задача оптимизации объема субподрядных работ
- Распределение единиц проектирования во времени
Введение к работе
Актуальность темы. В условиях динамичности современного строительного производства, применения новых прогрессивных технологий, значительно возросли требования к организации проектных работ.
Было выявлено первостепенное влияние на деятельность строительных предприятий качества проектных решений, которые во многом предопределяют возможность применения эффективных технологических процессов. Наряду с себестоимостью строительно-монтажных работ и продолжительностью строительства на стадии проектирования формируется основной показатель деятельности строительных предприятий — уровень производительности труда.
Исследования, проведенные А.А. Гусаковым и его школой, показывают, что до 85 % затрат на выполнение строительно-монтажных работ по возведению объекта формируются в процессе проектирования. В тоже время анализ структуры сметной стоимости строительно-монтажных работ показал, что около 60 % затрат зависят от принимаемых проектных решений.
Таким образом, на стадии проектирования закладываются реальные предпосылки успешной реализации планов по возведению конкретного объекта и его стоимостные характеристики.
Вопросы формирования планов проектных работ относятся к сфере организационно-технологического управления, включающий технологию проектирования, состав проектируемых элементов, формирование нормативной базы на элементы этой технологии и применение информационных технологий для автоматизации и оптимизации соответствующих расчетов. В то же время проблемы мотивации (стимулирование сокращения сроков работ), обеспечение достоверности представляемых данных и т.д. относятся к сфере экономических механизмов управления.
Следовательно, актуальность темы диссертационной работы определяется необходимостью разработки эффективных моделей оптимизации пла нов проектных работ, позволяющих сократить сроки и, как следствие этого, повысить качество проектирования.
Основные исследования, получившие отражение в диссертации, выполнялись по планам научно-исследовательских работ:
- МНТП «Архитектура и строительство» 2001-2002 г.г.- №5.15;
- федеральная комплексная программа «Исследование и разработки по приоритетным направлениям науки и техники гражданского назначения»;
- грант РФФИ «Гуманитарные науки» «Разработка оптимизационных моделей управления распределением инвестиций на предприятии по видам деятельности» № Г00-3.3-306.
Цель и постановка задач исследования. Целью диссертации является разработка
Достижение цели работы потребовало решения следующих основных задач:
1. Найти оптимальное размещение единиц проектирование во времени.
2. Определение набора работ, передаваемых субподрядным организациям.
3. Оптимальное размещение работ между подразделениями проектной организации
4. Задача совмещения проектных работ при различных свойствах функции продолжительности и различных критериев оптимизации.
5. Разработать алгоритм определения минимальной продолжительности проекта, обобщающий известный алгоритм определения критического пути в случае жестких зависимостей
6. Построить алгоритм решения задача минимизации стоимости проекта при сокращении его продолжительности за счет совмещения работ.
Методы исследования. В работы использованы методы моделирования организационных систем управления, системного анализа, математического программирования, теории игр.
Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:
1. модель оптимального размещения единиц проектирование во времени.
2. модель определения набора работ, передаваемых субподрядным организациям.
3. модель оптимального размещения работ между подразделениями проектной организации
4. модели совмещения проектных работ при различных свойствах функции продолжительности и различных критериев оптимизации.
5. алгоритм определения минимальной продолжительности проекта, обобщающий известный алгоритм определения критического пути в случае жестких зависимостей
6. алгоритм решения задача минимизации стоимости проекта при сокращении его продолжительности за счет совмещения работ.
Достоверность научных результатов. Научные положения, теоретические выводы и практические рекомендации, включенные в диссертацию, обоснованы математическими доказательствами. Они подтверждены расчетами на примерах, производственными экспериментами и многократной проверкой при внедрении в практику управления.
Практическая значимость и результаты внедрения. На основании выполненных автором исследований разработаны модели и алгоритмы позволяющие получать оптимальное распределение объемов проектных работ с минимизацией перегрузки задействованных ресурсов.
Использование разработанных в диссертации моделей и механизмов позволяет многократно применять разработки, тиражировать их и осуществлять их массовое внедрение с существенным сокращением продолжительности трудозатрат и средств.
Разработанные модели используются в практике реализации строительных проектов в корпорации «Воронеж-Дом» и Воронежском домостроительном комбинате.
Модели и алгоритмы, разработанные в диссертационной работе, включены в состав учебных курсов и дисциплин: «Управление проектами», «Организационно-технологическое проектирование», читаемых в Воронежском государственном архитектурно - строительном университете.
На защиту выносятся;
1. модель оптимального размещения единиц проектирование во времени.
2. модель определения набора работ, передаваемых субподрядным организациям.
3. модель оптимального размещения работ между подразделениями проектной организации
4. модели совмещения проектных работ при различных свойствах функции продолжительности и различных критериев оптимизации.
5. алгоритм определения минимальной продолжительности проекта, обобщающий известный алгоритм определения критического пути в случае жестких зависимостей
6. алгоритм решения задача минимизации стоимости проекта при сокращении его продолжительности за счет совмещения работ.
Апробация работы.
Материалы диссертации, ее основные положения и результаты доложены и обсуждены на международных и республиканских конференциях, симпозиумах и научных совещаниях в 2002-2005гг, в том числе: 1-й Международной конференции по проблемам строительства и энергетики (Тула, 2002 г), Международной научно-технической конференции по теории активных систем (ИПУ РАН, г. Москва 2003 г), Научно-технической отраслевой конференции «Системы автоматизированного управления производствами, предприятиями и организациями горнометаллургического комплекса (Старый Оскол, 2003 г), Международной конференции «Системные проблемы качества, математического моделирования, информационных и электронных технологий» (Москва-Сочи, 2003 г.), Международной конференции «Совре менные сложные системы управления» (Воронеж, 2003 г.; Тверь, 2004 г.; Тула, 2005 г.).
Публикации. По теме диссертации опубликовано 12 печатных работ.
Личный вклад автора в работах, опубликованных в соавторстве, состоит в следующем: В работах [5], [8], [11] автору принадлежит модель оптимального размещения единиц проектирование во времени; в работах [6], [8], [9] автору принадлежит модель определения набора работ, передаваемых субподрядным организациям; в работах [1], [8], [12] автору принадлежит модель оптимального размещения работ между подразделениями проектной организации; в работе [2], [3], [8] автору принадлежит модели совмещения проектных работ при различных свойствах функции продолжительности и различных критериев оптимизации; в работах [7], [8], [10] автору принадлежит алгоритм определения минимальной продолжительности проекта, обобщающий известный алгоритм определения критического пути в случае жестких зависимостей; в работах [4], [8] автору принадлежат алгоритм решения задача минимизации стоимости проекта при сокращении его продолжительности за счет совмещения работ.
Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений. Она содержит 149 страниц основного текста, 61 рисунков, 11 таблиц и 3 приложения. Библиография включает 195 наименований.
Во введении обосновывается актуальность, описывается цели и задачи исследования, научная новизна и практическая значимость.
В первой главе дается описание методологии и основных понятий планирования проектных работ. Организационно-технологическое управление проектными работами осуществляется на основе следующих исходных материалов: нормативно-справочная информация и нормативная база, представление списком подразделений и специальностей, классификатором проектных работ, описание нормативных технологических моделей, кодами и наименованиями классов работ, функциями зависимости оптимальной дли тельности работ от их объемов; исходная информация представленная перечнем позиций (объектов), по каждому заказу, индивидуальные наименования работ, описание планового периода (год, квартал, месяц), данные о состоянии выполнения работ. В результате формирующиеся планы на год и квартал, распределенные по головным исполнителям проекта, планы отделов на квартал, план загрузки подразделений и специальностей, отчет о выполнении, диспетчерские графики.
Традиционное управление технологией и организацией проектирования использует укрупненные нормативы и нормативные расчеты.
В качестве укрупненных нормативов обычно используют «Сборник цен на проектно-изыскательские работы» и «Временные нормы продолжительности проектирования». Их используют двояко: в качестве укрупненных классификаторов выполняемых работ и в качестве нормативной основы оценки объемов работ и их распределения между подразделениями организации.
Поддержание нормативной базы предлагают осуществлять экспертной проверкой, либо путем учета фактических трудозатрат.
При первом способе каждый раз при подборе модели и привязке ее к объекту эксперты оценивают ее пригодность и при необходимости корректируют модель.
При втором подходе в процессе учета хода проектных работ учитываются и фактические трудозатраты на работы. По этим фактическим трудозатратам и фактическим продолжительностям уточняются параметры работ.
По истечении периода существенной длительности (например года) по каждому часто встретившемуся виду для всех работ решают задачу проверки гипотез: принадлежат ли все встретившиеся работы генеральной совокупности с одним средним и дисперсией или имеет место сочетание двух таких совокупностей или более.
Если статистические критерии показывают на значимую вероятность второй гипотезы, эксперты рассматривают фактические данные и делают окончательный вывод о количестве типов работ. Если их два, то исходная модель расщепляется на две, в каждой из которых присутствует лишь один тип оцениваемой работы. Одновременно пополняется номенклатура работ и результатов.
Такой процесс обеспечивает сохранение адекватности системы моделей структуре проектных работ организации.
Рассмотрим ряд постановок задач оптимального планирования проектных работ. Задача 1. Оптимальное размещение единиц проектирования во времени
Примем, что проект состоит из п единиц проектирования (проектных работ или далее, просто работ). Технология проектирования (необходимая очередность выполнения работ) задана сетевым графиком, вершины которого соответствуют работам, а дуги - зависимостям между работами. Для каждой работы определены ранние допустимые сроки начала, поздние допустимые сроки окончания и продолжительность работы. Кроме того, для каждой работы задан график потребности в ресурсах относительно начала работы. Предполагая также, что задан вектор наличия ресурсов, определяемый на всем горизонте планирования. Требуется определить календарный план выполнения проектных работ в заданные сроки так, чтобы минимизировать перегрузку ресурсов. В такой постановке задача относится к классу NP - трудных задач и не имеет эффективных методов решения. Задача 2. Оптимальная передача на субподряд.
Если перегрузка ресурсов недопустимо велика, то естественно снизить ее за счет передачи части работ на субподряд. Задача заключается в определении множества работ, передаваемых на субподряд, такого, что стоимость субподрядных работ, была минимальной. Другими слова, требуется минимизировать затраты на субподрядные работы при условии что остальные работы могут быть выполнены своими силами без перегрузки ресурсов (либо при допустимой перегрузке ресурсов).
Задача 3. Оптимальное распределение работ между подразделениями проектной организации
Данная задача возникает в том случае, когда в организации имеется несколько подразделений, располагающих мощностями ресурсов одного вида. Требуется распределить проектные работы одного вида между подразделениями, так чтобы обеспечить максимально равномерную загрузку всех подразделений. Задача 4. Совмещение проектных и строительных работ
Совмещение работ, то есть параллельное выполнение работ, связанных технологической зависимостью, производятся с целью сокращения продолжительности всего проекта. Однако такое совмещение приводит как правило к увеличению продолжительности совмещаемой работы, поскольку зачастую приходится переделывать проект, либо к увеличению затрат по той же причине. Частным случаем совмещения работ является так называемые мягкие зависимости между работами (зависимость рекомендательного типа) исследованные в работах Буркова В.Н., Колпачева В.Н, Перелыгина А.Л. и др. Такие зависимости могут нарушаться, но их нарушение приводит к росту продолжительности и (или) затрат. В общем случае совмещение может быть частичным (например, 0,5 объема работы выполняются параллельно с другой работы).
Во второй главе рассмотрены постановки задач распределения ресурсов, следуя работе [1]. При этом предполагается, что проект описан в виде комплекса работ в определенными зависимостями между ними. Зависимости между работами отображаются в виде сетевого графика (сети).
Существуют два способа изображения работ в сетевом графике. В первом способе работы изображаются в виде вершин сети, а зависимости между работами - в виде дуг сети. Во втором способе вершины сети соответствуют событиям сети, то есть моментам завершения одной или нескольких работ, а дуги - работам сети, при этом, для отображения всех требуемых взаимосвязей иногда приходится вводить дуги специального вида - фиктивные работы (можно считать, что такие дуги соответствуют работам нулевой продолжительности, не требующим ресурсов).
В третьей главе рассматриваются возможные методы решения поставленных задач оптимального планирования проектных работ.
Рассмотрим сначала случай независимых проектных работ. В этом случае задача решается отдельно для каждого вида проектных работ. Пусть ограничение отсутствует, то есть при наличии ресурсов каждая работа может быть выполнена в одном интервале. В этом случае существует простое правило оптимального распределения ресурсов:
Правило Л. В первую очередь начинаются работы с минимальными поздними сроками окончания.
Рассматривается обобщение алгоритма на случай произвольного сетевого графика и определение рационального объема работ, передаваемых на субподряд.
Совмещение проектных работ, то есть их частично параллельное выполнение позволяет в ряде случаев сократить продолжительность проектирования. Однако, имеются и отрицательные последствия совмещения работ. Во-первых, уменьшение срока завершения работы за счет более раннего ее начала может не дать эффекта, и может привести даже к увеличению срока завершения по причине увеличения продолжительности работы.
Действительно, нарушение технологии проектирования может привести к необходимости вносить изменения в уже проделанную работу, не позволят в полной мере воспользоваться результатами предыдущих работ. Во-вторых, совмещение работ может привести к росту стоимости проектных работ. Рассмотрим ряд задач оптимального совмещения проектных работ.
В четвертой главе рассматривается методы интенсификации проектных работ в строительстве. На основе результатов главы 3 решена задача оптимизации распределения усилий проектной организации, определены объемы работ, которые целесообразно передавать на субподряд.
Постановка проблемно-ориентированных задач
Рассмотрим ряд постановок задач оптимального планирования проектных работ [27]. Задача 1. Оптимальное размещение единиц проектирования во времени Примем, что проект состоит из п единиц проектирования (проектных работ или далее, просто работ). Технология проектирования (необходимая очередность выполнения работ) задана сетевым графиком, вершины которого соответствуют работам, а дуги - зависимостям между работами. Для каждой работы определены ранние допустимые сроки начала а,, поздние допустимые сроки окончания Ь, и продолжительность работы т,. Очевидно, Кроме того, для каждой работы задан график q.} потребности в ресурсах относительно начала работы, то есть t" ,t t" + т,. Предполагая также, что задан вектор наличия ресурсов JQj}, j = l,m (m - число видов ресурсов) определяемый на всем горизонте планирования. Требуется определить календарный план выполнения проектных работ в заданные сроки так, чтобы минимизировать перегрузку ресурсов. В такой постановке задача относится к классу NP - трудных задач и не имеет эффективных методов решения. Мы представили эту задачу в более простом виде, учитывая определенную гибкость назначения исполнителей на работы. А именно, примем, что плановый период разбит на Т интервалов определенной длины А (недели, месяцы, кварталы и т.д.)
Обозначим R, - множество интервалов в которых может выполняться работа і, Р8 - множество работ, которые могут выполняться в s-ом интервале. Заданы ограничения Qtj на объем проектных работ каждого вида в каждом интервале. Для каждой проектной работы, в свою очередь, задан объем работ, выполняемый ресурсами каждого вида. Более того, примем, что каждая работа выполняется только одним видом ресурсов. Таким образом, все работы разбиты на m подмножеств, так, что работы j-ro подмножества выполняющиеся ресурсами j-ro вида.
Если перегрузка ресурсов недопустимо велика, то естественно снизить ее за счет передачи части работ на субподряд. Обозначим через Р - множество работ , передаваемых на субподряд, С, - стоимость і-ой работы при передаче ее на субподряд. Задача заключается в определении множества Р, такого, что стоимость субподрядных работ с(Р)2с,, ІєР была минимальной при ограничениях (1.2.1) для всех і g Р и (1.2.3) для всех і { Р и а = 1. Другими слова, требуется минимизировать затраты на субподрядные работы при условии что остальные работы могут быть выполнены своими силами без перегрузки ресурсов (либо при допустимой перегрузке ресурсов а , адоп).
Данная задача возникает в том случае, когда в организации имеется несколько подразделений, располагающих мощностями ресурсов одного вида. Требуется распределить проектные работы одного вида между подразделениями, так чтобы обеспечить максимально равномерную загрузку всех подразделений. Задача 4. Совмещение проектных и строительных работ
Совмещение работ, то есть параллельное выполнение работ, связанных технологической зависимостью, производятся с целью сокращения продолжительности всего проекта. Однако такое совмещение приводит как правило к увеличению продолжительности совмещаемой работы, поскольку зачастую приходится переделывать проект, либо к увеличению затрат по той же причине. Частным случаем совмещения работ является так называемые мягкие зависимости между работами (зависимость рекомендательного типа) исследованные в работах Буркова В.Н., Колпачева В.Н, Перелыгина и др. Такие зависимости могут нарушаться, но их нарушение приводит к росту продолжительности и (или) затрат. В общем случае совмещение может быть частичным (например, 0,5 объема работы выполняются параллельно с другой работы). Такое совмещение удобно задавать коэффициентом совмещения работы j выполняемую одновременно с работой і [10]. Коэффициент совмещения принимает значения от 0 до 1. В зависимости от величины К., увеличивается продолжительность работы j и (или) затраты не ее выполнение. Зависимость увеличения продолжительности работы j от Кц будем обозначать через а.(К..), а зависимость увеличения затрат через ЬдКц). Требуется определить коэффициенты совмещения работ, ток, чтобы проект был выполнен за время Т, а дополнительные затраты (либо суммарное увеличение продолжительности работ) были минимальными.
Но, как правило, эффективности исполнителей неизвестны руководителю проекта, в лучшем случае известен диапазон возможных изменений. Следовательно, процедура распределения ресурсов принимает двухэтапный характер: на первом этапе происходит сбор информации от исполнителей; на втором - на основе собранной информации осуществляется распределение ресурса каждому исполнителю. Таким образом, исполнители осознают, что сообщаемая ими информация влияет на количество выделяемого им ресурса. В этом случае они будут сообщать такую информацию, которая позволила бы получить максимально выгодное для себя количество ресурса. Естественно, что в этом случае сообщаемая информация может вовсе не соответствовать истинному положению дел. Таким образом, участники распределения ресурсов имеют возможность сознательно искажать информацию с целью получения более выгодного для себя распределения ресурса. Такое явление получило название манипулируемости.
Метод дихотомического программирования
Многие задачи дискретной оптимизации сводятся к следующей постановке: определить вектор х = {ХІ} с дискретными компонентами, минимизирующий аддитивную функцию фМ=2 і(х,) (2.2.1) і=1 при ограничении f(x) b. (2.2.2) Широкий класс функций f(x) допускает дихотомическое представление, такое, что вычисление значений функции сводится к последовательному вычислению значений функций двух переменных. Так функция f(x) = fo[fi(xbx2), f2(x2,x3)] допускает дихотомическое представление (рис. 2.2.1). При этом соответствующие функции f0, fi, f2 удобно представлять в матричном виде (рис. 2.2.2). Рис. 2.2.1. Такое представление широко используется в методах комплексного оценивания программ развития предприятий, регионов, результатов деятельности подразделений, уровня безопасности объектов и др.
Колмогоровым А.Щ67] и Арнольдом В.И. [6] доказаны теоремы о представлении непрерывных функций нескольких переменных суперпозициями непрерывных функций меньшего числа переменных (в частности, двух переменных). Так, например, любая непрерывная функция трех переменных представима в виде [6] ф1,х2,х3) = Ь1(х1,ф1(х2,х3))+Ь2(х1,ф2(х2,Хз))+ п3(х,,фз(х2,х3)) Ее дихотомическое представление (в агрегированном виде) — на рис. 2.2.3.
Поскольку функция дискретных переменных может быть продолжена до непрерывной функции, то, тем более, любая функция дискретных переменных представима в дихотомическом виде. Очевидно, что функция f(x) допускает дихотомическое представление, если все функции fj допускают такое представление.
В задачах комплексного оценивания функция f(x), дающая интегральную оценку объекта, как правило, допускает дихотомическое представление в виде дерева. В этом случае можно предложить эффективный метод решения задачи (2.1), (2.2). На рис. 2.2.4 приведен пример построения интегральной оценки трех показателей, имеющей вид f(xi,x2,x3) = (p0[fi(x,,X2), х3] = Фо(у,х3) Значения функций фі(х;) даны в нижних половинах квадратов, соответствующих переменным Хь Х2 и Хз. Дадим описание алгоритма на примере рис. 2.2.4 [23].
Из всех элементов матрицы имеющих одно и то же значение у = fj(xi,X2) выбираем элемент с минимальной суммой Фі(хі)+ф2(х2). Минимальную сумму записываем в нижнюю половину клетки, соответствующей этому значению у в верхней матрице. Так, например, значению у = 3 соответствуют 5 элементов нижней матрицы: (3;2), (4;2), (3;3), (4;3) и (2;4). Из них элемент (3;2) имеет минимальную сумму 30 (это число записано в нижней половине соответствующей клетки). Поэтому в верхней матрице значению у = 3 соответствует число 30, записанное в нижней половине соответствующей клетки.
Далее шаги 1 и 2 повторяются для верхней матрицы. В результате для каждого значения f(x) мы получаем минимальную величину ср(х).
Несложно обобщить описанный алгоритм на случай произвольного дихотомического представления функции f(x) в виде дерева. Шаги 1 и 2 алгоритма повторяются, начиная с висячих вершин дерева дихотомического представления.
Заметим, что дихотомическое представление рис. 2.2.4 имеет тип ветви дерева. В этом случае метод дихотомического программирования переходит в метод динамического программирования. Таким образом, метод дихотомического программирования в случае, когда дихотомическое представление имеет вид дерева, является обобщением метода динамического программирования, расширяя круг задач, решаемых на основе данного подхода (рис. 2.2.5).
Если в методе динамического программирования решением задачи является путь в некоторой специальным образом построенной сети, то в методе дихотомического программирования решением задачи является частичное дерево в некотором специально построенном дереве.
Рассмотрим произвольное дихотомическое представление функции f(x), задаваемое сетью, входом которой является вершина, соответствующая функции f(x), а выходами - вершины, соответствующие переменным Xj, i = l,n [23]. Рассмотрим множество конечных вершин, которые не являются висячими, то есть их степень захода больше 1. Разделим произвольным образом затраты ФІ(ХІ) на kj частей, где к; - число заходящих дуг. Фактически мы как бы разделили вершину і на к; висячих вершин с соответствующей частью затрат. Далее применяем описанный выше алгоритм. При этом каждый раз, когда встречается вершина, имеющая степень захода больше 1, мы делим затраты на соответствующее число частей. В результате применения алгоритма мы получим оптимальное решение для модифицированной сети. Однако, это решение может не быть решением исходной задачи. Тем не менее, имеет место следующая теорема.
Полученное с помощью вышеописанного алгоритма решение дает нижнюю оценку оптимального решения исходной задачи. Доказательство. Заметим, что множество решений модифицированной сети содержит все решения исходной задачи. Эти решения имеют следующий вид. Если в вершину, соответствующую переменной Xjk заходит хотя бы одна дуга полученного решения, то все дуги, заходящие в эту вершину, также принадлежат полученному решению. Отсюда следует, что полученное оптимальное решение модифицированной задачи дает нижнюю оценку для оптимального решения исходной задачи.
Задача оптимизации объема субподрядных работ
В условиях ограниченных ресурсов для выполнения плана проектных работ в заданные сроки приходится привлекать другие организации. Пусть проектные работы являются независимыми, то есть могут выполняться одновременно. Начнем рассмотрение с простейшего случая, когда зависимость скорости работы yvt от количества ресурсов Uj имеет вид Wi=ui5i = M (3.2.1) В этом случае каждый вид проектных работ можно рассматривать отдельно. Пусть количество ресурсов рассматриваемого вида равно N. В этом случае продолжительность выполнения всех проектных работ определяется выражением W Т = —, (3.2.2) N J где W = w.. Если Т То (То — заданный срок выполнения проектных работ), то часть работ необходимо передать другим организациям, которые смогут выполнить эти работы за время не больше Т0. Обозначим с, - стоимость выполнения і-ой работы на субподряде. Для формальной постановки задачи обозначим Xj = 1, если работа і передается на субподряд, х, = 0, в противном случае.
Мы получили классическую «задачу о ранце», для которой существуют эффективные методы решения [38]. В частности, весьма эффективным явля 74 ется метод дихотомического программирования, который при структуре дихотомического представления, максимально близкий к симметричной, имеет меньший объем вычислений, чем метод динамического программирования.
Кроме того вариант W=9, С=7 доминируется вариантом W=10, С=6, так как большему объему субподрядных работ соответсвуют меньшие затраты. Аналогично вариант W=14, С=10 доминируется вариантом W=15, С=9. Не заполненные клетки матрицы не рассматриваются, поскольку соответствующие варианты не могут быть оптимальными. 2 этап. / шаг В матрице (у5) находим клетку с минимальной стоимостью субподрядных работ среди всех клеток с объемом субподрядных работ не меньше 19. Это клетка у3 = 0, у4 = 19 с величиной стоимости С=13. 2 шаг В матрице (у4) находим клетку с объемом субподрядных работ W=19 и стоимостью С=13. Ей соответствует у, =3 (стоимость 2) и у2 =16 (стоимость 11). 3 шаг В матрице (уз) находим клетку с объемом у3 = 0 (стоимость также равна 0). Ей соответствует, очевидно х5 = х6 = 0, то есть работы 5 и 6 выполняются собственными силами. 4 шаг В матрице (у) находим клетку со значением у2=16 (стоимость также равна 11). Ей соответствует вариант, в котором х3 = х4 = 1, то есть работы 3 и 4 отдаются на субподряд. 5 шаг В матрице (уі) находим клетку со значением yt = 3 (стоимость равна 2). Ей соответствует вариант хх = 1, х2 = 0, то есть работа 1 отдается на субподряд, а работа 2 нет. Окончательно получаем оптимальный вариант, в котором на субподряд отдаются работы 1, 3 и 4 суммарного объема 19 и суммарной стоимостью 13. Заметим, что объем вычислений пропорционален суммарному числу рассматриваемых клеток всех матриц. В нашем примере это число равно 48.
Заметим, однако, что суммарное число клеток в методе динамического программирования равно 56, что больше чем при структуре рис.5.1.. Построенные матрицы (рис. 3.2.2 ч- 3.2.6) позволяют решить задачу при любом b 19, применяя второй этап алгоритма. Так, например, при b = 12, получаем решение , в котором х2 = 1, х3 = 1, С=7.
Учтем теперь коэффициент а перегрузки ресурсов. Если а 1, то возникают дополнительные затраты, связанные, например, с оплатой сверхурочных или выплатой дополнительных премий. Рассмотрим задачу определения оптимального уровня а перегрузки ресурсов. Премии, что дополнительные затраты являются возрастающей функцией от уровня перегрузки. Обозначим эту функцию q(a). Обозначим также Cmin(a) минимальные затраты на субподряд в зависимости от уровня перегрузки а.
В этом случае решение первой задачи изменится хі=0, х2=1, х3=1. Соответственно, оценка снизу будет равна Ф=13. Полученные решения трех задач о ранце уже не дают допустимого решения исходной задачи. Здесь возможно два способа действий. Первый способ (улучшение оценки). Для улучшения оценок увеличим s21 на единицу, соответственно, уменьшив s2I на единицу. При этом, одним из оптимальных решений задачи 1 станет решение Хі=1, х2=0, х3=0, Фі=6. Что касается задачи 2, то решение Х2=0, х3=0, Х4=1. по-прежнему остается оптимальным, Ф2=4, Фз=4, Ф=14. Таким образом, мы опять получили допустимое решение исходной задачи хі=1, х2=0, х3=0. х4=1, х5=1. со значением целевой функции „=14 Второй способ (метод ветвей и границ). Выбираем переменную Xj, которая имеет различные значения в трех задачах о ранце. Пусть, например, это переменная Хз (х3=1 в первой задаче, Хз=0 во второй и третьей задачах). Разбиваем множество всех решений на два подмножества. В первом подмножестве Хз=1, а во втором хз=0. Оценка первого подмножества. Подставляя х3=1, мы получаем следующую задачу: Минимизировать 6х, +5х2+6х4 + 2х5 При ограничении 8х,+5х2 5 4х2+8х4 4 4х4 + 6х5 3 Сохраняя прежние значения s2 и s4, получаем следующие оценочные задачи о ранце. Задача 1. Минимизировать 6x, +3x2 При ограничении 8x,+5x25 Ее решение хі=0, Х2=1, со значением Ф, = 3. Задача 2. Минимизировать 2х2+4х4 При ограничении 4х2+8х4 4 Ее решение Х2=1, х4=0, Ф2 = 2. Задача 3. Минимизировать 2х4 + 2х5 При ограничении 4х4 + 6х5 3 Она имеет два решения х4=1, х5=0 и х4=0, х5=1. со значением Ф3=2. Заметим, что из этих решений можно получить допустимое решение исходной задачи Хі=0, х2=1, х4=0, х5=1, С(х3=1)=15, которая является оптимальным в данном подмножестве. Оценки второго подмножества. Подставляя хз=0, мы получаем следующую задачу: Минимизировать 6х, +5х2+6х4 + 2х5 При ограничении 8х,+5х2 8 4х2+8х4 7 4x4+6xs10 Решение этой задачи очевидно: xi=l, х2=0, х4=1, х5=1, С(х3=0)=14, Выбираем второе подмножество с меньшей оценкой. Итак, мы получили оптимальное решение, в котором на субподряд отдаются работы 1, 4 и 5. Оба способа можно комбинировать, то есть сначала попытаться улучшить нижнюю оценку, изменяя разбиение Cj на sjj, при сохранении условия STs.j = с., а затем применить разбиение на подмножества, j
В заключение рассмотрим один частный случай задачи, для которого удается получить эффективный метод решения. Примем, что имеется m проектов, каждый из которых состоит из двух типов проектных работ, выполняемых последовательно, сначала первый, а затем второй. Все работы первого типа выполняются одной группой проектировщиков (или просто одним проектировщиком). Поэтому они не могут выполняться одновременно. Для выполнения работ второго типа имеется достаточное количество специалистов. Поэтому они могут вестись параллельно. Обозначим через aj - продолжительность работы первого типа для проекта і, через bj - продолжительность работы второго типа для проекта і. Рассмотрим сначала случай, когда ни одна работа не отдается на субподряд.
Распределение единиц проектирования во времени
Предприятие ООО Управляющая компания «Жилпроект» осуществляет разработку проектно - сметной документации для строительных предприятий Воронежского региона.
Примем, что шаг по времени составляет 1 день, при этом будем рассматривать полугодовую программу предприятия. В качестве ресурсов будем рассматривать число проектировщиков, которое равно 90 чел. Применим алгоритм, описанный в [1] для случая независимых проектных работ. В этом случае задача решается отдельно для каждого вида проектных работ. В этом случае существует простое правило:
Правило Л оптимального распределения ресурсов: в первую очередь начинаются работы с минимальными поздними сроками окончания. Таким образом, проекты 1 и 2 выполняются с перегрузкой 24 %, проекты с третьего по шестой с перегрузкой 26 % и остальные проекты с перегрузкой 45 %. То есть, очевидно, что данный производственный план для предприятия с заданными параметрами является чрезвычайно напряженным, особенно в конце планового периода. Для руководства предприятия целесообразно решить вопрос либо о расширении организации, либо же о передаче части работ субподрядной организацией.
Рассмотрим задачу определения объемов работ, передаваемых на субподряд. Для этой цели необходимо определить стоимость каждого проекта в том случае, когда он передан на субподрядное выполнение. Если Т То (Т0 - заданный срок выполнения проектных работ), то часть работ необходимо передать другим организациям, которые смогут выполнить эти работы за время не больше То. Обозначим с, - стоимость выполнения і-ой работы на субподряде.
Мы получили классическую «задачу о ранце», для которой существуют эффективные методы решения [ ]. В частности, весьма эффективным является метод дихотомического программирования, который при структуре дихотомического представления, максимально близкий к симметричной, имеет меньший объем вычислений, чем метод динамического программирования.
Согласно отчетности ООО УК «Жилпроект» за 2004 год, чистая прибыль составила 14507 тыс. р., а себестоимость проданной продукции 29633 тыс. р. Таким образом, рентабельность составит 49 %. Таким образом, передавая работы на субподрядное выполнение, предприятие лишается этой прибыли. Соответствующие данные представлены в табл. 4.2.3.
Общая трудоемкость составляет 10100 чел.-см. Пусть объем, выполняемый собственными силами составит 7200 чел.-см. В этом случае объем работ, передаваемых на субподряд составит 2800 чел.-см.
Компания имеет пять групп, выполняющих проектные работы. Численность каждой из них в среднем составляет 18 специалистов. Возникает проблема распределения портфеля заказов компании между творческими коллективами. В третьей главе п. 3.3 дан алгоритм решения такой задачи. Показано, что эта проблема может быть сведена к известной задаче о «камнях».
Используя данные о производственной программе ООО УК «Жилпроект» (см. табл.4.2.1), запишем исходные данные для задачи распределения объемов работ между структурными подразделениями. Сведения приведены в табл. 4.3.1 (в табл. 4.3.1 объемы работ необходимо умножить на 100). Та 129 ким образом, у нас имеется 10 работ, которые необходимо распределить между 5 подразделениями, то есть в данной задаче будет n=10, пг=5.
В состав управляющей компании ООО «Жилпроект» входи 5 структурных подразделений, занятых выполнением проектных работ. Рассмотрим задачу о распределении заданного объема работ между подразделениями.
Согласно табл. 4.3.1 находим, что А=101, средняя трудоемкость, приходящаяся на одно подразделение - Т0=21. Находим из табл. 4.3.1 множества, удовлетворяющие соотношению Ф(То) А. Такими множествами будут являться: Qi=(U8), Q2=(l,5,10), Q3=(2,6), Q4=(5,8), Q5=(8,10). Для этих множеств оценка Mi=21. Для М2=20 имеем следующие множества: Q6=(l,3), Q7=(l,4,5), Q8=0,7), QsrO,9). Qio=(l,4,10), Qn=(3,5), Q,2=(3,10), Q,3=(4,5,10), QH=(4,8), Q15=(5,7), Q16=(5,9), Q,7=(7,10), Q18=(9,10).
