Управление проектами на основе оптимизации календарных графиков работы неоднородных команд специалистов тема диссертации и автореферата по ВАК РФ 05.13.10, кандидат наук Роговая Людмила Александровна

• Роговая Людмила Александровна
• кандидат наук
• 2019

Оглавление диссертации кандидат наук Роговая Людмила Александровна

Введение

ГЛАВА 1. МЕТОДЫ КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ В

УПРАВЛЕНИИ ПРОЕКТАМИ

§1.1 Задачи календарного планирования работ

§1.2 Задачи ресурсного планирования комплексов работ

§1.3 Методы решения задач дискретной оптимизации

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

ГЛАВА 2. РАЗРАБОТКА АЛГОРИТМОВ ОПТИМИЗАЦИИ КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ РАБОТ

НЕОДНОРОДНЫХ КОМАНД СПЕЦИАЛИСТОВ

§2.1 Постановка задачи и алгоритмы календарного планирования

работ неоднородных команд специалистов

§2.2 Модификация симплекс-метода для решения задачи календарного планирования работ неоднородных

команд специалистов

Выводы по главе

ГЛАВА 3. РАЗРАБОТКА АЛГОРИТМОВ КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ РАБОТ НЕОДНОРОДНЫХ КОМАНД

СПЕЦИАЛИСТОВ С УЧЕТОМ АУТСОРСИНГА

§3.1 Задача календарного планирования работ неоднородных команд специалистов с учетом аутсорсинга

(непрерывный случай)

§3.2 Задача календарного планирования работ неоднородных команд специалистов с учетом аутсорсинга

(дискретный случай)

Выводы по главе

ГЛАВА 4. ОПТИМИЗАЦИЯ КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ ПРОЦЕССА ОЦЕНКИ СООТВЕТСТВИЯ

КАЧЕСТВА СИНТЕТИЧЕСКИХ КАУЧУКОВ

В АО «ВОРОНЕЖСИНТЕЗКАЧУК»

§4.1 Центр «Эластомеры» АО «Воронежсинтезкаучук» и

его функции

§4.2 Описание технологического процесса оценки соответствия

качества синтетических каучуков

§4.3 Разработка оптимального календарного плана процесса

оценки соответствия качества синтетических каучуков

Выводы по главе

Заключение

Список литературы

Приложение А. Акты внедрения

ВВЕДЕНИЕ

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

Степень научной разработанности проблемы. Вопросы формализации процессов календарного планирования и управления проектами, широко представлены в работах С. А. Баркалова, В. Н. Буркова, И. В. Бурковой, П. Н. Курочки, Д. А. Новикова, Л. В. Россихиной, M. Garey, E. Demeulemeester, W. и др.

Однако полученные теоретические результаты, к сожалению, не учитывают следующие объективные обстоятельства: возможность прерывания отдельных работ в процессе выполнения проекта, возможность изменения последовательности реализации отдельных работ в рамках календарного группового выполнения ра-

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

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

Тематика диссертационной работы соответствует одному из основных научных направлений «Развитие моделей и методов управления проектами» лаборатории № 57 федерального государственного бюджетного учреждения науки «Институт проблем управления им. В. А. Трапезникова Российской академии наук» (гранты РФФИ № 17-20-05216, № 18-07-01258).

Объект исследования: процессы ресурсного и календарного планирования комплексов работ, выполняемых неоднородными командами специалистов.

Предмет исследования: оптимизационные модели календарного планирования работ неоднородных команд специалистов.

Целью диссертационного исследования является повышение эффективности процессов формирования календарных планов работ в условиях неоднородных команд специалистов.

Достижение цели работы потребовало решения следующих основных задач:

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

- осуществить модификацию симплекс-метода для решения задачи календарного планирования работ неоднородных команд специалистов;

- формализовать задачу календарного планирования работ неоднородных команд специалистов с учетом аутсорсинга;

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

- разработать алгоритм решения задачи календарного планирования работ не-

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

Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:

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

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

3. Формализация задачи календарного планирования работ неоднородных команд специалистов, отличающаяся учетом зависимости между работами, которая описывается сетевым графиком «вершина - событие».

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

5. Формализация задачи календарного планирования работ неоднородных команд специалистов, отличающаяся учетом возможности передачи работ (части или целиком) на аутсорсинг по критерию минимизации стоимости работ, передаваемых на аутсорсинг.

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

Использование полученных результатов позволяет разрабатывать опти-

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

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

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

Результаты исследований апробированы в Центре «Эластомеры» АО «Во-ронежсинтезкаучук». Разработаны методические рекомендации по планированию работ неоднородных команд специалистов по оценке соответствия качества синтетических каучуков необходимым требованиям. Внедрение методики в реальных производственных условиях показало, что сокращение времени проведения всех работ по оценке соответствия качества синтетических каучуков составило 10 % от первоначального плана.

Предложенные средства оптимизации календарного планирования работ неоднородных команд специалистов апробированы в лаборатории неразрушающе-го контроля Юго-Восточного филиала АО «Калужремпутьмаш».

Кроме того, полученные результаты использованы в образовательном процессе Воронежского государственного университета при разработке учебно -методических материалов и преподавании дисциплины «Теория игр и исследование операций» (направление подготовки 01.03.02 Прикладная математика и информатика).

Методология и методы исследования. Методологическую основу исследования составляет аппарат теории управления организационными системами. В диссертации реализованы методы теории исследования операций, теории графов, теории управления проектами, математического программирования, дискретной оп-

тимизации.

Тематика работы соответствует пунктам паспорта научной специальности 05.13.10: п. 2 «Разработка методов формализации и постановка задач управления в социальных и экономических системах», п. 4 «Разработка методов и алгоритмов решения задач управления и принятия решений в социальных и экономических системах».

Положения, выносимые на защиту:

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

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

3. Постановка задачи календарного планирования работ неоднородных команд специалистов с учетом зависимости между работами, которая описывается сетевым графиком «вершина - событие».

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

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

Основные положения диссертационной работы докладывались и обсуждались на Международной научно-практической конференции «Проблемы, перспективы и направления инновационного развития науки» (г. Омск, 2017); XI Международной научной конференции «Научный диалог: молодой ученый» (г.

Санкт-Петербург, 2017); Международной научно-практической конференции «Научно-практические аспекты развития современной техники и технологий в условиях курса на инновации» (г. Магнитогорск, 2017); VIII Международной конференции «Теория расписаний и методы декомпозиции. Танаевские чтения» (г. Минск, 2018); Международной мультидисциплинарной конференции по промышленному инжинирингу и современным технологиям FarEastСon - 2018 (г. Владивосток, 2018); XV Всероссийской школе-конференции молодых ученых «Управление большими системами» (г. Воронеж, 2018); XIII Международной научно-практической конференции «Современные сложные системы управления» (г. Старый Оскол, 2018); XI Международной научной конференции «Управление развитием крупномасштабных систем» (г. Москва, 2018), а также на научных семинарах лаборатории № 57 ФГБУН "Институт проблем управления им. В. А. Трапезникова РАН" (2017 - 2019 гг.).

Публикации. По теме диссертации опубликовано 13 научных работ объемом 6 печ. л., в том числе 5 работ объемом 3,8 печ. л. опубликованы в рецензируемых научных изданиях из перечня ВАК. В работах, опубликованных в соавторстве и приведенных в конце автореферата, лично соискателю принадлежат: в работе [3] - модификация симплекс-метода для решения задачи календарного планирования работ команд специалистов; [4, 5, 7, 10] - постановка задачи календарного планирования работ команд специалистов с минимальной продолжительностью выполнения всех работ при ограничении на число специалистов каждого типа; алгоритм календарного планирования работ команд специалистов с минимальным числом прерываний работ, основанный на методе локальной оптимизации; постановка задачи календарного планирования работ команд специалистов с учетом зависимости между работами, которая описывается сетевым графиком «вершина - событие»; [12] - алгоритм календарного планирования работ команд специалистов, обеспечивающий минимальную продолжительность выполнения всех работ при условии, что максимальные наборы содержат все команды, за исключением одной; [6, 13] - постановка задачи календарного планирования работ команд специалистов с возможностью передачи работ (части или целиком)

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

Структура работы обусловлена целями, задачами, логикой и методологией исследования и состоит из введения, четырех глав, заключения, списка литературы из 145 наименований, приложения. Общий объем работы составляет 130 страниц машинописного текста, включая 8 рисунков, 59 таблиц.

ГЛАВА 1. МЕТОДЫ КАЛЕНДАРНОГО ПЛАНИРОВНИЯ В УПРАВЛЕНИИ ПРОЕКТАМИ

§1.1 Задачи календарного планирования работ

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

В данной работе под проектом будем понимать совокупность взаимосвязанных действий, направленных на достижение конкретных целей [1]. Работа команд специалистов является примером проекта, между работами которого существует отношение предшествования.

Общую постановку задачи составления расписания выполнения работ, при котором не нарушаются отношения предшествования, ресурсные ограничения, и при этом срок окончания проекта минимальный, можно представить следующим образом [2].

Пусть задано множество работ N = {1,...,n} и U возобновляемых ресурсов и =1,...,U. В каждый момент времени t доступно Qединиц ресурса и. Заданы продолжительности работ тг > 0 для каждой работы i =1,...,n. Во время выполнения работы i требуется qiu < Q единиц ресурса и =1,...,U. После завершения работы, освобожденные ресурсы в полном объеме могут быть назначены на выполнение других работ. На множестве всех работ задан частичный порядок их выполнения: если работа i предшествует работе j, то выполнение работы j не может начаться раньше окончания работы i. Выполнение работы начинается в момент времени t = 0. Необходимо определить моменты времени начала выполнения работ Sl, i = 1,...,n, так, чтобы минимизировать время выполнения всего проекта, т.е. минимизировать значение

Cmax = max {Q}

z=1,.../j

где Ci = St +тг.

При этом должны быть соблюдены следующие ограничения [3]:

n

1) в каждый момент времени t е [о,Cmx) должно выполняться ^qiu^(t)< Q,

i=1

u = 1,U, где (pXt) = 1, если работа i выполняется в момент времени t и ^(t) = о, в противном случае. То есть работы в процессе выполнения должны быть полностью обеспечены ресурсами;

2) не нарушаются отношения предшествования между работами, т.е. S < S,, если i ^ j для i, j е N

i i J ' J <s

Задачам календарного планирования проектов с учетом ограничений на ресурсы посвящено много работ [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14].

В работе [15] рассматривается задача календарного планирования с ограничениями на воспроизводимые ресурсы (станки, исполнители и т.д.) и порядок выполнения работ. Приведена постановка задачи: дано N работ, при выполнении которых используются М видов возобновимых ресурсов. Имеется Vm единиц ресурса вида m (m=1,2,...,M). Работа n характеризуется длительностью тпеZ+ и потребностью vm в m-м виде ресурсов (n = 1,2,...,N; m = 1,2,...,M). Для каждого t > 0 и каждого m суммарная по всем работам, выполняемым в момент t, потребность в ресурсе m не должна превосходить Vm. Прерывания работ не допускаются. На множестве всех работ не нарушаются отношения предшествования. Необходимо выполнить все работы за минимальное время. Представленная задача является обобщением задачи построения конвейерного расписания [16], задачи с параллельными приборами [17], задачи календарного планирования с единичными длительностями. Автором [15] на основе геометрической интерпретации задачи разработан алгоритм построения оптимального расписания выполнения заданных работ.

Задача календарного планирования проектов с учетом ограничений на складируемые ресурсы рассмотрена в работе [18]. Исследован частный случай задачи при независимых работах. Предложен точный алгоритм решения, основанный на

методе динамического программирования. Обзоры по задачам календарного планирования со складируемыми ресурсами и критерием чистой приведенной прибыли представлены в работах [19, 20].

Задачи календарного планирования в управлении независимыми проектами рассмотрены в работах [21, 22]. Предложен метод разработки календарного плана выполнения проектов, основанный на снижении эффекта от реализации проекта в более позднем периоде и учитывающий ограничения на объемы финансирования.

В работе [23] рассмотрена задача формирования календарного плана реализации программы, состоящей из п независимых проектов, при заданном графике финансирования. Предложенное решение задачи включает два этапа. На первом этапе проверки реализуемости программы определены поздние времена начала работ при заданном сроке Т реализации программы, получено условие финансовой реализуемости программы. На втором этапе предложен алгоритм календарного планирования, на первом шаге которого начинаются все проекты в поздние моменты начала, рассматриваются периоды в порядке номеров. На следующем шаге, применяя правило приоритета, проекты передвигают в начало рассматриваемого периода, пока хватает средств. Далее переходят к следующему периоду. При этом, проект включен в программу в данном периоде, если требуемые для его реализации средства поступили в полном объеме. Для случая начала проекта еще до поступления всех средств предложен эвристический алгоритм.

Рассмотренная задача в [21, 22] получила развитие при формировании календарных планов проектов, при совместном выполнении которых появляется дополнительный (синергетический) эффект [24, 25, 26]. Предложен точный алгоритм решения для двух периодов для графа взаимозависимостей проектов, преобразованного к виду паросочетания путем удаления вершин и рассмотрения всех вариантов выполнения проектов, соответствующих удаленным вершинам, в первом периоде. Выбирается лучший (с большим суммарным эффектом) вариант календарного плана.

Для Т периодов задача календарного планирования проектов, совместная реализация которых дает дополнительный эффект, является №-сложной. Пред-

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

§1.2 Задачи ресурсного планирования комплексов работ

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

( ч Ж

туи )

где и - количество ресурсов, выполняющих работу;

Введение диссертации (часть автореферата) на тему «Управление проектами на основе оптимизации календарных графиков работы неоднородных команд специалистов»

т{и) - продолжительность работы.

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

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

Пусть имеется п операций Лг-, х$) - состояние /-ой операции в момент I, то есть объем этой операции, выполненный к моменту / при х(0) = 0, х(Т) = Ж/, где Ж - объем /-ой операции, Т - момент окончания комплекса операций. Скорость выполнения операций (интенсивность) имеет вид:

^ = Л и (*)' * ^

где и! (г) - количество ресурсов у-го вида, выполняющий /-ую операцию в момент

г.

Набор векторов и (0 = 1 и1^),и2(¡),...и^(г)] принадлежит множеству допусти-

I V I I I у

мых распределений ресурсов ^ k - число различных видов ресурсов. Требуется определить допустимое распределение и(/) = [^ (/),...и^ (/)], минимизирующее время выполнения комплекса операций Т.

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

Задача оптимального распределения ресурсов получила развитие в работе

[28], в которой рассмотрены методы оптимального распределения ресурсов в мультипроекте, основанные на идее представления проектов в виде отдельных операций.

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

Задача распределения ресурсов при реализации мультипроектов в зависимости от скорости реализации работ и количества самих ресурсов рассмотрена в

[29]. В статье предложена классификация задач по двум признакам:

- виду ресурсов, выполняющих работы каждого проекта;

- виду зависимостей скорости работ от количества ресурсов.

Рассмотрен класс задач, в которых первые, вторые и третьи работы проектов выполняются различными видами ресурсов, а зависимости скорости работ от количества ресурсов являются непрерывными:

иу, ии * аи >

аг], и.. > аг],

где и •• - количество ресурсов на выполнение некоторой работы (¡у), и

а- - количество ресурсов у-го вида.

Задача заключалась в распределении ресурсов по мультипроекту, которое минимизирует его продолжительность. Найдено оптимальное решение, в котором все работы выполняются максимальным количеством ресурсов за время:

"и

т ■■ = —— ,

" а,и '

где " - объем работ (¡у).

и

В статьях [30, 31] рассмотрены частные случаи задачи, когда мультипроект состоит из проектов, представленных цепочкой трех работ. Предложены эффективные алгоритмы решения для различных случаев:

1) ограничены ресурсы первого вида

п

£а,1 > М , (1.1)

ресурсов второго и третьего видов достаточно, и соответствующие работы выполняются за минимальное время Т2, Т/3; 2) ограничены ресурсы второго вида

п

I а,2 > М2 , (1.2)

,=1

работы первого и третьего типа выполняются за минимальное время Тц, Т3; 3) ограничены ресурсы третьего вида

Iагз > Nз , (1.3)

,=1

работы первого и второго типа выполняются за минимальное время Тц, Т2;

4) ограничены ресурсы первого и второго вида (1.1) и (1.2), работы третьего типа выполняются за минимальное время Т/3;

5) ограничены ресурсы первого и третьего вида (1.1) и (1.3), работы второго типа выполняются за минимальное время Т/2;

6) ограничены ресурсы второго и третьего вида (1.2) и (1.3), работы первого типа выполняются за минимальное время Тц;

7) ограничены ресурсы всех видов (1.1), (1.2), (1.3).

Для решения задач определена двудольная сеть из 2(п+1) вершин. Вершины первого слоя сети - проекты, вершины второго слоя - интервалы времени. Доказано, что минимальное время Т, при котором поток максимальной величины насыщает входные дуги, определяет оптимальное распределение ресурсов по мультипроекту, минимизирующее его продолжительность.

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

Авторами [32] предложена следующая постановка задачи: по заданной сетевой модели комплекса из п операций, состоящей из сетевого графика, графа продолжительности работ, матрицы времени перемещения ресурсов с /-ой операции на у-ую |Ц|, зависимости w1 = £ {и,) скорости выполнения /-ой операции от

количества ресурсов соответствующего вида, количества ресурсов у-го вида N ] = 1, к, где к - число классов операций, определить поток ресурсов по графу продолжительности работ, минимизирующий время выполнения комплекса, либо упущенную выгоду.

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

В работе [32] сделаны первые попытки предложить методы оптимального распределения ресурсов на двойной сетевой модели.

Предложенные постановки задач и алгоритмы решения получили развитие в работах [33, 34].

В статье [34] дана постановка задачи календарного планирования для независимых работ с учетом времени перемещения ресурсов, предложен метод решения для вогнутых зависимостей скоростей выполнения работ от количества ресурсов.

Полученные результаты позволяют определить оптимальное распределение ресурсов (при условии, что все работы заканчиваются одновременно, все работы выполняются с одинаковой интенсивностью) при минимальной продолжительности проекта Т, которая определяется из уравнения

Ж

Ъъ

т - а0г

= N,

где Ж - объем /-ой работы,

N - количество ресурсов,

а, - время перемещения ресурсов на работу.

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

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

Постановка задачи. Найти оптимальный календарный план Т* выполнения работ проекта, минимизирующий

СТ)= Ъ сМ

при ограничениях

Tv + tv < Sdup для V(/, j)e E j-sj(t<0, 0<t<Sdup,

(i,j У-U tj S dup

[\npuTj < t < Tj + t j

где Sj(tHq j j j, t j j,

Tj > to, is P, (i, j)etf,

T - плановое начало выполнения работы (i,j), ti} - продолжительность ее выполнения, t - начало выполнения работы,

Р - множество событий (вершин сетевого графика G = {P,U}),

U - множество работ (дуг),

Sd - директивный срок выполнения проекта,

С - плановая стоимость выполнения проекта в целом,

С = f (t) - числовая функция, где t е тг], тг] - область определения этой функции.

В статье [36] рассмотрена задача определения объемов операций из условия выполнения комплекса операций за время Т и минимума некоторой функции потерь монотонно возрастающей с уменьшением объемов операций. То есть необходимо определить объемы операций w такие, чтобы минимальная продолжительность выполнения комплекса операций TMUH(wS) не превышала директивный срок завершения Тдир и дополнительные потери j(w) (дополнительные затраты на привлечение дополнительных ресурсов и др.) были минимальными. Под операцией понимаем процесс, описанный уравнением h(t) = dx(x)/ dt = f [u(t)], h(t) - скорость (интенсивность) операции в момент t (скаляр), u(t) - количество ресурсов на операции в момент t (вектор), x(t) - состояние операции в момент t (скаляр), f (и) - неубывающая, непрерывная справа функция.

Ресурсы участвуют в операции в определенном наборе, то есть п^) = ау([), где а > 0 - заданный вектор. Тогда зависимость /(и) можно представить в виде /(у), где у - количество ресурсов (единиц набора).

Для независимых операций условия выполнимости объема работ w за время Тдир имеют вид:

Г Ж

n

Z j

i=1

T

дир

< N,, j = 1, m.

IS*/ у

(рг - функция обратная fi (выпуклые кверху функции vt для всех i), ai} - j-ая компонента вектора ai для i-ой операции. Задача минимизации <(w) имеет вид:

a(w) = Z С Q - Wt) ^ min ,

i

0 < Wt < Qt, i = In,

n _

Z aijwr < NjTdup , j = 1 m ,

i=1

где Qi - максимальный объем i-ой операции.

Рассмотрена задача минимизации дополнительных потерь при условии, что скорости операций являются линейными функциями количества ресурсов на отрезке [о, b ]:

f (y )=fVi , если0 <Уг < Ъ ,

г г \Ъ.,еслиЬ < у.

г > г г

и количество ресурсов является кусочнопостоянной функцией времени с интервалами постоянства (т8_ 15 т5), 5 = 1, г, где т0 = 0, тг = Тдир. Постановка задачи. Минимизировать

с, е - ж, )=£ас -х с,х„

г , г

при ограничениях

г _

Ж =х* е,, г = 1,и.

5=1

П _

Z < Ns-А s , S = 1, i

i=1

0 < xis < bt • As, i = 1, n, s = 1, r,

где As - длительность интервала (т5Ч, т5),

^ - количество ресурсов в интервале (ts_ г, ts),

хи - часть объема /-ой операции, выполняемой в s-ом интервале.

В работе [37] представлены алгоритмы определения объемов операций, основанные на правиле максимального выравнивания остаточных уровней ресурсов и правиле распределения ресурсов по степени критичности операций.

Задача распределения ресурсов по множеству независимых операций с учетом зависимости скорости операции от количества ресурсов и от состояния операций рассмотрена в [38]. В работе представлены необходимые условия оптимальности для случая линейных по управлению и состоянию зависимостей.

Частные задачи распределения ресурсов в управлении проектами рассмотрены в работах [39, 40, 41, 42, 43, 44].

§1.3 Методы решения задач дискретной оптимизации

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

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

Термин «теория расписаний» предложил Р. Беллман в 1956 году [45]. Для решения задач теории расписаний применяются методы и алгоритмы решения задач дискретной оптимизации.

В общем случае задача дискретной оптимизации заключается в определении минимума или максимума некоторой функции f(x) на множестве допустимых решений G, то есть в нахождении такого решения x0 е G, что

f (x0 )= min f (x), (1.4)

xeG

где О - множество допустимых решений, 0 < < да,

- число элементов множества О.

Примером задачи дискретной оптимизации является задача о ранце [46, 47, 48, 49].

Постановка задачи. Имеется п предметов, каждый из которых характеризуется стоимостью pj > 0 и весом ну > 0, у =1 ,2,...,п. Имеется ранец, грузоподъемность которого равна С>0. Требуется положить в ранец набор предметов максимальной суммарной стоимости. При этом вес выбранных предметов не должен превышать грузоподъемности ранца.

Математическое описание задачи. Пусть ху =1, если предмет находится в

рюкзаке, ху =0 в противном случае, то есть ху е{0,1},у =1 ,2,...,п. Найти такие ху, при которых

и

/(х) = XРуху ^ тах (15)

j=1

и

X н]х]- < С. (1.6)

у=1

Множеством О для этой задачи является множество векторов х=(х1, х2,

и

... хп), удовлетворяющих условиям Xнуху < С.

j=1

Задача о ранце относится к задачам целочисленного линейного программирования [50, 51, 52, 53, 54].

Примером задачи дискретной оптимизации также является задача коммивояжера [55, 56, 57, 58, 59].

Постановка задачи. Коммивояжер должен посетить п городов. Каждый город имеет номер 1,2, ..., п. Между каждой парой городов / и у задано расстояние с у > 0, причем в разном направлении расстояние между городами могут быть разными, Су ^ су,. В начальный момент времени коммивояжер находится в городе с

номером 0. Он выезжает из этого города, объезжает все города, посетив каждый из них один раз, и возвращается в город 0. Необходимо найти такую последова-

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

Решение этой задачи можно представить как вектор, характеризующий порядок посещения городов ж = (уьj2,...,]п). Для маршрута ж пройденное расстояние можно вычислить как суммарную длину по формуле:

п-1

Кж) = соЛ + 1 сАс^+1 + с]п0 . (1.7)

I =1

О - множество возможных маршрутов (перестановок).

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

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

С середины XX века началось активное теоретическое исследование задач теории расписаний [60, 61, 62], предложены первые методы их решения [63].

Большинство задач теории расписаний являются МР-трудными [64, 65, 66, 67, 68, 69], для решения которых разрабатываются приближенные эвристические алгоритмы с известными оценками погрешности получаемого результата [70, 71, 72].

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

Наиболее распространенными методами решения задач теории расписаний является метод ветвей и границ [73, 74, 75, 76, 77, 78, 79], метод динамического программирования [45, 80, 81, 82].

Метод динамического программирования получил большое распространение при получении точного решения задач дискретной оптимизации [83, 84, 85, 86].

Общая схема многошагового процесса принятий оптимальных решений (с дискретным временем) состоит в следующем. Пусть имеется некоторая система S, состояние которой в начальный момент времени ?0 = 0 характеризуется числом х0. В каждый момент времени к, к =1,...,п, делается некоторый выбор ^, в результате чего система изменяет свое состояние. При этом каждое решение (выбор) х^ должно удовлетворять как исходным ограничениям системы £ так и ограничениям, возникающим за счет ранее сделанных выборов хь х2,..., хк ч. Каждое решение (выбор) приносит определенный выигрыш (доход). Для применимости схемы динамического программирования необходимо, чтобы общий доход за п шагов был равен сумме доходов от отдельных шагов. Последовательность допустимых решений (допустимого выбора) на отдельных шагах обычно называют стратегией. Требуется найти среди всех стратегий оптимальную, дающую максимум суммарного дохода.

В основе динамического программирования лежит следующая простая характеристика оптимальной стратегии, сформулированная Р. Беллманом в 50-е годы XX века и названная принципом оптимальности Беллмана [45]: каково бы ни были начальное состояние и первое решение, последующие решения составляют оптимальную политику по отношению к начальному состоянию, полученному в результате первого решения.

Модификацией метода динамического программирования является графический метод, который широко используется в решении задач управления проектами [87, 88].

Дадим иллюстрацию метода на примере 1. 1 решения классической задачи о ранце (1.5), (1.6).

Пример 1.1. Имеются три предмета, данные о ценностях и весах которых приведены в таблице 1.1.

Таблица 1.1 - Данные о ценностях и весах предметов

1 2 3

Ру 2 3 1

3 2 1

Пусть С = 4.

Строим на плоскости систему координат, ось абсцисс соответствует предметам у, ось ординат - их весу wJ■. По оси предметов отмечаем номера предметов 1, 2, 3 (рисунок 1.1).

1 Вес £1

И И №

/ т И

2 / [1]

/ » -»

О 1 2 3 Предмет

Рисунок 1.1 - Пример графического представления метода динамического

программирования

Любой путь из начальной вершины 0 в одну из конечных соответствует одному из наборов предметов. Причем длины горизонтальных дуг равны 0, а длины наклонных - ценности предмета ру. Длина пути, соединяющая начальную вершину с одной из конечных, соответствует суммарной ценности набора предметов с суммарным весом не более 4. Значение координаты по оси ординат соответствует суммарному весу. Таким образом, задача свелась к определению пути с максимальной длиной, который соответствует решению задачи. Этот путь выделен на

рисунке 1.1 толстыми дугами, это соответствует тому, что предметы 2 и 3 с суммарной ценностью 4 и суммарным весом 3 будут размещены в рюкзаке.

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

Под ветвлением понимают процесс разбиения множества G на подмноже-

r

ства G, сG, i=1,2,...,r, причем UG = G. Таким образом, задача (1.4) разбивается

i=1

на подзадачи (1.8)

f(x0 )= min f(x), (1.8)

xeG'

где G'c G.

При этом каждая подзадача Gi является основой для другого ветвления. В результате ветвления формируется дерево поиска оптимального решения.

Верхней оценкой для подзадачи Gi называется значение (1.9), которое используется для оценки возможности того, что подзадача содержит оптимальное решение исходной задачи.

UBi > min f (x), (1.9)

xeGt

Нижней оценкой для подзадачи Gi называется значение (1.10), которое в процессе работы алгоритмов ветвей и границ сравнивается со значением целевой функции, рассчитанным для лучших допустимых решений.

Щ < min f (x), (1.10)

xeGj

Если значение нижней оценки больше текущего значения целевой функции, то подмножество Gi не содержит оптимального решения и в дальнейшем не рассматривается.

Рассмотрим применение метода ветвей и границ на примере решения классической задачи о ранце (1.5), (1.6).

Выберем следующий способ ветвления: множество О разбиваем на подмножества О0, в котором находятся все решения, соответствующие Х1=0, и подмножество Gl, в котором находятся все решения, соответствующие х1=1. Аналогичным образом разбиваются на подмножества О0 и G1, исходя из двух возможных значений х2=0 или х2=1 и т.д.

Каждой подзадаче О' в этом дереве поиска соответствует ситуация, когда значения некоторых переменных хь х2,...,х]-1 уже фиксированы.

Перед очередным выбором значения для переменной х]- необходимо прове-

]-1

рить выполнение условия X™кхк + ^^ > С. Если условие не выполняется, тогда для

к=1

этой подзадачи фиксируется х=0, и решение продолжается только по ветке

Оо = О'.

Верхняя оценка рассчитывается для подзадачи, для которой значения переменных х1, х2,..., Х]-1 фиксированы, например, по формуле (1.11).

( \

'I +

!еМ

Р]+1

где а]+1 ,

+1

]+1 - номер очередной еще не рассмотренной переменной, М - множество фиксированных переменных.

Развитием методов решения задач дискретной оптимизации является метод сетевого программирования и его частный случай - метод дихотомического программирования [89, 90, 91, 92].

Широко применяются для построения допустимых расписаний проекта эвристические алгоритмы, основанные на некоторых разумных правилах [9, 93, 94, 95, 96, 97, 98, 99, 100].

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

Р = X Р1 + С - X wl •а]+1, (1.11)

" " " V 1еМ у

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

© © ©■■'■"О б'-'-©

Рисунок 1.2 - Структурное представление метода ветвлений В работе [94] рассмотрены основные эвристические правила распределения ресурсов по фронту работ (максимальному множеству независимых работ, которые могут выполняться одновременно), если количество ресурсов в момент 1 недостаточно для выполнения всех работ с максимальной интенсивностью.

Правило 1 . Распределение ресурсов по степени критичности работ. Степенью критичности называют наиболее поздний момент начала работы при условии, что все работы выполняются с максимальной интенсивностью. В первую очередь ресурсы распределяются на работы с минимальной степенью критичности.

Правило 2. По минимальной продолжительности работы. В первую очередь выполняются работы, имеющие минимальную продолжительность.

Правило 3. По минимальному позднему моменту окончания. В первую очередь выполняются работы с минимальным поздним моментом окончания.

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

В работах [101, 102] предложены механизмы распределения ресурсов типа "мощности", то есть материально-технических и трудовых ресурсов, на основе эвристических правил приоритета по возрастанию первых разностей работ проекта, по возрастанию величины комплексных оценок работ, по максимальным эф-фективностям работ в проекте.

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

Все эвристические алгоритмы можно разделить на три группы: конструктивные, улучшающие и метаэвритсические. Конструктивные методы применяются для построения допустимого решения (схемы составления расписания (последовательная, параллельная, прямая, обратная, двунаправленная и т.д.), правила приоритета работ, комбинация различных схем составления расписаний и правил приоритета). С помощью улучшающих методов можно получить более эффективное решение из имеющегося допустимого решения (поиск соседних решений, алгоритмы спуска). Эволюция эвристических методов календарного планирования привела к метаэвристическим методам (генетические алгоритмы [104, 105, 106], метод муравьиных колоний [107, 108] и др.). Метаэвристические методы представляют динамические системы, которые комбинируют конструктивные и улуч-

шающие методы для непрерывного совершенствования расписания, вплоть до нахождения оптимального решения.

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

Порядок работ задается их приоритетами, которые вычисляются по правилам приоритета [109],

1) основанным на свойствах работ:

- по самому короткому времени выполнения работ;

- по самому длинному времени выполнения;

- случайный список приоритетов;

2) основанным на последовательности работ:

- наибольшее число прямых последователей;

- основанное на приоритете работ, не являющихся непосредственными последователями;

- основанное на интегральном весе (продолжительность работы по отношению к продолжительности всех последователей);

3) основанным на критическом пути:

- раннее время начала работы;

- раннее время окончания работы;

- позднее время начала работы;

- позднее время окончания работы;

- минимальный резерв времени;

- минимальное увеличение продолжительности проекта при откладывании всех еще не имеющихся в расписании работ после выполнения выбранной работы;

- динамическое самое раннее время начала работы;

- динамическое самое позднее время окончания работы;

- динамический минимальный резерв времени;

4) основанным на количестве используемых ресурсов:

- самая большая потребность в ресурсах отдельной работы;

- самая большая потребность в ресурсах работы и ее последователей;

- эквивалентная по ресурсам продолжительность работы;

- эквивалентная по ресурсам продолжительность работы и ее последователей;

5) комбинированным:

- комбинация трех предшествующих правил составления списка приоритетов.

Схемы определения начала работ определяются направлением формирования расписания: от первого дня к последнему (прямая схема), от последнего дня к первому (обратная схема) и двунаправленная (часть работ выполняется как можно раньше, другая - как можно позже). Схемы разрешения ресурсных конфликтов -последовательная и параллельная [110].

Список литературы диссертационного исследования кандидат наук Роговая Людмила Александровна, 2019 год

/ т И

2 / [1]

/ » -»

О 1 2 3 Предмет

Рисунок 1.1 - Пример графического представления метода динамического

программирования

Любой путь из начальной вершины 0 в одну из конечных соответствует одному из наборов предметов. Причем длины горизонтальных дуг равны 0, а длины наклонных - ценности предмета ру. Длина пути, соединяющая начальную вершину с одной из конечных, соответствует суммарной ценности набора предметов с суммарным весом не более 4. Значение координаты по оси ординат соответствует суммарному весу. Таким образом, задача свелась к определению пути с максимальной длиной, который соответствует решению задачи. Этот путь выделен на

рисунке 1.1 толстыми дугами, это соответствует тому, что предметы 2 и 3 с суммарной ценностью 4 и суммарным весом 3 будут размещены в рюкзаке.

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

Под ветвлением понимают процесс разбиения множества G на подмноже-

r

ства G, сG, i=1,2,...,r, причем UG = G. Таким образом, задача (1.4) разбивается

i=1

на подзадачи (1.8)

f(x0 )= min f(x), (1.8)

xeG'

где G'c G.

При этом каждая подзадача Gi является основой для другого ветвления. В результате ветвления формируется дерево поиска оптимального решения.

Верхней оценкой для подзадачи Gi называется значение (1.9), которое используется для оценки возможности того, что подзадача содержит оптимальное решение исходной задачи.

UBi > min f (x), (1.9)

xeGt

Нижней оценкой для подзадачи Gi называется значение (1.10), которое в процессе работы алгоритмов ветвей и границ сравнивается со значением целевой функции, рассчитанным для лучших допустимых решений.

Щ < min f (x), (1.10)

xeGj

Если значение нижней оценки больше текущего значения целевой функции, то подмножество Gi не содержит оптимального решения и в дальнейшем не рассматривается.

Рассмотрим применение метода ветвей и границ на примере решения классической задачи о ранце (1.5), (1.6).

Выберем следующий способ ветвления: множество О разбиваем на подмножества О0, в котором находятся все решения, соответствующие Х1=0, и подмножество Gl, в котором находятся все решения, соответствующие х1=1. Аналогичным образом разбиваются на подмножества О0 и G1, исходя из двух возможных значений х2=0 или х2=1 и т.д.

Каждой подзадаче О' в этом дереве поиска соответствует ситуация, когда значения некоторых переменных хь х2,...,х]-1 уже фиксированы.

Перед очередным выбором значения для переменной х]- необходимо прове-

]-1

рить выполнение условия X™кхк + ^^ > С. Если условие не выполняется, тогда для

к=1

этой подзадачи фиксируется х=0, и решение продолжается только по ветке

Оо = О'.

Верхняя оценка рассчитывается для подзадачи, для которой значения переменных х1, х2,..., Х]-1 фиксированы, например, по формуле (1.11).

( \

'I +

!еМ

Р]+1

где а]+1 ,

+1

]+1 - номер очередной еще не рассмотренной переменной, М - множество фиксированных переменных.

Развитием методов решения задач дискретной оптимизации является метод сетевого программирования и его частный случай - метод дихотомического программирования [89, 90, 91, 92].

Широко применяются для построения допустимых расписаний проекта эвристические алгоритмы, основанные на некоторых разумных правилах [9, 93, 94, 95, 96, 97, 98, 99, 100].

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

Р = X Р1 + С - X wl •а]+1, (1.11)

" " " V 1еМ у

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

© © ©■■'■"О б'-'-©

Рисунок 1.2 - Структурное представление метода ветвлений В работе [94] рассмотрены основные эвристические правила распределения ресурсов по фронту работ (максимальному множеству независимых работ, которые могут выполняться одновременно), если количество ресурсов в момент 1 недостаточно для выполнения всех работ с максимальной интенсивностью.

Правило 1 . Распределение ресурсов по степени критичности работ. Степенью критичности называют наиболее поздний момент начала работы при условии, что все работы выполняются с максимальной интенсивностью. В первую очередь ресурсы распределяются на работы с минимальной степенью критичности.

Правило 2. По минимальной продолжительности работы. В первую очередь выполняются работы, имеющие минимальную продолжительность.

Правило 3. По минимальному позднему моменту окончания. В первую очередь выполняются работы с минимальным поздним моментом окончания.

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

В работах [101, 102] предложены механизмы распределения ресурсов типа "мощности", то есть материально-технических и трудовых ресурсов, на основе эвристических правил приоритета по возрастанию первых разностей работ проекта, по возрастанию величины комплексных оценок работ, по максимальным эф-фективностям работ в проекте.

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

Все эвристические алгоритмы можно разделить на три группы: конструктивные, улучшающие и метаэвритсические. Конструктивные методы применяются для построения допустимого решения (схемы составления расписания (последовательная, параллельная, прямая, обратная, двунаправленная и т.д.), правила приоритета работ, комбинация различных схем составления расписаний и правил приоритета). С помощью улучшающих методов можно получить более эффективное решение из имеющегося допустимого решения (поиск соседних решений, алгоритмы спуска). Эволюция эвристических методов календарного планирования привела к метаэвристическим методам (генетические алгоритмы [104, 105, 106], метод муравьиных колоний [107, 108] и др.). Метаэвристические методы представляют динамические системы, которые комбинируют конструктивные и улуч-

шающие методы для непрерывного совершенствования расписания, вплоть до нахождения оптимального решения.

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

Порядок работ задается их приоритетами, которые вычисляются по правилам приоритета [109],

1) основанным на свойствах работ:

- по самому короткому времени выполнения работ;

- по самому длинному времени выполнения;

- случайный список приоритетов;

2) основанным на последовательности работ:

- наибольшее число прямых последователей;

- основанное на приоритете работ, не являющихся непосредственными последователями;

- основанное на интегральном весе (продолжительность работы по отношению к продолжительности всех последователей);

3) основанным на критическом пути:

- раннее время начала работы;

- раннее время окончания работы;

- позднее время начала работы;

- позднее время окончания работы;

- минимальный резерв времени;

- минимальное увеличение продолжительности проекта при откладывании всех еще не имеющихся в расписании работ после выполнения выбранной работы;

- динамическое самое раннее время начала работы;

- динамическое самое позднее время окончания работы;

- динамический минимальный резерв времени;

4) основанным на количестве используемых ресурсов:

- самая большая потребность в ресурсах отдельной работы;

- самая большая потребность в ресурсах работы и ее последователей;

- эквивалентная по ресурсам продолжительность работы;

- эквивалентная по ресурсам продолжительность работы и ее последователей;

5) комбинированным:

- комбинация трех предшествующих правил составления списка приоритетов.

Схемы определения начала работ определяются направлением формирования расписания: от первого дня к последнему (прямая схема), от последнего дня к первому (обратная схема) и двунаправленная (часть работ выполняется как можно раньше, другая - как можно позже). Схемы разрешения ресурсных конфликтов -последовательная и параллельная [110].

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

Алгоритм локальной оптимизации [111, 112,113, 114], в случае решения задачи минимизации, для решения я0 в окрестности Р(я0 ) определяет наилучшее

решение я*, такое, что

f (я1 )= min f (я).

жеР(ж0)

Если выполняется условие f (я* )< f (я0), то рассматривается окрестность Р(я*) и определяется наилучшее решение я2 и так до тех пор, пока не будет получено локально-оптимальное решение як

f (як )= min f (я).

яер(як)

Далее берется новое начальное решение и методом локальной оптимизации получается локально-оптимальное решение и т.д. Либо расширяется окрестность поиска решения

Р{жк ) = и Р(я),

Ж&Р(Жк )

где як - локально-оптимальное решение,

Р(жк) - объединение всех окрестностей решений, принадлежащих окрестности локально-оптимальных решений.

Если лк является локально-оптимальным решением в новой окрестности, то

производится дальнейшее расширение окрестности, либо остается полученное решение.

Недостатком метода является отсутствие алгоритмов оценки близости полученного локально-оптимального решения к оптимальному.

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

Для построения допустимых расписаний проекта с минимальной его продолжительностью и ограниченными ресурсами нашли применение генетические алгоритмы [116, 117, 118, 119, 120, 121, 122].

В общем виде генетический алгоритм реализуется в несколько этапов [123]:

1) формирование начальной популяции;

2) осуществление отбора наилучших решений;

3) формирование потомства, скрещиванием полученных на предыдущем этапе решений и внесение в них случайных изменений (мутаций);

4) формирование новой популяции из родительских решений и их потомков;

5) проверка условия на завершение работы алгоритма. Механизм генетического алгоритма представлен на рисунке 1.3.

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

Отбор наилучших расписаний для производства потомства происходит на основании показателя функции приспособленности, как правило, функции, вычисляющей продолжительность проекта, что обеспечивает последовательное приближение к оптимальному решению [124, 125].

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

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

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

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

- осуществить модификацию симплекс-метода для решения задачи календарного планирования работ неоднородных команд специалистов;

- формализовать задачу календарного планирования работ неоднородных команд специалистов с учетом аутсорсинга;

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

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

ГЛАВА 2. РАЗРАБОТКА АЛГОРИТМОВ ОПТИМИЗАЦИИ

КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ РАБОТ НЕОДНОРОДНЫХ

КОМАНД СПЕЦИАЛИСТОВ

§2.1 Постановка задачи и алгоритмы календарного планирования работ неоднородных команд специалистов

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

Определение 1. Неоднородной командой специалистов (далее командой) называется множество специалистов различного вида, необходимых для выполнения работы [128].

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

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

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

Рассмотрим проект из п независимых работ. Каждая работа выполняется командой специалистов различного типа за время тг.

Задано число специалистову-го типа N ■ , ] = 1, т.

Обозначим а1у - количество специалистов у-го типа, включенных в команду

к, хк ^)=1, если команда к в момент / выполняет работу к, хк )=0, в противном

случае. В силу ограниченности числа специалистов каждого типа справедливы ограничения

^а,хк($< , I е[0,т], ] = 1т, (2.1)

к

где Т - момент завершения выполнения всех работ. Условия выполнения всех работ имеют вид

т _

|хк (т)4т = т, , ' = 1, п. (2.2)

о

Постановка задачи [130].

Определить хк ^), к = 1, п, при которых время Т выполнения всех работ минимально, при ограничениях (2.1), (2.2). Это динамическая задача дискретной оптимизации, которая является №-трудной в силу ограничений (2.1). Поставим задачу как задачу линейного программирования. Для этого введем понятие набора команд.

Определение 2. Набором команд (далее набором) называется совокупность команд Q, такая, что выполняются условия:

х а; < , ]=1т. (2.3)

'е<2

Заметим, что набор команд может работать одновременно.

Определение 3. Максимальным набором называется набор, к которому нельзя добавить ни одной команды, не нарушив ограничения (2.3).

Обозначим Я - множество всех максимальных наборов N = , х. - продолжительность работы у-го набора. Примем, что допустимы перерывы в выполнении работ.

Любой набор ' е 0 будем описывать вектором и ={му}, где и1}=1, если в наборе присутствует команда у, =0 в противном случае.

Задача 2.1. Определить х = }, минимизирующие

0(х )=£ ^ (2.4)

при ограничениях хг > 0,

Е>т, , j = 1, и . (2.5)

г

Получили задачу линейного программирования.

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

Рассмотрим частный случай задачи, когда максимальные наборы содержат все команды за исключением одной [131]. Очевидно, что таких наборов п.

Примем, что /-ый набор не содержит /-ой команды. В этом случае задача принимает вид: минимизировать (2.4) при ограничениях хг > 0, г = 1, п и

Еxj >т ,г = 1И. (2.6)

j

Поскольку 0 = Е X , то перепишем (6) в виде

г

0-х >тг, г = 1П. (2.7)

Упорядочим наборы по убыванию т, т.е. т{ > т{ >... > т{ .

Теорема 1. Существует оптимальное решение задачи (2.4), (2.6) следующего

вида:

1) в случае, если т +т, >т , то

гп-1 1п \

т + т — т

х = _п-л—п—I, хг = 0, j = 2ТТП—2.

г1 2 ' гj

т ■ — т- +т-X =т — X = 1п гп—1 ^

гп—1 гп г1 2

тг — тг + тг

гп—1 п г1

X,- =т — х. =

п 2 п 1 1 2

при этом 0

т ■ + т ■ + ти i л i 1 n-1 n

min 2

2) в случае, если т + Т < т существуют несколько оптимальных ре-

hn-1 ln \

шений вида:

х, = 0, j = 1 n - 2 г]

х- > т-ln-1 ln

хг >Ti in in-1

xi + xi = Ti n-1 ln 1

при этом 0 . =Т-r min h

1

Доказательство теоремы 1. Исключим все наборы кроме ¡1, ¡п-1 и ¡„. Фикси-

руем время работы х набора ¡1. Имеем

'1

х • > т- - х. , 'п-1 1п г1

х• >т. -х. , 'п п-1 г1

х- + х- > т■ 'п-1 'п г1.

Пусть т + т > т . Возьмем х,- = т - х , х = Т - х , 'п-1 п 1 п-1 п 1 п п-1 1

0 = х. + х. + х, =т- +т. -х. . г г л 1 г л г гл п п -1 п-1 п 1

Продолжительность всех работ 0 тем меньше, чем больше х

1

Имеем х + х- =т +Т -2х. =т. . п-1 гп 1п п-1 ' г1

т. +т. -т.

I I 1

Получаем х; = —-п-1-1,

т. -т. + т. 1 1 л 1л

X; =Г. -X. - П П -1 1

1n -1 1n 11 2

т. -т. +т. 1 л 1 1Л v -т V - n-1 n 1 Xi -т1 , -Xi -

n

n-1 1 2

т. + т. +т. 1 - 1 1, 0 _ n-1 n 1

min 2

Пусть т, +т. <т. . В этом случае х, - 0, а х- + х. -т- . Любые значе-

1п л 1 h 1 ^ 1 1 1

n-l n 1 1 n-1 n 1

ния х , х , удовлетворяющие условиям

n-1 1n

Xi - т1 , 1n-1 1n

X — т-1n 1n-1

1n-1 1n 1

определяют оптимальные решения задачи с величиной ©min - т .

Заметим теперь, что при полученном решении все задачи от i2 до in-2 также будут выполнены.

Теорема доказана.

Пример 2.1. Рассмотрим численный пример. Пусть т=10, т2 =8, т3 =4. Поскольку т0+т0 >10, то х -12—10 -1, х? - 4-1 - 3 , X - 8-1 - 7 , 0 . - 11. J 2 3 1 2 min

Заметим, что при любой очередности наборов, одна работа выполняется с перерывом.

Обозначим т(т) - минимальную продолжительность проекта в зависимости от т - (т-, 1 - 1,n).

Теорема 2. T (т) выпуклая функция т.

Доказательство теоремы 2. Пусть т1 и т2 два допустимых решения. Возьмем т-ат1 +(1 -а)т2, 0 <а < 1.

Обозначим х1 - оптимальное решение для т1, х2 - оптимальное решение для

т

Очевидно, что х = ах1 + (1 - а)х2 является допустимым решением для т. При этом продолжительность проекта 0(х) = аТ (т1)+ (1 -а)Т (т2). Имеем

Т(т) < 0(х) = аТ(т1) + (1 - а)Т(т2).

Теорема доказана.

Недостатком рассмотренного выше алгоритма являются возможные прерывания в выполнении работ. Естественно желательно минимизировать число прерываний. Возможные планы выполнения работ определяются перестановками ж = (ц, г2,..., гп) наборов.

Задача 2.2. Определить перестановку ж, при которой число прерываний работ минимально.

Пример 2.2. Имеются пять работ и получено оптимальное решение из пяти наборов команд. В таблице 2.1 приведены данные при очередности наборов

ж0 = (1,2,3,4,5).

Таблица 2.1 - Данные при очередности наборов ж0 = (1,2,3,4,5)

} 1 тj ц

1 2 3 4 5

1 1 1 9 1

2 1 1 5 0

3 1 1 8 1

4 1 1 7 0

5 1 1 6 1

х1 5 7 5 3 6 0 = 26 3

Единица в клетках означает, что в данном интервале 1 выполняется работа Ц - число прерываний работы Определим общее число прерываний работ. Рабо-

та 1 очевидно прерывается. Работа 2 заканчивается в первом интервале, поэтому не прерывается. Работа 3 прерывается. Работа 4 не прерывается, поскольку заканчивается во втором интервале. Наконец работа 5 прерывается. Всего имеем три прерывания работ. Невозможность иметь таблицу прерываний (расстояний между городами в задаче коммивояжера) затрудняет применение методов типа метода ветвей и границ, требующих получение нижних оценок. Поэтому применим методы, которые основаны на построении окрестностей решений. Это методы локальной оптимизации, включая генетические алгоритмы. Рассмотрим метод локальной оптимизации, в котором окрестность решений получается путем операций транспозиции (перестановка соседних элементов) исходного решения.

Описание алгоритма

Шаг 1. Сформировать начальную перестановку ж.

Шаг 2. Построить окрестность 2 (ж), переставляя пары соседних наборов.

Шаг 3. Определить лучшее решение в окрестности ж .

Шаг 4. Перейти к шагу 2.

Шаг 5. Если в очередной окрестности нет лучшего решения, то получено локально-оптимальное решение.

Далее можно выбрать новое начальное решение и повторить процедуру.

Пример 2.3. Возьмем данные примера 2.2. Начальная перестановка Ж = (1,2,3,4,5). Окрестность 2(ж) содержит четыре перестановки: ж = (2,1,3,4,5), ж =(1,3,2,4,5), ж =(1,2,4,3,5), ж =(1,2,3,5,4).

Определяем для каждого решения число прерываний работ.

1. ж = (2,1,3,4,5). Решение приведено в таблице 2.2, ь{ж1) =3. Таблица 2.2 - Решение задачи

} 1

2 1 3 4 5

1 0 1 0 0 1 9 1

2 0 1 1 0 0 5 0

3 1 0 0 1 0 8 1

4 1 0 0 1 0 7 0

5 0 0 1 0 1 6 1

7 5 5 3 6 26 3

Действуя аналогично, получаем наилучшую перестановку в окрестности

щ =(1,2,4,3,5), ь(щ) = 1.

Строим окрестность Q (щ) :

щ =(2,1,4,3,5), щ =(1,4,2,3,5), щ = (1,2,4,5,3).

Наилучшие решения в окрестности щ = (1,4,2,3,5) и щ = (1,2,4,3,5), ь(щ )=ьЩъ )=1.

Поэтому щ является локально-оптимальным решением. Можно, конечно, продолжить процедуру для второго лучшего в окрестности решения, но вряд ли мы получим решение с меньшим ь(ж), поскольку наборы 1 и 5 очень далеки друг от друга и прерывание работы 1 неизбежно.

Попробуем взять другое начальное решение, сблизив наборы 1 и 5, сохранив близость наборов 3 и 5.

Возьмем, например, перестановку щ = (3,5,1,2,4). Расчеты приведены в таблице 2.3.

Таблица 2.3 - Результаты решения

j i TJ L

3 5 1 2 4

1 0 1 1 0 0 9 0

2 1 0 1 0 0 5 0

3 0 0 0 1 1 8 0

4 0 0 0 1 1 7 0

5 1 1 0 0 0 6 0

xi 5 6 5 7 3 26 0

Получили оптимальное решение без прерывания работ.

При запрещении прерывания работ задача назначения команд становится сложной (№-трудной) задачей дискретной оптимизации.

Для ее решения применяются эвристические алгоритмы, основанные на правилах приоритета работ [132]. Достаточно популярным является правило приоритета работ, согласно которому в первую очередь выполняются так называемые критические работы [29].

В нашем случае критические работы это работы с наибольшей продолжительностью т .

Описание алгоритма

Шаг 1. В начальный момент времени 1=0 назначаем команды в очередности убывания продолжительностей соответствующих работ до получения максимального набора.

Шаг 2. В момент окончания какой-либо работы назначаем команды также в очередности убывания продолжительностей еще невыполненных работ.

Пример 2.4. Имеются пять работ, и соответственно пять команд, данные о которых приведены в таблице 2.4.

Имеются также пять типов специалистов, причем специалистов каждого типа равно 2.

Таблица 2.4 - Данные о работах и командах специалистов

} 1

1 2 3 4 5

1 1 1 0 1 0 12

2 0 1 1 0 1 10

3 1 0 0 1 0 8

4 0 1 1 0 0 4

5 0 0 1 1 1 3

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

Шаг 1. В момент t=0 начинаем работы 1, 2 и 3, которые образуют максимальный набор.

Шаг 2. В момент t=8 заканчивается работа 3. Начинаем работу 5. Работу 4 начать не можем, поскольку набор (1, 2, 4) не допустим.

Шаг 3. В момент t=10 заканчивается работа 2. Начинаем работу 4, поскольку набор (1, 4, 5) допустим.

Шаг 4. В момент t=14 заканчивается работа 4.

Продолжительность выполнения всех работ равна 14.

Оценку снизу можно получить, разрешив прерывание работ.

Имеются пять максимальных наборов команд:

-(1,2,3), 02 -(1,2,5), Q3 -(2,3,4), Q -(2,3,5), Q5 -(1,4,5).

Соответствующая задача имеет вид: минимизировать

X1 + X2 + X3 + X4 + X5

при ограничениях

X1 + X2 + X5 — 12

X1 + X2 + X3 + X4 — 10

X1 + X3 + X4 — 8

х3 + х5 — 4

X2 + X4 + X5 — 3

Ее оптимальное решение х1 - 7, х2 - 2, х3 -1, х4 - 0, х5 - 3 с величиной

0 . -13. min

При этом одна работа выполняется с перерывом, так что полученное выше решение является оптимальным. Решение большого числа примеров показало, что средняя относительная погрешность равна 5 %, причем с ростом числа задач (команд) относительная ошибка уменьшается.

Рассмотрим задачу назначения команд для случая, когда существуют зависимости между работами [133]. Эти зависимости будем описывать сетевым гра-

фиком, вершины которого соответствуют работам, а дуги зависимостям типа «финиш-старт» (дуга (1,]) означает, что работа] не может начаться, пока не завершена работа 1) [134].

Обозначим - множество работ, которые могут выполняться в Б-ом интервале (интервал между (б-1) и Б-ым событиями, 5 = 1, г), - множество интервалов, в которых может выполняться работа 1, у5 = (у , г е Я5) продолжительности работ, выполняемых в Б-ом интервале, А 5 (у5) - минимальная длина Б-го интервала как функция у5. Продолжительность программы равна

0(у)= Е А5{у5)

5 = 1 (2.8)

Задача 3. Определить (у), г е я5, 5 = 1,г минимизирующие (2.8) при услови-

ях

Е У5 ^ , I е Я,. (2.9)

Теорема 3. 0(у) выпуклая функция у.

Доказательство теоремы 3. Доказательство следует из теоремы 2, поскольку в каждом интервале работы являются независимыми, и известного факта, что сумма выпуклых функций является выпуклой функцией. Далее заметим, что для любых двух решений у1 и у2, удовлетворяющих (2.9), их выпуклая линейная комбинация также удовлетворяет (2.9). Теорема доказана.

Рассмотрим решение задачи для частного случая, когда максимальные наборы содержат все команды за исключением одной [135]. В этом случае решение задачи для каждого интервала выписывается в явном виде:

А 5 (У5 ) =

У/,5, еСЛиУц ,5 > У1 .,5 + Уп,5 1 п-1' п

Уц ,5 + Уг ,5 + Уп,5 (2.10)

1 п-1' п

2 еслиУ1,5 < Уг ,,5 + Угп,5

2 1 п-1 п

<

Учитывая выпуклость целевой функции (2.10) задача может быть решена методами градиентной оптимизации, в частности методом покоординатной оптимизации.

Рассмотрим простой численный пример 2.5.

Пример 2.5. Рассмотрим сетевой график, представленный на рисунке 2.1.

(1)

Рисунок 2.1. Сетевой график «вершина - событие» У дуг указаны номера работ. В таблице 2.5 приведены команды, выполняющие работы программы, а в таблице 2.6 продолжительности работ. Таблица 2.5 - Данные о командах, выполняющих работы

} 1

1 2 3

(0,1) 0 1 1

(0,2) 0 1 1

(1,2) 1 0 1

(1,3) 1 1 0

(2,3) 0 1 1

Таблица 2.6 - Продолжительность работ

1 1 2 3 4 5

24 10 8 28 8

1 шаг. Возьмем начальное решение

уп=12, у12=12, у42=14, У4з=14

продолжительность программы

е,= 12 +12 + 8 +14 +14 = 43.

1 2

2 шаг. Оптимизируем по первой работе. Оптимальное решение У11=10, У12=14, У42=14, у43=14 продолжительность программы

02 = 10 + 14 + 8 +14 +14 = 42 .

2 2

3 шаг. Оптимизируем по четвертой работе. Оптимальное решение

У11=10, У12=14, У42=20, у43=8

продолжительность программы

^ _ 14 + 20 + 8 „ _

0, = 10 +-+ 8 = 39 .

3 2

4 шаг. Оптимизируя по первой работе, получаем то же самое решение. Поэтому решение третьего шага является оптимальным.

В полученном решении имеется одно прерывание третьей работы. Если прерывание запрещены, то применяем эвристический алгоритм по степени критичности работ, то есть, начинаем в первую очередь критические работы. Критической является работа 2. Шаг 1. В момент ^=0 выполняем работы 1 и 2. Шаг 2. В момент ^=10 начинаем выполнение критической работы 4. Шаг 3. В момент 1:3=24 начинаем выполнение работы 3. Шаг 4. В момент :4=32 начинаем выполнение работы 5. Продолжительность программы Т=40.

Полученное решение является оптимальным, поскольку решением без прерываний работ с продолжительностью 39 не существует.

§2.2 Модификация симплекс-метода для решения задачи календарного планирования работ неоднородных команд специалистов

Старейшим и одним из самых известных алгоритмов для задачи линейного программирования является симплекс-метод [136].

Предложим модифицированный симплекс-метод для решения задачи линейного программирования (2.4), (2.5), в котором вектор, включаемый в базис на очередной итерации, определяется в результате решения задачи дискретной оптимизации [137].

Описание алгоритма

Шаг 1. Сформировать начальное решение х и базис любым эвристическим алгоритмом.

Шаг 2. Выразить единичные вектора у' ( у' = 1, у'. = 0, если у ф ') через вектора базиса

У = Е суи

з

и определить щ = Е сгу , ' = 1, п.

)

Шаг 3. Решить задачу:

с = Е а121 ^ тах (211)

г

при ограничениях (2.3), = (0;1).

Если в оптимальном решении задачи с < 1, то и - оптимальное решение задачи. Если с > 1, то решение можно улучшить, введя в базис оптимальное решение задачи (2.3), (2.11).

К сожалению, задача (2.3), (2.11) является сложной (^Р-трудной) задачей дискретной оптимизации. Рассмотрим частный случай, когда она решается эффективно. Пусть имеется тип специалистов который является «узким местом»,

т.е. допустимые наборы определяются только числом этих специалистов (т.е. одним ограничением):

I< N. (2.12)

г

В этом случае задача (2.3), (2.11) является классической задачей о ранце, эффективно решаемой при целочисленных значениях ц методами динамического и дихотомического программирования [90].

Пример 2.6. Имеются 5 работ, данные о которых приведены в таблице 2.7.

Таблица 2.7 - Данные о работах

1 1 2 3 4 5

ъ 2 4 6 5 3

а( 6 5 4 4 7

Примем N = 11.

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

и1 = (0, 0, 1, 1, 0), = 5

и2 = (0, 1, 1, 0, 0), ^2 = 1 и3 = (1, 1, 0, 0, 0), хз = 2 и4 = (0, 0, 0, 0, 1), Х4 = 3 и5 = (0, 1, 0, 0, 0), Х5 = 1 Время выполнения всех работ Т = 12.

2 шаг. Выражаем векторы у1 через базисные векторы. Имеем

Ц = 1, Ц = 1,