Авторефераты по всем темам >>
Авторефераты по техническим специальностям
На правах рукописи
Бородин Алексей Иванович
МОДЕЛИ И МЕТОДЫ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ В СЕТЯХ С УПОРЯДОЧЕННЫМИ СОБЫТИЯМИ ПРИ УПРАВЛЕНИИ ПРОЕКТАМИ
Специальность 05.13.10 - Управление в социальных и экономических системах
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата технических наук
Воронеж - 2012
Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования Воронежский государственный архитектурно-строительный университет.
Научный консультант: доктор технических наук, профессор Бурков Владимир Николаевич
Официальные оппоненты:
Горошко Игорь Владимирович, доктор технических наук, профессор, Академия управления МВД России / кафедра информационных технологий управления органами внутренних дел, начальник кафедры Новосельцев Виктор Иванович, доктор технических наук, профессор, Автономная некоммерческая образовательная организация высшего профессионального образования Воронежский институт высоких технологий / кафедра психологии, педагогики и профессионального образования, профессор
Ведущая организация: Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Ростовский государственный строительный университет
Защита диссертации состоится 25 мая 2012 г. в 1300 часов на заседании объединенного диссертационного совета ДМ 212.033.03 при Воронежском ГАСУ по адресу: 394006, г. Воронеж, ул. 20-летия Октября, 84, ауд. 3220.
С диссертацией можно ознакомиться в библиотеке федерального государственного бюджетного образовательного учреждения высшего профессионального образования Воронежский государственный архитектурностроительный университет
Автореферат разослан 25 апреля 2012 г.
Ученый секретарь диссертационного совета Белоусов В.Е.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Вопросы формирования планов проектных работ относятся в сфере организационно-технологического управления, включающего технологию проектирования, состав проектируемых элементов, формирование нормативной базы на элементы этой технологии и применение информационных технологий для автоматизации и оптимизации соответствующих расчетов. В то же время проблемы мотивации (стимулирования сокращения сроков работ), обеспечения достоверности представляемых данных и т.д. относятся к сфере экономических механизмов управления.
Производство проектной продукции является весьма трудоемким процессом. Проектные организации, кроме собственно выпуска проектносметной документации, оказывают инжиниринговые услуги: консультативную помощь при подготовке заказчиком (инвестором) исходных данных для проектирования, при согласованиях проекта, осуществляют авторский надзор и др. При этом в качестве используемых ресурсов привлекаются специалисты-проектировщики различных специальностей: архитекторы, конструкторы, технологи, теплотехники, сантехники, электрики и т.д. Они активно взаимодействуют друг с другом в процессе работы над проектом, обмениваются наработанным материалом, проводят множество промежуточных согласований. Проблема рационального использования этих ресурсов при параллельной разработке множества проектов равнозначна проблеме обеспечения успешной работы фирмы.
Анализ моделей распределения ресурсов при выполнении проектных работ показал, что основная совокупность имеющихся средств решает проблему распределения ресурсов на стадии предпроектного проектирования, когда определена номенклатура работ, подлежащих выполнению, и конкретные исполнители.
Но вопрос о размещении единиц проектирования во времени, определения исполнителей, в том числе и субподрядных, как правило, в анализируемых моделях не рассматривается.
Следовательно, актуальность темы диссертационной работы определяется необходимостью разработки эффективных моделей и алгоритмов оптимизации проектных работ, позволяющих рационально распределить ресурсы проектной организации во времени и пространстве, а также между собственными структурными подразделениями.
Основные исследования, получившие отражение в диссертации, выполнялись по планам научно-исследовательских работ:
федеральная комплексная программа Исследование и разработки по приоритетным направлениям науки и техники гражданского назначения;
госбюджетная научно-исследовательская работа Разработка и совершенствование моделей и механизмов внутрифирменного управления.
Цель и постановка задач исследования. Целью диссертации является разработка комплекса моделей календарного планирования проектных работ с учетом ограничений, накладываемых на численность проектировщиков.
Достижение цели работы потребовало решения следующих основных задач:
1. Проанализировать современные проблемы управления процессом распределения ресурсов при выполнении проектных работ.
2. Получить модель оптимального размещения единиц проектирования во времени с учетом целочисленности распределяемых ресурсов.
3. Дать постановку и предложить метод решения задачи максимизации объема выполненных работ при условии, что все работы начинаются одновременно.
4. Разработать модель оптимального размещения единиц проектирования во времени.
5. Построить модель оптимальной передачи части проектных работ на субподряд.
6. Получить модель минимизации штрафов за срыв допустимых (плановых) сроков выполнения проектных работ.
7. Разработать модель построения календарных планов проектностроительных работ Методы исследования. В работе использованы методы системного анализа, математического программирования, теории графов.
Научная новизна результатов работы состоит в следующем:
1. Получена модель оптимального размещения единиц проектирования во времени, отличающаяся учетом целочисленности распределяемых ресурсов, что позволяет получить максимальный объем выполняемых работ.
2. Дана постановка и предложен метод решения задачи максимизации объема выполненных работ при условии, что все работы начинаются одновременно.
3. Разработана модель оптимального размещения единиц проектирования во времени, отличающаяся учетом времени возможного начала и окончания каждой из работ, что позволяет свести задачу календарного планирования к задаче о нахождении максимального потока в специальным образом построенной сети.
4. Построена модель оптимальной передачи части проектных работ на субподряд по критерии минимальной стоимости, отличающаяся тем, что уровень используемых ресурсов непостоянен и сроки начала и завершения всех работ различны.
5. Получена модель минимизации штрафов за срыв допустимых (плановых) сроков выполнения проектных работ, отличающаяся учетом ограничений на количество используемых ресурсов по каждой работе и различными плановыми сроками завершения работ.
6. Разработана модель построения календарных планов проектностроительных работ, отличающаяся использованием эвристических алгоритмов распределения ресурсов в соответствии с приоритетами работ; рассмотрены четыре вида приоритетов; в результате численных экспериментов было установлено правило, дающее в 99 % случаев лучшее решение.
Достоверность научных результатов. Научные положения, теоретические выводы и практические рекомендации, включенные в диссертацию, обоснованы математическими доказательствами, расчетами на примерах, производственными экспериментами и проверкой разработанной системы при внедрении в практику управления строительных организаций.
Практическая значимость и результаты внедрения. На основании выполненных автором исследований разработаны модели и алгоритмы, позволяющие получать оптимальные планы работы как всей проектной организации, так и ее структурных подразделений.
Использование разработанных в диссертации моделей и механизмов позволяет многократно применять разработки, тиражировать их и осуществлять их массовое внедрение с существенным сокращением трудозатрат и средств.
Разработанные модели используются в практике работы ООО УК Жилпроект (г. Воронеж), ЗАО Воронежэнергопроект (г. Воронеж) и ЗАО Проектный институт Гипрокоммундортранс (г. Воронеж).
Модели, алгоритмы и механизмы включены в состав учебного курса Исследование операций при моделировании социально-экономических систем, читаемого в Воронежском государственном архитектурностроительном университете.
На защиту выносятся:
1) модель оптимального размещения единиц проектирования во времени с учетом целочисленности распределяемых ресурсов;
2) модель оптимального размещения единиц проектирования во времени при начале всех работ в одно и то же время;
3) общая модель максимизации объема выполненных работ, где соответствующая задача сводится к задаче о максимальном потоке;
4) модель оптимальной передачи части проектных работ на субподряд;
5) модель минимизации штрафов за срыв допустимых (плановых) сроков выполнения проектных работ;
6) модель построения календарных планов проектно-строительных работ.
Апробация работы. Основные результаты исследований докладывались и обсуждались на международной конференции Современные сложные системы управления (г. Тверь, 2009 г.; г. Старый Оскол, 2012 г.); 65-й всероссийской научно-практической конференции Инновации в сфере науки, образования и высоких технологий (г. Воронеж, 2010 г.); 64Ц67-й научнотехнических конференциях по проблемам архитектуры и строительных наук (г. Воронеж, 2009-2012 гг.).
Публикации. По теме диссертации опубликовано 7 научных работ, в том числе 2 работы опубликованы в изданиях, рекомендованных ВАК РФ.
ичный вклад автора в работах, опубликованных в соавторстве, состоит в следующем: в работах [2], [7] автору принадлежит модель оптимального размещения единиц проектирования во времени с учетом целочисленности распределяемых ресурсов; в работе [1] - модель оптимального размещения единиц проектирования во времени; в работе [6] - модель оптимальной передачи части проектных работ на субподряд; в работах [4], [5] - модель минимизации штрафов за срыв допустимых (плановых) сроков выполнения проектных работ; в работах [3], [7] - модель построения календарных планов проектно-строительных работ.
Объем и структура работы. Диссертация состоит из введения, трех глав, заключения, списка литературы из 179 наименований и приложений.
Общий объем работы составляет 141 страницу машинописного текста, включая 49 рисунков и 51 таблица.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обосновывается актуальность темы, описываются цели и задачи исследования, научная новизна и практическая значимость полученных результатов.
В первой главе приводится ряд постановок задач календарного планирования при проведении проектных работ.
Задача 1. Оптимальное размещение единиц проектирования во времени.
Примем, что проект состоит из n единиц проектирования (проектных работ или далее, просто работ). Технология проектирования (необходимая очередность выполнения работ) задана сетевым графиком, вершины которого соответствуют работам, а дуги - зависимостям между работами. Для каждой работы определены ранние допустимые сроки начала di, поздние допустимые сроки окончания Di и продолжительность работы. Очевидно, i Di di.
i t Кроме того, для каждой работы задан график потребности в ресурqij сах относительно начала работы, то есть tiн t tiн i. Предполагаем также, что задан вектор наличия ресурсов, j 1,m (m - число видов ресурсов), Qt j определяемый на всем горизонте планирования. Требуется определить календарный план выполнения проектных работ в заданные сроки так, чтобы минимизировать перегрузку ресурсов. В такой постановке задача относится к классу NP - трудных задач и не имеет эффективных методов решения.
Мы представили эту задачу в более простом виде, учитывая определенную гибкость назначения исполнителей на работы. А именно, примем, что моменты di и Di, j 1,m соответствуют событиям сетевого графика. Таким образом, плановый период T разбит на интервалы между событиями длительности и количествам ресурсов Ns, s 1,r, где r - число интервалов.
s Такие сетевые графики называются сетями с упорядоченными событиями.
Обозначим Ri - множество интервалов, в которых может выполняться работа i, Ps - множество работ, которые могут выполняться в s-м интервале.
Заданы ограничения на объем проектных работ каждого вида в каждом интервале. Для каждой проектной работы, в свою очередь, задан объем работ, выполняемый ресурсами каждого вида. Более того, примем, что каждая работа выполняется только одним видом ресурсов. Таким образом, все работы разбиты на m подмножеств, так, что работы j-го подмножества выполняющиеся ресурсами j-го вида. Обозначим через xis объем i-й работы, выполняемый в s-м интервале, Cis - максимальный объем i-й работы, который можно выполнить в s-м интервале. Задача заключается в определении xis, i 1, n, s 1,r, так, чтобы все работы были выполнены, то есть xis Cis, i Ps, s 1,r, xis Wi, i 1, n (1), s Ri где Wi - объем i-й работы, а перегрузка исполнителей (то есть превышение объема работ над тем объемом, который могут выполнить исполнители, работая по нормативам) была минимальной. Если обозначить через относительный уровень перегрузки ресурсов, то формально критерий можно записать в виде min при ограничениях xis Qsj, j 1,m. (2) i Ri Фактически мы перешли от задачи календарного планирования к задаче объемно-календарного планирования.
Задача 2. Оптимальная передача на субподряд. Если перегрузка ресурсов недопустимо велика, то естественно снизить ее за счет передачи части работ на субподряд. Обозначим через Р множество работ, передаваемых на субподряд, Ci - стоимость i-й работы при передаче ее на субподряд. Задача заключается в определении множества Р, такого, что стоимость субподрядных работ C(P) Ci i P была минимальной при ограничениях (1), i P и (2) для всех i P и 1.
Другими словами, требуется минимизировать затраты на субподрядные работы, при условии что остальные работы могут быть выполнены своими силами без перегрузки ресурсов (либо при допустимой перегрузке ресурсов ).
доп Задача 3. Минимизация штрафов за срыв допустимых (плановых) сроков выполнения работ. Если передача на субподряд невозможна по тем или иным причинам (отсутствие соответствующих организаций, высокая стоимость работ и др.), то произойдет задержание в окончании тех или иных работ, что приведет к штрафам. Задача состоят в разработке календарного плана, при котором суммарные штрафы за срыв плановых сроков минимальны.
Механизм штрафов часто действует совместно с механизмом премирования за досрочное выполнение работ.
Ряд постановок задачи были рассмотрены в работах Нгуен Тхи Куинь Чанг, которая предложила как точные, так и эвристические алгоритмы решения.
Во второй главе рассматривается оптимальное размещение единиц проектирования во времени.
Первоначально рассматривается случай, когда все di=d и Di=D, i=1, n.
Далее принимаем d=0, а уровень ресурсов Ns = N, s 1,r.
В этом случае минимальная продолжительность реализации всех работ определяется выражением Tmin = max [W ; maxi i ], (3) N Wi где W= Wi, i =, i= 1, n.
i ai W Если Tmin =, то все работы могут выполняться одновременно и заN канчиваться в момент Tmin, при этом количество ресурсов на i-й работе равно Wi ui=, i= 1, n.
N Заметим, что ui может быть нецелым числом. При большом числе проектировщиков ошибка незначительна. Однако при малом числе проектировщиков ошибка может оказаться существенной.
В работе показано, что всегда можно получить целочисленный календарный план с тем же временем выполнения всех работ.
Теорема 1. Существует целочисленный календарный план продолжительности Tmin.
Опишем алгоритм определения моментов окончания всех работ. Пусть Tmin > W.
N W 1 шаг. Выделяем множество P1 работ, таких что, i P1.
i N Для этих работ ui =ai, ti =,i P1. Вычисляем i W W (P1) T1, N A(P1) где W(P1) = Wi, A(P1) = ai.
i P1 i PОпределяем множество Р2 работ, таких что T1. Если Р2 = , то задаi i Pча решена и ti = T1,.
Если Р2 , то полагаем ti =, i P2 и переходим к следующему шагу.
i k-шаг. Вычисляем k W W (Pi ) i Tk, k N A(Pi ) i где W(Pi) = Wi, A(Pi) = ai.
i Pi i Pi Определяем множество Рк+1 работ, таких что Tk, i P1 P2 ... Pk.
i Если Рк+1 = , то задача решена. В противном случае переходим к следующему шагу. Согласно теореме 1 из полученного календарного плана всегда можно получить целочисленный план.
Рассмотрим задачу максимизации объема выполненных работ при условии, что уровни ресурсов в интервалах различны. Обозначим V Nk k.
k n Утверждение 1. При заданной сумме W= Wi максимальный объем i работ будет выполнен, если ai Wi= ai = W. (4) A Доказательство. Пусть WV. Положим ai Wi Uik Nk Nk.
A W Объем выполненных работ составит Uik k = V, i,k то есть максимален.
Пусть WV, положим ai W Uik Nk.
A V Объем выполненных работ составит Uik k =W, i,k то есть также максимален.
Доказанное утверждение обосновывает следующий алгоритм решения задачи.
Предварительно объединим все работы с одинаковым в одну обобщенную работу с параметрами = qs и as ai As, где Ps - множество таi Ps ких работ. Пусть работы упорядочены по убыванию qs, т.е. q1 > q2 >... >qh.
1 шаг. Рассматриваем первый интервал длительности с уровнем ресурсов N1. Определяем номер обобщенной работы k, такой что k 1 k (qS qk )AS N1 1 (qS qk 1)AS. (5) s 1 s Определяем q из уравнения k (qs q)As N1 1.
s Получаем k qs As N1 s q =. (6) k As s Получаем объем S-й работы, выполняемый в первом интервале. Он равен xs1 (qs q)* As,s 1,k.
Переходим к следующему интервалу, повторяя шаг 1 с новыми Ps и As.
Алгоритм заканчивается в двух вариантах. В первом варианте рассмотрены все интервалы.
При этом получен календарный план с максимальным объемом выполненных работ в силу утверждения 1.
Во втором варианте после очередного шага оставшиеся уровни ресурсов Nk = N, то есть одинаковые. Получаем случай, также рассмотренный выше.
Рассмотрим теперь случай, когда сроки возможного начала работ различны. Пусть работы упорядочены по возрастанию этих сроков, то есть d1=0d2Еdn.
Заметим, что утверждение 1 остается справедливым для этого случая.
Отсюда следует алгоритм решения задачи.
Предварительно определяем множество Rj работ с одинаковыми di, i=1,r, где r - число различных di. Примем, что d1=0 1 шаг. Рассматриваем интервал [0, d1) и решаем задачу максимизации объема работ множества R1, выполненных в этом интервале. Алгоритм ее решения был описан выше. k шаг. Рассматриваем интервал (dk-1, dk) и решаем задачу максимизации объема работ множества, выполненных в этом интервале, с учетом объRj j k емов, выполненных в предыдущих интервалах, применяя описанный выше алгоритм. r шаг. Рассматриваем интервал [dr-1, dr) и решаем задачу максимизации объема всех работ, выполненных в этом интервале, с учетом работ, выполненных в предыдущих интервалах. Проанализируем еще один частный случай, а именно, примем, что все di=0, а Di различны. В этом случае применим принцип обращения времени. Рассмотрим процесс в обратном времени. В этом случае моменты Di становятся временами возможного начала работы, а моменты di - требуемого окончания. Теперь можно применить описанный выше алгоритм, начиная, естественно, с последнего интервала. 1,n Рассмотрим общий случай, когда различны di и Di, i=. В этом случае применим потоковую модель процесса. Потоковая модель рассмотрена в работах В. Н. Буркова, П. В. Михина, Нгуен Тхи Куинь Чанг и других авторов. Дадим ее описание, следуя в основном работе Нгуен Тхи Куинь Чанг, с небольшими модификациями. Рассмотрим двудольную сеть, состоящую из входа, выхода и двух множеств вершин X и Y. Число вершин множества X равно числу работ, а число вершин множества Y равно числу интервалов. Обозначим Yi множество интервалов, в которых может выполняться i-ая работа, Xk - множество работ, которые могут выполняться в интервале k, xik - объем i-й работы, выполняемый в интервале k. Соединим вход сети 0 с каждой вершиной i множества X дугой пропускной способности Wi, каждую вершину k множества Y соединим дугой с выходом Z пропускной способности Ckz=Nkk. Наконец, вершину i множества X соединим с вершиной k Yi дугой пропускной способности Cik=aik. Имеем ограничения 0xikCik, i Xk, k=1, m, (7) x0i= xik Wi, i=1,n, (8) k Yi xkz= xik Ckz, k 1,m. (9) i X k Легко видеть, что числа x0i, xkz и {xik}, i=1,n, k=1, m, i Xk, k Yi образуют поток в сети, величина которого n x0i = xkz = Ф= xik (10) i k i 1 k Yi равна объему выполненных работ. Рассмотрим произвольную сеть без контуров на дугах (i, j), которой заданы пропускные способности Cij>0. Как известно, потоком в сети называется совокупность чисел 0 xij cij, (i, j) U (U- множество дуг сети), таких что xij = xki (11) k j для всех i0, n, где 0 - вход сети, а n - выход сети. Величиной потока называется = x0i = xjn. (12) i j Задача заключается в определении потока максимальной величины. Для решения этой задачи, как правило, применяется алгоритм ФордаФалкерсона. Рассмотрим другой подход, в основе которого лежит метод сетевого программирования, предложенный в работах В.Н. Буркова и И.В. Бурковой. Для этой цели воспользуемся понятием агрегируемой сети. Напомним, что сеть называется агрегируемой, если путем агрегирования последовательных и (или) параллельных множеств дуг ее можно свести к одной дуге. Задача о максимальном потоке для агрегируемой сети эффективно решается. Таким образом, задача сводится к определению потока максимальной величины в двудольном графе, который легко превратить в сеть, добавив две вершины - вход, из которой исходят дуги к вершинам множества X с пропускными способностями, равными объемам соответствующих работ, и выход, в который заходят дуги из вершин множества Y с пропускными способностяСkz ми, равными, k Y. Если сеть не является агрегируемой, то ее можно превратить в агрегируемую путем разделения ряда вершин. Имеют место следующие теоремы. Теорема 2. Величина максимального потока в агрегируемой сети меньше или равна величине максимального потока в исходной сети. Теорема 3 (двойственности). Существует разбиение пропускных способностей дуг, исходящих из разделенных вершин, такое, что величина максимального потока в агрегируемой сети равна величине максимального потока в исходной сети. Следствие. Если (i,j) дуга, заходящая в разрез минимальной пропускной способности в исходной сети, то все дуги (is, j) так же заходят в разрез минимальной пропускной способности в агрегируемой сети. Из теоремы и следствия получаем необходимые и достаточные условия оптимальности потока в агрегируемой сети: все дуги, исходящие из разделенной вершины, либо заходят в разрез минимальной пропускной способности, либо ни одна из них не заходит в разрез минимальной пропускной способности. Опишем алгоритм. 1 шаг. Делим пропускные способности C0i на qi частей Sij, где qi - число дуг, исходящих из вершины i первого слоя. При этом должны выполняться ограничения Sij Cij, где Cij - пропускная способность дуги (i,j), соединяющей вершину i первого слоя с вершиной j второго слоя. Если C0i Cij, то полагаем xij=Cij, j Qi (Qi - множество исходящих j дуг из вершины i первого слоя). Корректируем пропускные способности дуг (j,z), C, Cjz Cij, j Qi. jz 2 шаг. Рассматриваем все вершины второго слоя. Для каждой вершины j вычисляем min[ Sij;Cjz ], j i R j где Ri - множество дуг, заходящих в вершину j. Если минимум достигается на Cjz, то оставляем Sij без изменений. В противном случае увеличиваем Sij, i Rj, так чтобы Sij = Cjz (если это возможно). Фиксируем соответствующие потоки. Второй шаг повторяется до тех пор, пока на очередном шаге не будет ни одного изменения Sij. Полученные значения Sij определяют поток максимальной величины. Можно не переходить к агрегируемой сети, а указывать разделенные части Sij пропускных способностей C0i непосредственно на дугах (i,j), j Qi. Задача минимизации стоимости субподрядных работ рассматривалась В. Н. Бурковым, П. В. Михиным, Нгуен Тхи Куинь Чанг и др. для случая, когда уровень ресурсов постоянен и сроки начала и завершения всех работ одинаковы. Для общего случая близкая по формальной постановке задача рассматривалась Нгуен Тхи Куинь Чанг (в содержательном плане речь шла о формировании календарного плана ремонта мостовых сооружений). Однако в постановке Нгуен Тхи Куинь Чанг допускалась отдача на субподряд части работы. Рассмотрим задачу в общем случае, при условии что частичная отдача на субподряд не допускается. Для решения задачи применим метод ветвей и границ. Для получения нижних оценок допустим отдачу на субподряд части работы. Рассмотрим критерий n F(x)= Ci (1 xij ), (13) Wi j i где xij - объем i-й работы, выполняемый в j-м интервале, Ci - стоимость i-й работы при ее передаче на субподряд. Заметим, что в множестве всех допустимых значений {xij} имеются и решения, соответствующие отсутствию передачи на субподряд части работы. Это все решения, для которых xij равна либо 0, либо Wi. Таким образом, j решение задачи по критерию (13) дает нижнюю оценку для исходной задачи. Минимизация F(x), в свою очередь, эквивалентна максимизации величины Ci F1(x)= xij, (14) Wi i, j то есть максимизации стоимости потока. Опишем алгоритм максимизации стоимости потока. Пусть C1 C2 Cn.... W1 W2 Wn 1 шаг. Решаем задачу определения потока максимальной величины через вершину 1. k шаг. Решаем задачу определения потока максимальной величины через вершину k, не уменьшающего величины потоков через вершины j Поток, полученный после n шагов, дает оптимальное решение задачи. Полученная оценка используется в методе ветвей и границ. Рассмотрим другой алгоритм решения задачи, который либо дает оптимальное решение, либо нижнюю оценку решения задачи. Для этого обозначим yi=1, если работа i отдается на субподряд, и yi=0 - в противном случае. Очевидно, что необходимым условием выполнения остальных работ является следующее: Wi (1 yi ) Nk k i k или Wi yi W Nk k L. (15) i k Возникает следующая задача: определить y={yi}, минимизирующие C(y)= ci yi (16) i при ограничении (15). Получили классическую задачу о ранце. Если отобранные работы, которые не отдаются на субподряд, могут быть выполнены, то задача решена. В противном случае получаем оценку снизу. Рассмотрим задачу минимизации суммы штрафов за превышение плановых сроков завершения работ с учетом премий за досрочное завершение работ. Пусть ai N, di = 0, Di = D, i=1,n. Для решения задачи применим эвристические алгоритмы распределения ресурсов в соответствии с приоритетами работ. Будем рассматривать ситуацию, когда коэффициенты премий пропорциональны коэффициентам штрафов, то есть bi = ci, i=1,n и 1.Будем рассматривать четыре вида приоритетов: ci ci 1 bi bi qi ;ri ;qi ;ri1. wi i wi i Заметим, однако, что если qi>qj, то и qi >. Аналогично, если ri>rj, то qj и для всех i, j. Поэтому достаточно рассматривать только приоритеты qi ri1 rj и ri. Возникает вопрос, какая система приоритетов дает лучшие решения. Было рассчитано 50 примеров при случайном выборе параметров Wi, ai и ci. Только в одном проценте случаев правило приоритетов {qi} дало лучшее решение, причем отклонение от решения, полученного по правилу приоритетов {ri}, не превышало 10 %. Поэтому можно сделать вывод, что правило приоритетов {ri} явно предпочтительнее правила приоритетов {qi}. В третьей главе приведен пример решения задачи размещения единиц проектирования во времени по данным ООО УК Жилпроект. Рассмотрим составление календарного плана для случая трех работ, которые могут выполняться также в три временных интервала. Соответствующий двудольный граф приведен на рис. 1. Числа в нижних половинах вершин множества X равны объемам работ, а числа в нижних половинах вершин множества Y равны объемам работ, которые могут выполнить ресурсы в соответствующем интервале. Числа у дуг (i,j) равны максимальному объему i-й работы, который может быть выполнен в j-м интервале. На начальном шаге мы взяли Qs = Wi. s i (4) 1 8 (6) (6) 2 (4) 6 (3) (6) 3 10 Рис. Проведем построение агрегируемой сети. Разделим каждую вершину множества Y на несколько вершин, число которых равно числу заходящих дуг. В нашем примере каждая вершина множества Y делится на две вершины. Соответственно делим произвольным образом объемы Qs на две части Rs и Rs*, такие что Rs + Rs*= Qs (рис. 2). Для определения максимального потока в агрегируемой сети обозначим через Pi множество вершин из множества Y агрегируемой сети, смежных с вершиной i множества X. Величина максимального потока равна min[Wi; min(Cis;Rs)] (17) max i s PДля обоснования этой формулы заметим, что если добавить к двудольному графу вход 0 и выход Z, то мы получим агрегируемую сеть. Фрагмент этой сети, содержащий вершину i множества X, показан на рис. 3. (4) 1, (6) (4) 2, (6) (3) (6) 3, Рис. S Ris Cis Wi 0 i Z Cis RisSРис. Применяя к этому фрагменту алгоритм определения потока максимальной величины для агрегируемой сети и суммируя по всем фрагментам, получаем (17). Для рассматриваемого примера имеем =7+6+10=23. m ax Дуги и вершины разреза минимальной пропускной способности показаны на рис. 2 толстыми дугами или вершинами. Видно, что разделенные вершины либо обе принадлежат разрезу (вершины 2 и 2*), либо ни одна из них не принадлежит разрезу (вершины 1.1* и 3.3*). Следовательно, получен поток максимальной величины 23 для исходной сети. Рассмотрим задачу о максимальном потоке для двудольных сетей, то есть сетей, состоящих из двудольного графа и двух добавленных вершин - входа и выхода (рис. 4). Рис. Для преобразования в агрегируемую сеть разделим каждую вершину первого уровня на число исходящих дуг, соответственно разделив пропускные способности дуг (0,i) (рис. 5), пропускные способности поделены пополам. Теперь легче определить поток максимальной величины в полученной агрегируемой сети. Рис. Для примера рис. 5 имеем S11=S13=3, S21=S22=3, S32=5,S33=1. Рассматриваем вершину 1 второго слоя: min[ 3 3;5] 5 C1z. Оставляем Si1 без изменений, i=1,2. Рассматриваем вершину 2 второго слоя: min[ 3 5;5] 5 C2z. Оставляем Si2 без изменений, i=2,3. Рассматриваем вершину 3 второго слоя: min[1 3;5] 4 C3z. Увеличиваем S13 на единицу S13=4, S11=2. Теперь S13+S33=5=C3z. Полагаем x13=4, x33=1, повторяем второй шаг. Рассматриваем вершину 1 второго слоя, поскольку S11 уменьшилось: min[ 2 3;5] S11 S21 C1z. Полагаем x11=2, x21=3. Определяем поток максимальной величины X=15. Потоки по дугам (2,2) и (3,2) определяются неоднозначно, например, x22=2, x32=3. На каждом шаге алгоритма происходит увеличение потока, по крайней мере, на единицу. Поэтому за конечное число просмотров вершин j второго слоя будет получен поток максимальной величины. В заключении сформулированы основные выводы и рекомендации, полученные в ходе выполнения диссертационной работы. Основные результаты работы заключаются в следующем: 1. Анализ моделей распределения ресурсов при выполнении проектных работ показал, что основная совокупность имеющихся средств решает проблему распределения ресурсов на стадии предпроектного проектирования, когда определена номенклатура работ, подлежащих выполнению, и конкретные исполнители. Но вопрос о размещении единиц проектирования во времени, определения исполнителей, в том числе и субподрядных, как правило, в анализируемых моделях не рассматривается. 2. Дана постановка и предложен метод решения задачи максимизации объема выполненных работ при условии, что все работы начинаются одновременно. 3. Получена модель оптимального размещения единиц проектирования во времени, отличающаяся учетом целочисленности распределяемых ресурсов, что позволяет получить максимальный объем выполняемых работ. 4. Разработана модель оптимального размещения единиц проектирования во времени, отличающаяся учетом времени возможного начала и окончания каждой из работ, что позволяет свести задачу календарного планирования к задаче о нахождении максимального потока в специальным образом построенной сети. 5. Построена модель оптимальной передачи части проектных работ на субподряд по критерию минимальной стоимости, отличающаяся тем, что уровень используемых ресурсов непостоянен и сроки начала и завершения всех работ различны. 6. Получена модель минимизации штрафов за срыв допустимых (плановых) сроков выполнения проектных работ, отличающаяся учетом ограничений на количество используемых ресурсов по каждой работе и различными плановыми сроками завершения работ. 7. Разработана модель построения календарных планов проектностроительных работ, отличающаяся использованием эвристических алгоритмов распределения ресурсов в соответствии с приоритетами работ; рассмотрены четыре вида приоритетов и в результате численных экспериментов было установлено правило, дающее в 99% случаев лучшее решение. Основные результаты диссертационной работы изложены в следующих публикациях. Статьи, опубликованные в изданиях, рекомендованных ВАК РФ 1. Бородин, А.И. Методология проблемно-ориентированных задач календарного планирования проектных работ / А.И. Бородин, М.П. Михин, В.В. Зубарев // Системы управления и информационные технологии. - 2012. - № 1 (47). - С. 39 - 41 (личный вклад автора - 2 с.). 2. Бородин, А.И. Моделирование производственной деятельности строительного предприятия / И.С. Суровцев, А.И. Бородин, А.М. Дудин, П.Н. Курочка // Научный вестник Воронеж. гос. арх.-строит. ун-та. Строительство и архитектура. - 2011. - №2(22). - С. 150 - 158 (личный вклад автора - 5 с.). Статьи, материалы конференций 3. Бородин, А.И. Динамические методы оценки экономической эффективности инвестиционных проектов / Т.А. Аверина, А.И. Бородин, Ю.А. Черенков // Управление в организационных системах: сб. ст. - Воронеж, 2009. - С. 110 - 114 (личный вклад автора 2 с.). 4. Бородин, А. И. Выбор оптимального варианта совмещения работ при реализации проекта / С.А. Баркалов, И.Ф. Набиуллин, А.С. Амплеев, 5. А.И. Бородин // Инновации в сфере науки, образования и высоких технологий: сб. ст. - Воронеж, 2010. - № 568 (личный вклад автора 2 с.). 6. Бородин, А.И. Эвристические алгоритмы распределения ресурсов / А.И. Бородин, А.Н. Симоненко // Экономика и менеджмент систем управления. - 2012. - №1 (3). - С. 16 - 25 (личный вклад автора 6 с.). 7. Бородин, А.И. Методы решения задач минимизации стоимости работ, отдаваемых на субподряд / А.И. Бородин, М.П. Михин // Современные сложные системы управления: сб. ст. по материалам междунар. науч.-техн. конф. - Старый Оскол, 2012. - С. 17 - 19. (личный вклад автора 2 с.) Учебные пособия 8. Бородин, А.И. Управление инновационными проектами [Текст] // В кн.: Инновационный менеджмент Т.А. Аверина, С.А. Баркалов, И.С. Суровцев / Томск, Томский политехнический институт, 2011. - с. 141 - 189 (личный вклад автора). Бородин Алексей Иванович АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Подписано в печать 23.04.2012. Формат 6084 1/16. Усл. печ. л. 1,0. Бумага писчая. Тираж 100 экз. Заказ № ______. Отпечатано: отдел оперативной полиграфии Издательства учебной литературы и учебно-методических пособий Воронежского ГАСУ 394006 г. Воронеж, ул. 20-летия Октября,
Авторефераты по всем темам >>
Авторефераты по техническим специальностям