Содержание к диссертации
Введение
1. Модели управления проектными работами 10
1.1. Основные понятия управления проектами 10
1.2. Процесс подготовки проектной документации 1 7
1.3. Модели управления процессом проектирования 25
1.4. Задача совмещения выполняемых работ 35
1.5. Выводы и постановка задач исследования 47
2. Разработка календарных планов проектно строительных работ 49
2.1. Постановка задач 49
2.2. Задача Джонсона и ее модификации 50
2.3. Задача оптимального совмещения проектно-строительных работ 69
2.4. Общий случай 93
2.5. Сравнение методов решения задачи планирования проектных работ 101
3. Методика управления проектными работами
3.1. Методика управления проектными работами, реализованная УК
ООО «Жилпроект» 109
3.2. Управление проектированием 112
3.3. Вспомогательные процессы 129
3.4. Вариант календарного плана для УК ООО «Жилпроект» 131
Заключение 135
Литература 136
- Модели управления процессом проектирования
- Выводы и постановка задач исследования
- Задача оптимального совмещения проектно-строительных работ
- Вспомогательные процессы
Введение к работе
Актуальность темы. Одной из особенностей продукции строительного производства является ее длительный жизненный цикл: до сих пор во многих городах России находятся в эксплуатации здания и сооружения, спроектированные и построенные 50 - 100 лет назад. Следовательно, от того, удачные или нет, проектные решения были приняты на начальной стадии создания этого объекта будет зависеть эффективность его эксплуатации и во многом будет определяться длительность его жизненного цикла. Существуют многочисленные примеры удачных решений, обеспечивающих жизненный цикл здания или сооружения в течение нескольких столетий, а также и примеры обратного, когда неудачные проектные или технологические решения привели к необходимости досрочного завершения эксплуатации объекта, то есть существенного сокращения его жизненного цикла.
В связи с этим огромная ответственность ложится на проектировщиков, решения которых на начальном этапе инвестиционно-строительного цикла во многом определяют успешность реализации всего проекта. К сожалению, в настоящее время столь важные решения принимаются во многом интуитивно, без должной вариантной проработки, поэтому возникает насущная необходимость осуществления разработки комплекса моделей, обеспечивающих повышение эффективности функционирования, как самой проектной фирмы, так и качества выдаваемой ею продукции. При этом все виды работ должны быть выполнены в заданные сроки и с приемлемым уровнем качества. Таким образом, возникает задача управления продолжительностью инвестиционно-строительного цикла.
Известно, что имеется несколько возможностей сокращения продолжительности выполняемых работ: экстенсивный путь, подразумевающий насыщение ресурсами фронтов работ, то есть увеличение число специалистов, работающих над данным проектом; интенсивный путь, то есть повышение производительности труда персонала и организационный, когда за счет продуманной организации сокращаются непроизводительные потери времени, а за счет организации параллельного выполнения работ осуществляется сокращение общей продолжительности выполняемых работ.
Следовательно, актуальность темы диссертационной работы определяется необходимостью разработки эффективных моделей и алгоритмов оптимизации проектных и строительных работ, позволяющих осуществлять рациональное их совмещение с целью сокращения продолжительности инвестиционно-строительного цикла.
Основные исследования, получившие отражение в диссертации, выполнялись по планам научно-исследовательских работ:
федеральная комплексная программа «Исследование и разработки по приоритетным направлениям науки и техники гражданского назначения»;
госбюджетная научно - исследовательская работа «Разработка и совершенствование моделей и механизмов внутрифирменного управления».
Цель и постановка задач исследования. Целью диссертации является повышение разработка комплекса моделей, повышающих эффективность управления процессами проектирования и строительства на основе оптимизации календарных планов в условиях ограниченности ресурсов.
Достижение цели работы потребовало решения следующих основных задач:
-
Анализ существующих моделей управления проектно-строительными работами.
-
Дать постановки задач управления процесса проектирования и строительства для различных критериев оптимизации (минимум продолжительности, минимум отклонений от заданных сроков, минимум штрафов).
-
Разработать точные методы решения этих задач.
-
Разработать эвристические методы решения этих задач.
-
Произвести экспериментальную проверку эвристических методов при различных правилах приоритетности.
-
Разработать методику практического использования предложенных алгоритмов и апробировать их на практике.
Методы исследования. В работе использованы методы системного анализа, математического программирования, теории графов.
Научная новизна результатов работы состоит в следующем:
-
Дано обобщение известных моделей управления процессами проектирования и строительства, отличительной особенностью которых является рассмотрение и учет совмещений процессов проектирования и строительства.
-
Разработан эвристический метод распределения ресурсов строительной организации на основе различных правил приоритетности.
-
Проведен вычислительный эксперимент по сравнению различных правил приоритетности, на основе которого выделены наиболее эффективные правила.
-
Дано обобщение задачи Джонсона о станках на случай рекомендательных зависимостей между проектами и строительными работами. Предложен алгоритм ее решения, обобщающий известное правило Джонсона.
-
Поставлена задача минимизации потерь при совмещении проектных и строительных работ. Предложен для ее решения метод ветвей и границ, при получении нижних оценок на основе метода сетевого программирования.
-
Рассмотрена задача минимизации упущенной выгоды при задержке сроков строительства для случая, когда проектные работы, а также и строительные, выполняются одной строительной бригадой и одной проектной бригадой.
-
Для случая ограниченности ресурсов для проектной и строительной организации поставлена задача минимизации времени завершения всех проектов. Для ее решения предложен итеративный эвристический алгоритм.
Достоверность научных результатов. Научные положения, теоретические выводы и практические рекомендации, включенные в диссертацию,
обоснованы математическими доказательствами, расчетами на примерах, производственными экспериментами и проверкой разработанной системы при внедрении в практику управления строительных организаций.
Практическая значимость и результаты внедрения. На основании выполненных автором исследований разработаны модели и алгоритмы, позволяющие получать оптимальные планы работы, как всей проектной организации, так и ее структурных подразделений.
Использование разработанных в диссертации моделей и механизмов позволяет многократно применять разработки, тиражировать их и осуществлять их массовое внедрение с существенным сокращением трудозатрат и средств.
Разработанные модели используются в практике работы ООО УК «Жилпроект» (г. Воронеж), ОАО «Воронежпроект».
Модели, алгоритмы и механизмы включены в состав учебного курса «Исследование операций при моделировании социально-экономических систем», читаемого в Воронежском государственном архитектурно-строительном университете.
На защиту выносятся:
-
Обобщение известных моделей управления процессами проектирования и строительства, отличительной особенностью которых является рассмотрение и учет совмещений процессов проектирования и строительства.
-
Эвристический метод распределения ресурсов строительной организации на основе различных правил приоритетности.
-
Результаты вычислительного эксперимента по сравнению различных правил приоритетности, на основе которого выделены наиболее эффективные правила.
-
Обобщение задачи Джонсона о станках на случай рекомендательных зависимостей между проектами и строительными работами и предложен алгоритм ее решения, обобщающий известное правило Джонсона.
-
Модель минимизации потерь при совмещении проектных и строительных работ и адаптация метода ветвей и границ для ее решения, с получением нижних оценок на основе метода сетевого программирования.
-
Модель минимизации упущенной выгоды при задержке сроков строительства для случая, когда проектные работы, а также и строительные, выполняются одной строительной бригадой и одной проектной бригадой.
-
Модель минимизации времени завершения всех проектов при ограниченности ресурсов для проектной и строительной организации и итеративный эвристический алгоритм для ее решения.
Апробация работы. Основные результаты исследований докладывались и обсуждались на 64-67-й научно-технических конференциях по проблемам архитектуры и строительных наук (г. Воронеж, 2009-2012 гг.); X международная научно-техническая конференция «Современные сложные системы управления» (г. Старый Оскол, 2012 г.); Международная молодежная конференция «Математические проблемы современной теории
управления системами и процессами» г. Воронеж, 2012 гг.); конференция "Управление в технических, эргатических, организационных и сетевых системах" (УТЭОСС-2012), (г. Санкт-Петербург, 2012 г.).
Публикации. По теме диссертации опубликовано 11 научных работ, в том числе 5 работ опубликованы в изданиях, рекомендованных ВАК РФ.
Личный вклад автора в работах, опубликованных в соавторстве, состоит в следующем: в работах [1], [11] автору принадлежит обобщение известных моделей управления процессами проектирования и строительства; в работах [6], [11] - эвристический метод распределения ресурсов строительной организации; в работах [5], [9] - обобщение задачи Джонсона о станках на случай рекомендательных зависимостей между проектами и строительными работами; в работах [8], [10], [11] - модель минимизации потерь при совмещении проектных и строительных работ; в работах [10], [11] - модель минимизации упущенной выгоды при задержке сроков строительства; в работах [2], [11] - модель минимизации времени завершения всех проектов при ограниченности ресурсов для проектной и строительной организации.
Объем и структура работы. Диссертация состоит из введения, трех глав, заключения, списка литературы из 159 наименований и приложений. Общий объем работы составляет: 149 страниц основного текста, 26 страниц приложений, 43 рисунка, 19 таблиц.
Модели управления процессом проектирования
Состояние большинства российских предприятий в настоящее время таково, что процедуру признания несостоятельности предприятия можно возбудить в любое время против большинства из них. Причины кризисного положения российских предприятий, проанализированные в [211, указывают на то, что основные проблемы находятся в сфере стандартных мероприятий антикризисного управления, позволяющих изменить отрицательную тенденцию, сложившеюся в организации. В связи с этим, в большинстве случаев, современное кризисное положение большинства организаций объясняется отсутствием у руководства этих предприятий понимания имеющихся внутренних причин кризиса и необходимого объема знаний, необходимых хотя бы для частичного их разрешения.
Успешность мероприятий антикризисного управления, будет определяться использованием современных эффективных управленческих технологий, основу которых составляет теория управления проектами, предполагающая формирование организационной структуры компании, отвечающей целям и задачам проектного управления. Это связано с тем, что деятельность любого предприятия можно рассматривать либо как выполнение постоянных и систематически повторяющихся действий, получивших название операций, либо как выполнение однократных и уникальных действий, называемых проектами. Вполне понятно, что организационная структура фирмы должна соответствовать выполняемым действиям: для операций одна, для проектов -другая. Сведение всего многообразия форм функционирования предприятия к двум видам весьма условно и один набор действий, выполняемых на предприятии в различных условиях, может быть отнесен как к операциям, так и к проектам. В этом случае характерен пример с серийным производством. Согласно общепринятым представлениям такая деятельность должна быть отнесена к операциям, так как имеет место именно постоянные и систематически повторяющиеся действия. Но в тоже время такая деятельность предприятия может рассматриваться и как проект, направленный на выпуск определенного вида продукции. Объясняется это тем, что даже такому виду деятельности присущи признаки проекта: временные границы (серийное производство любого вида продукции имеет четкие временные рамки, в которых оно производится, хотя, надо отметить, что эти временные границы могут определяться годами или даже десятилетиями) и уникальность (серийное производство любого изделия имеет свои конкретные особенности, которые могут трактоваться как уникальность).
Таким образом, при определении характера, выполняемых предприятием действий, очевидно, приходится исходить из величины глубины планирования, на которую производится анализ, а также из масштабов этого анализа. Следовательно, это обстоятельство позволяет сделать вывод, что практически любой вид деятельности предприятия можно представить как проект. Это означает, что функционирование предприятия можно представить как последовательность реализуемых проектов.
Предприятия, ориентированные на проектное управление должны иметь организационную структуру, обеспечивающую одновременное ведение большого количества проектов за счет вертикальных и, самое главное, горизонтальных связей. Исследователями отмечается взаимосвязь между организационной структурой и результатами реализации проекта.
Организационная структура предприятия часто ограничивает возможности использования технологий проектного управления, для которых общепринятый функциональный подход не обеспечивает горизонтальных связей на предприятии, так необходимых для реализации проекта. Промежуточной организационной структурой, позволяющей внедрить технологию проектного управления на базе существующих функциональных структур, являются разнообразные матричные структуры. Основные пояснения, относящиеся к влиянию типа организационной структуры на характеристики выполняемых проектов, представлены в табл. 1.1.1 [88].
На рис. 1.1.1 114 приведена классическая функциональная организационная структура, представляющая собой иерархическую модель, в которой каждый сотрудник имеет одного прямого начальника, причем все сотрудники сгруппированы по функциональным направлениям, например, производство, маркетинг, инжиниринг, финансы.
Реализация проектов в рамках функциональной организации характерна отсутствием горизонтальных связей, что значительно затрудняет выполнение работ и увеличивает сроки их выполнения. Так, например, если в процессе работы сотрудников одного из функциональных направлений возникают вопросы, связанные с деятельностью другого функционального подразделения этой же организации, то они передаются по структуре наверх начальнику соответствующего функционального подразделения, который запрашивает начальника другого функционального подразделения, а ответ спускается вниз к специалисту, направления инициирующего обращение. На рис. 1.1.1 участники реализации проекта выделены двойной линией.
Выводы и постановка задач исследования
Процесс решения задачи очень удобно и наглядно описывается с помощью двудольного графа, у которого первый слой вершин обозначает заказы, принятые к выполнению проектной фирмой, а второй - из m величин, соответствующих m интервалам времени, в которых эти заказы могут выполняться. Для построения этих интервалы необходимо упорядочить все моменты d, и Дно возрастанию.
Для дальнейшего решения необходимо достроить исходный двудольный граф до сети, добавив вход сети (вершина 0) и выход сети (вершину z). Будем считать, что объемы работ по / -ому заказу равны пропускным способностям дуг (0, / ), то есть С „, =М (, пропускные способности дуг (s,z) будут соответствовать объемам работ, выполняемых N специалистами в течение время As, то есть С\. - Л дч и, наконец, в качестве пропускных способностей дуг (i.s), і = 1./7. л = І./» принимаются максимальные объемы работ, которые могут выполнить а, специалистов за интервал времени S , то есть Q = а,Дч.
Пусть .у,ч - объем работ но / -ому заказу, выполняемых в 5-ом интервале, тогда объем работ но / -ому заказу определяется выражением вида \-„, = л ,ч , где R, - множество интервалов, в которых могут выполняться ра боты по / -ому заказу; а объем работ, выполняемый в Л -ом интервале, будет задавиться в следующем виде л\ = л ,ч .
При этом должны выполняться ограничения, задаваемые условием задачи 0 х„ с„. /=Гй, 0 .гл сл. \e\\.i = Lm, 0 л;_ . s = йіі (1.3.5) Таким образом в построенной сети существует поток по сети, величина которого = 5X = Z-Y - Содержательно, если будет выполняться соотношение X = W, =W то / это соответствует условию, когда все заказы выполнены в срок; в тоже время разность W, - л"о, = S„ показывает объем невыполненных работ по і-ому заказу. В 114] предлагается алгоритм решения задачи минимизации максимального отклонения от договорных сроков.
Пусть // = ma\(Tt - Ц). Тогда следует, что Т D, +/. і = \.п Считая величину U постоянной, увеличим все D, на U. В этом случае может измениться последовательность упорядоченных чисел d, и D,+ U, а значит, изменятся и длительности интервалов с пропускными способностями дуг (i,s) и (s.z).
Найдем величину потока в построенной сети. Лемма 1.3.1. 11 И] Минимальная величина U, при которой поток максимальной величиной равен W, определяет оптимальное решение задачи по критерию F\. Доказательство очевидно. Описание алгоритма 1 шаг. Пусть U[) и найден поток Х$ максимальной величины. В том случае, если величина потока равна И7, то решение задачи найдено. Иначе переходим ко второму шагу. 2 шаг. Находим минимальный разрез и определяем увеличение пропускной способности разреза при увеличении всех значений D, на величину MJ. При этом, если в разрез заходит дуга (S, Т) или (/ , S) то увеличение их пропускных способностей зависит от величины iS такой, что его длина равна разности соседних значений d, либо соседних D, то очевидно, при увеличении Дэта разность не изменится и увеличение пропускных способностей равно 0. Если же отрезок S такой, что его длина равна разности некоторого D и некоторого d, то очевидно, увеличение пропускной способности dy(i,s)равно а,Аи, и дуги (S. Z) равно NAu. Пропускные способности дуг (0, / ), заходящих в разрез, не изменяются. Суммарные увеличения является медленной функцией Aw (при условии, что очередность отрезков не изменилась) определяемой соотношением Д(К) = A0.AU .
За конечное число шагов будет найдено значение AU, такое, что поток максимальной величиной равен IV, что соответствует условию выполнения всех запланированных работ. Начальное приближение для величины AU0 на первом шаге можно брать не нуль, а находить из условия (А(У(1 + тах D, -mm d,)N = IV. ЭТО соотношение получено из предположения о том, что все работы должны быть выполнены в интервале времени Т = minc/,;A» + max Д I. Так как общий объем работ равен IV, а количество ресурсов - /V, то длина интервала 7 должна быть не меньше чем —. Следовательно, получаем минимальное увеличение AU0 = /V max D, - mint/, Если эта величина отрицательна, то получаем Д/0 = 0. Рассмотрим задачу минимизации суммы штрафов (потерь) при невыполнении заказов в требуемые сроки [114], причем эти штрафы прямо пропорциональны объему невыполненных работ F2 = 2: С (w: - хо:) = : с w;. - , С А 0!-, Эта задача будет эквивалентна минимизации взвешенного объема выполненных работ, то есть /% = СДо, .
Приведем описание алгоритма согласно [114]. 1 шаг. Упорядочим заказы по убыванию С. Примем, что нумерация заказов соответствует этому упорядочению. Строим соответствующую сеть и определяем поток максимальной величины по дуге (0,1) k-шаг. Определяем поток максимальной величины по дуге (0, к), не изменяющий величины потоков по дугам (0,/), i k.
Поток, полученный после /7-го шага, дает оптимальное решение задачи. Обоснованием алгоритма служит тог факт, что получаем максимальный поток и увеличить его можно только за счет уменьшения на ту же величину потоков по дугами (0, / ), \ к. Но это уменьшает исходный критерий.
Понятно, что характер получаемого решения будет зависеть от типа рассматриваемой функции штрафов. Рассмотрим наиболее общий случай, когда функции штрафа (потерь) (р, (6V) нелинейны.
Пусть функции штрафа (потерь) р,( 5,) выпуклые возрастающие кусочно-линейные функции от 5,-. Это допущение означает то, что множество возможных потоков в этом случае будет также являться выпуклым и задача минимизации F2 будет является задачей выпуклого программирования.
Задача оптимального совмещения проектно-строительных работ
В работе рассматривается практически важный случай, когда Ь, а„ /-1./7, то есть продолжительность строительства превышает продолжительность проектирования. Заметим, что во многих случаях имеет место более сильное условие. А именно, Ь, а,, і./ \.п, то есть продолжительность строительства любого проекта превышает продолжительность проектирования любого проекта. В ряде случаев для реализации проектов в срок допускается совмещение проектного и строительного этапов. При этом, естественно, возрастает либо стоимость, либо продолжительность строительства, либо то и другое.
Задача Джонсона является простейшей моделью проектно-строительного процесса. В поставленной выше проблеме задача Джонсона соответствует ситуация, когда каждый этап выполняется одной бригадой (проектный этап - бригадой проектировщиков, а строительный - бригадой строителей), причем имеется всего одна бригада проектировщиков и одна бригада строителей. Правило Джонсона получения оптимального решения по критерию 1 (минимизация времени реализации всех проектов) в интерпретации выполнения проектов выглядит следующим образом: в первую очередь выполняются проекты, для которых bj а\, в очередности возрастания а;; во вторую очередь выполняются проекты, для которых bj а;, в очередности убывания bj. Поскольку в нашем случае bj а; для всех проектов, то правило Джонсона упрощается, то есть проекты выполняются в очередности возрастания (не убывания)
Рассмотрим задачу Джонсона с другими критериями оптимальности. Минимизация максимального отклонения от требуемых сроков (критерий 2). Рассмотрим решение задачи при сильном условии bj а,, для всех i,j. Пусть уже выбран проект, который будет выполняться первым. Тогда при сильном условии строительные этапы всех остальных проектов будут выполняться один за другим без перерывов. Для этого случая решение задачи состоит в том, что остальные проекты должны выполняться в очередности возрастания (не убывания) Dj.
Докажем это. Пусть первым выбран проект к и определена некоторая последовательность остальных проекіов. Рассмотрим два соседних проекта i,j в этой последовательности и пусть D, Dj. Обозначим через 1 момент окончания предыдущих проектов.
Таким образом, при перестановке величина Л не увеличилась. Решение задачи состоит в переборе всех проектов - претендентов на выполнение в первую очередь. Остальные проекты упорядочиваются по возрастанию Dj. Из полученных п решений выбирается лучшее по критерию А.
Получили оптимальное Я—(1,2,3,4) с величиной критерия А=8. Минимизация штрафов за невыполненные объемы работ. Заметим, что в рассматриваемом случае величина штрафа для і-о го проекта равна St = а, ma\min(/), Д - Д)аг,;0". Действительно, если к моменту D, строительные работы еще не начаты, то штраф равен а,Ь, (за невыполнение проектных работ штраф не берется). Іісли же строительные работы ведутся, но не завершены в момент D,. то штраф равен а,(Т,-0,). Примем, что имесг место сильное условие, го ссгь Ь, а5 для всех i,j. В этом случае при выборе проекта, который будет выполняться первым (пусть это проект q) задача для остальных проектов сводиться к минимизации
Рассматриваем проекты в очередности их номеров. Пусть рассматривается проект ii-k. Обозначим t, возможный момент начала проекта і, равный сумме длительностей проектных этапов всех ранее рассмотренных проектов. Если t, D„ то очевидно, штраф равен а,Ь,. Если t, D,, то начиная с момента D„ сдвигаем влево все ранее рассмотренные проекты (естественно, до моментов t,). Размешаем проект і в интервале (t,,D,) на свободных участках. Далее сдвигаем все проекты максимально вправо (до момента D,). Далее переходим к следующему шагу.
Обоснованием алгоритма служит тот факт, что уменьшение штрафа для проекта / возможно только при освобождении некоторого интервала г., ранее занятого другими проектами. Однако это не уменьшит величины штрафов, поскольку коэффициенты штрафов всех ранее рассмотренных проектов больше (не меньше), чем у проекта / . Сравнивая решения для различных вариантов начала, выбираем оптимальное.
Вспомогательные процессы
Очевидно, что это нижняя оценка для решения исходной задачи и ее можно применить в методе ветвей и границ. Однако, как показывают решения многих примеров это достаточно грубая оценка, так что применение метода ветвей и границ с такой оценкой является неэффективным. Действительно, ВО-ПерВЫХ, X t=6, ЧТО боЛЫНе ЧЄМ Т4 5. Во-ВТОрЫХ, Х= -3, что уменьшает оценку на 12 единиц. Опишем алгоритм решения задачи.
Идею алгоритма предварительно рассмотрим на примере с данными примера 2.3.1. Рассмотрим график, приведенный на рис 2.3.2 (отсутствует совмещение проектных и строительных). Критический путь (1,2,2,3,4) имеет длину ТШХ=42. Уменьшить продолжительность выполнения всех проектов можно двумя способами, первый состоит в совмещении проектных и строительных работ у второго проекта. Для сокращения продолжительности критического пути на 2 единицы необходим интервал совмещения той же длины, что требует 12 единиц затрат. При этом в сети появится новый критичный путь (1,2,3,3,4) длиной 41. Его сокращение на единицу за счет совмещения проектных и строительных работ третьего проекта на единицу, требует затрат 4 единицы. В целом при этом способе требуется 16 единиц дополнительных затрат. Рассмотрим второй способ. Он заключается в том, что за счет совмещения проектных и строительных работ одного из проектов, который выполняется позже проекта 2 (это проекты 3 и 4) уменьшить величину Д, и тем самым поставить на второе место один из этих проектов вместо второго проекта. Для этого необходимо, чтобы либо А, =7, либо Д., =7. Для обеспе 74 чения Л, =7 необходим интервал совмещения для третьего проекта равный х, =а, -А, =8-7 = 1, что требует дополнительных затрат в 4 единицы. Для обеспечения А, = 7 необходим интервал совмещения для четвертого проекта длины х, = 7, - А, = 9-7 = 2 , что требует дополнительных затрат в 2 единицы.
Выбираем вариант совмещения проектных и строительных работ для четвертого проекта. Теперь мы можем поставить четвертый проект на второе место (Рис. 2.3.4). Длина критичного пути не уменьшилась. Однако, теперь на критичном пути лежит проект 4 с минимальными дополнительными затратами при совмещении на единицу работ, поэтому увеличиваем интервал совмещения работ для четвертого проекта еще на две единицы. Дополнительные затраты составят 4 единицы. Теперь критичным становится путь (1,1,4,2,3) длины 41. Однако мы можем поставить на первое место проект 4, поскольку А, =А, =5. Получаем сетевой график Рис. 2.3.5 с той же длиной критического пути. I 9 16 " 0 I
Наконец, увеличивая интервал совмещения работ четвертого проекта еще на одну единицу, получаем оптимальное решение с длиной критичного пути Т=40, интервалами совмещения работ длины .v, =0..т, =0.v, =0.х, =5 и величиной дополнительных затрат С(х)=5. Описание алгоритма. 1 шаг. І Іолаї асм \, =0./ = 1.и и определяем критический путь в сетевом графике при упорядочении проектов по возрастанию а,. Определяем критический проект (пусть это проект к). 2 шаг. Оцениваем возможные варианты сокращения критического пути: a. Увеличиваем интервал совмещения работ критического проекта на единицу и вычисляем дополнительные затраты дк =сА . b. Увеличиваем интервалы совмещения работ всех проектов, следую щих за критическим на \(, определяемых из условия х1=а1-Ак , (если сі,-Ак г,, то проект j не рассматриваем). Оцениваем дополнительные заїра 76 ты St =cl(al -ДА). Выбираем вариант (а), если 8к пл\\\81, то есть увеличиваем интервал совмещения работ критического проекта на 1. Выбираем вариант (Ь), если ) , mine) ,, то есть увеличиваем интервал совмещения работ проекта с минимальной величиной 81 на (c -AJ. Далее шаг 2 повторяется до получения требуемой длины критического пути. Замечание 1. Іісли в сети несколько критических путей, то шаг 1 выполняется для каждого критического пути, а шаг 2 выполняется сначала для самого верхнего критического пути.
Замечание 2. После окончания алгоритма могут найтись проекты, которые не лежат на критическом нуги, но у которых интервал совмещения работ положителен. В этом случае интервал совмещения уменьшается на максимально возможную величину. Рассмотрим более сложный пример.
Шаг 4. Критический путь остается прежним. Вариант (a): v, =5. , =10. Проект 3: \ =з. t \=9. Имеем S ,. Заметим однако, что если поставить проект 3 первым, то погребуеіся по крайней мере \, =6 для того чтобы Т=80. Однако, \, 5, поэтому выбираем вариант (а) и полагаем \, =5. Шаг 5. Теперь в сетевом графике три критических пути (4,4,1,2,3,5), (4,1,2,3,5,5) и (4,1,1,2.3,5) Рис. 2.3.9. Следовательно, в варианте (а) необходимо учитывать ишервал совмещении работ для трех проемов 4, 1 и 5. Рис. 2.3.8 Проект 3: \\-а, -Д4 =5. 6, -=-15. Проект 5: v, =и. -д = 12. 3 =12 Выбираем вариант (b), проект 2. Подаїасм v2 = 3 и ставим проект 2 на первое место (Рис. 2.3.10). Шаг 6. В сети два критических пути (2,2,1,3,4,5) и (2,1,3,4,5,5), причем у критического проекта 5 пег проектов, которые следуют за ним. Поэтому остается вариант (а), то есть увеличение интервалов совмещения проектов 2 и 5 на 1. Имеем л, = 4.\\ = 1. S-, = 16. - \ =1. Дополнительные затраты равны 17.
