Автоматика и телемеханика, № 1, 2019
Оптимизация, системный анализ
и исследование операций
© 2019 г. В.Н. БУРКОВ, д-р техн. наук (vlab17@br.ru)
(Институт проблем управления им. В.А. Трапезникова РАН, Москва),
Л.В. РОССИХИНА, д-р техн. наук (rossihina_lv@mail.ru)
(Воронежский институт Федеральной службы исполнения наказаний, Воронеж),
А.П. ВЬЮНОВ (nvant@mail.ru)
(Центральная нормативно-техническая лаборатория Федеральной службы
исполнения наказаний, Москва),
Л.В. РОГОВАЯ (rogovayala@yandex.ru)
(Научно-исследовательский центр АО “Воронежсинтезкаучук”, Воронеж)
ЗАДАЧА ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ
КОМАНД СПЕЦИАЛИСТОВ
Рассматривается задача распределения команд специалистов, совмест-
но выполняющих некоторые работы (услуги по консультированию, оцен-
ка соответствия или несоответствия изделий, товаров или услуг необхо-
димым требованиям и т.д.). Команда, выполняющая работу, состоит из
множества специалистов различных типов (специальностей), число кото-
рых ограничено. Задача заключается в разработке плана работы команд,
при котором время выполнения всех работ минимально. Задача сведена к
задаче линейного программирования. Рассмотрены также эвристические
алгоритмы и частные случаи задачи.
Ключевые слова: команда специалистов, календарный план, набор ко-
манд, задача линейного программирования.
DOI: 10.1134/S0005231019010082
1. Введение
Задача распределения ресурсов в управлении проектами и задачи кален-
дарного планирования относятся к сложным задачам нелинейной оптимиза-
ции. Особой сложностью отличаются задачи распределения ресурсов, в кото-
рых каждая работа выполняется несколькими видами ресурсов. Для таких
задач в публикациях [1, 2] было введено понятие набора ресурсов.
Предполагается, что ресурсы Ui(t) выполняют работу i в определенном со-
отношении, т.е. Uij (t) = aij vi(t). При этом Ui(t) — набор ресурсов в момент t,
aij — параметры набора, vi(t) — мощность набора. Если vi(t) принимает всего
два значения 0 или 1, то будем говорить, что работа выполняется с фиксиро-
ванной интенсивностью.
Определение 1. Командой специалистов (далее просто команда) на-
зывается множество специалистов различного вида, необходимых для вы-
полнения работы.
116
Отметим, что команда работает как единое целое, поскольку при выполне-
нии работы специалисты взаимодействуют друг с другом. Примерами явля-
ются команды управления проектом, создаваемые на период реализации про-
екта, команда специалистов по проверке изделий на соответствие требуемым
условиям, команда специалистов, выезжающая для проверки деятельности
различных организаций, например ВУЗов, и др.
Очевидно, что команда — это набор с фиксированной интенсивностью.
В статье рассматривается задача формирования календарного плана ра-
боты команд, при котором продолжительность выполнения всех работ мини-
мальна при заданных ограничениях на число специалистов каждого вида.
2. Постановка задачи
Рассмотрим программу из n независимых работ. Каждая работа выполня-
ется командой специалистов различного типа за время τi.
Задано число специалистов j-го типа Nj , j = 1, m.
Обозначим через akj количество специалистов j-го типа, включенных в
команду k, yk(t) = 1, если команда k в момент t выполняет работу k, yk(t) = 0
в противном случае. В силу ограниченности числа специалистов каждого
типа имеют место ограничения
∑
(1)
akjyk (t) ≤ Nj
,
t ∈ [0,T], j = 1,m,
k
где T — момент завершения выполнения всех работ. Условия выполнения
всех работ имеют вид
T
∫
(2)
yk (τ) dτ = τi
,
i = 1,n.
0
Задача 1. Определить yk(t), k = 1,n, при которых время T выполнения
всех работ минимально при ограничениях (1), (2).
Это динамическая задача дискретной оптимизации, которая является
NP-трудной в силу ограничений (1). При сравнительно небольших размер-
ностях (числа работ) задачу можно свести к задаче линейного программиро-
вания. Для этого введем понятие набора команд.
Определение 2. Набором команд (далее просто набором) называется
совокупность команд Q, такая что выполняются условия:
∑
(3)
aij ≤ Nj
,
j = 1,m.
i∈Q
Заметим, что команды, входящие в набор, могут работать одновременно.
Определение 3. Максимальным набором называется набор, к которо-
му нельзя добавить ни одной команды, не нарушив ограничения (3).
117
Обозначим через R множество всех максимальных наборов N = |R| и через
xj продолжительность работы j-го набора. Считаем, что допустимы переры-
вы в выполнении работ.
Любой набор i ∈ Q будем описывать вектором bi = {bij }, где bij = 1, если
в наборе присутствует команда j, bij = 0 в противном случае.
Задача 2. Определить x = {xj}, минимизирующие
∑
(4)
T (x) =
xj
j=1
при ограничениях xi ≥ 0 и
∑
(5)
bij xj ≥ τi,
i = 1,n.
j=1
Получилась задача 2 линейного программирования.
Заметим, что число максимальных наборов может быть значительным (по-
рядка 2n). Отсюда решить большеразмерную задачу линейного программи-
рования известными методами затруднительно.
3. Частный случай
Рассмотрим частный случай задачи 2, когда максимальные наборы со-
держат все команды за исключением одной. Очевидно, что таких наборов
будет n.
Примем, что i-й набор не содержит i-й команды. В этом случае задача
принимает вид: минимизировать (2) при ограничениях xi ≥ 0, i = 1, n, и
∑
(6)
xj ≥ τi
,
i = 1,n.
j=i
∑
Поскольку θ =i xi, то перепишем (4) в виде
(7)
θ-xi ≥τi
,
i = 1,n.
Упорядочим наборы по убыванию τi, т.е. τi1 ≥ τi2 ≥ · · · ≥ τin .
Покажем, что существует оптимальное решение задачи (4), (6).
1. В случае если τin-1 + τin ≥ τi1 , то
τin-1 + τin - τi1
xi1 =
,
xij = 0, j = 2,in-2,
2
τin - τin-1 + τi1
xin-1 = τin - xi1 =
,
2
τin-1 - τin + τi1
xin-2 = τin-1 - xi1 =
,
2
118
при этом
τi1 + τin-1 + τin
θmin =
2
2. Если τin-1 + τin < τi1 , то существуют несколько оптимальных решений:
xij = 0, j = 1, n - 2,
xin-1 ≥ τin ,
xin ≥ τin-1 ,
xin-1 + xin = τi1 ,
при этом θmin = τi1 .
Исключим все наборы кроме i1, in-1 и i. Фиксируем время работы xi1
набора i1. Имеем
xin-1 ≥ τin - xi1 ,
xin ≥ τin-1 - xi1 ,
xin-1 + xin ≥ τi1 .
Пусть τin-1 + τin ≥ τi1 . Возьмем xin-1 = τin - xi1 , xin = τin-1 - xi1 , θ = xin +
+xin-1 + x1 = τin-1 + τin - xi1.
Продолжительность всех работ θ тем меньше, чем больше xi1 . Имеем
xin-1 + xin = τin + τin-1 - 2xi = τi1 .
Получаем:
τin + τin-1 + τi1
xi1 =
,
2
τin + τin-1 + τi1
xin-1 = τin - xi1 =
,
2
τin-1 - τin + τi1
xin = τin-1 - xi1 =
,
2
τin-1 + τin + τi1
θmin =
2
Пусть τin-1 + τin < τi1 . В этом случае xi1 = 0, а xin-1 + xin = τi1 . Любые
значения xin-1 , xin , удовлетворяющие условиям
xin-1 ≥ τin ,
xin ≥ τin-1 ,
xin-1 + xin ≥ τi,
определяют оптимальные решения задачи с величиной θmin = τi1 .
Заметим, что при полученном решении все задачи от i2 до in-2 также
будут выполнены.
119
Пример 1. Рассмотрим численный пример. Пусть τ1 = 10, τ2 = 8, τ3 = 4.
Поскольку τ2 + τ3 > 10, то x1 =12-102 = 1, x2 = 4 - 1 = 3, x3 = 8 - 1 = 7,
θmin = 11.
Заметим, что при любой очередности наборов одна работа выполняется с
перерывом.
4. Задача минимизации числа прерываний работ
Недостатком рассмотренного выше алгоритма являются возможные пре-
рывания в выполнении работ. Естественно, желательно минимизировать чис-
ло прерываний. Возможные планы выполнения работ определяются переста-
новками π = (i1, i2, . . . , in) наборов.
Задача 3. Определить перестановку π, при которой число прерываний
работ минимально.
Задача 3 похожа на задачу коммивояжера [3], в которой также необхо-
димо найти перестановку посещения городов. Однако имеется существенная
разница. Она состоит в том, что для данной задачи 3 не существует одной
таблицы числа прерываний между наборами. Чтобы показать это, рассмот-
рим пример 2.
Пример 2. Имеются пять работ и получено оптимальное решение из пя-
ти наборов команд. В табл. 1 приведены данные при очередности наборов
π0 = (1,2,3,4,5).
Таблица 1
τi
Lj
j i
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
xi
5
7
5
3
6
θ = 26
3
Единица в клетках табл. 1 означает, что в данном интервале i выполняется
работа j, Lj — число прерываний работы j. Определим общее число преры-
ваний работ. Работа 1, очевидно, прерывается. Работа 2 заканчивается в пер-
вом интервале, поэтому не прерывается. Работа 3 прерывается. Работа 4 не
прерывается, поскольку заканчивается во втором интервале. Наконец, рабо-
та 5 прерывается. Всего имеем три прерывания работ. Невозможность иметь
таблицу прерываний (расстояний между городами в задаче коммивояжера)
затрудняет применение методов типа метода ветвей и границ, требующих по-
лучение нижних оценок. Поэтому применим приближенный метод локальной
оптимизации решения задачи минимизации числа прерываний работ. Окрест-
ность решений в методе локальной оптимизации получается путем операций
транспозиции (перестановки соседних элементов) исходного решения.
Описание метода.
1. Выбираем начальную перестановку π0.
2. Строим окрестность Q(π0), переставляя пары соседних наборов.
120
3. Определяем лучшее решение в окрестности π∗.
4. Возвращаемся к шагу 2, т.е. строим окрестность Q (π∗) и т.д. вплоть до
получения локально-оптимального решения.
Далее можно выбрать новое начальное решение и повторить процедуру.
Пример 3. Возьмем данные примера 2. Начальная перестановка π0 =
= (1, 2, 3, 4, 5). Окрестность Q(π0) содержит четыре перестановки:
π1 = (2,1,3,4,5), π2 = (1,3,2,4,5), π3 = (1,2,4,3,5), π4 = (1,2,3,5,4).
Определяем для каждого решения число прерываний работ.
1. π1 = (2, 1, 3, 4, 5). Решение приведено в табл. 2, L(π1) = 3.
Таблица 2
j i
1
2
3
4
5
τj
Lj
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
xi
7
5
5
3
6
26
3
Действуя аналогично, получаем наилучшую перестановку в окрестности
π3 = (1,2,4,3,5), L(π3) = 1.
Строим окрестность Q(π3):
π5 = (2,1,4,3,5), π6 = (1,4,2,3,5), π7 = (1,2,4,5,3).
Наилучшие решения в окрестности π6 = (1, 4, 2, 3, 5) и π3 = (1, 2, 4, 3, 5),
L (π6) = L (π3) = 1.
Поэтому π1 является локально-оптимальным решением. Можно, конечно,
продолжить процедуру для второго лучшего в окрестности решения, но вряд
ли получим решение с меньшим L(π), поскольку наборы 1 и 5 очень далеки
друг от друга и прерывание работы 1 неизбежно.
Попробуем взять другое начальное решение, сблизив наборы 1 и 5, сохра-
нив близость наборов 3 и 5.
Возьмем, например, перестановку π8 = (3, 5, 1, 2, 4). Расчеты приведены в
табл. 3.
Таблица 3
j i
1
2
3
4
5
τj
Lj
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
Получим оптимальное решение без прерывания работ.
121
5. Задача назначения команд при запрещении прерывания работ
При запрещении прерывания работ задача назначения команд становится
сложной (NP-трудной) задачей дискретной оптимизации.
Для ее решения применяются эвристические алгоритмы, основанные на
правилах приоритета работ. Достаточно популярным является правило прио-
ритета работ, согласно которому в первую очередь вычисляются так назы-
ваемые критические работы [4].
В рассматриваемом случае критические работы — это работы с наиболь-
шей продолжительностью τi.
5.1. Описание алгоритма
1. В начальный момент времени t = 0 назначаем команды в очередности убы-
вания продолжительностей соответствующих работ до получения макси-
мального набора.
2. В момент окончания какой-либо работы назначаем команды также в оче-
редности убывания продолжительностей еще невыполненных работ.
Пример 4. Имеются пять работ и соответственно пять команд, данные
о которых приведены в табл. 4.
Таблица 4
j i
1
2
3
4
5
τj
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
2
Имеются также пять типов специалистов, причем по два специалиста каж-
дого типа.
В строках табл. 4 приведены команды для каждой работы, а в столбцах —
занятость специалистов каждого типа.
Алгоритм.
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.
Оценку снизу можно получить, получив прерывание работ.
Имеются шесть максимальных наборов команд:
x2 + x4 + x6 ≥ 4,
x3 + x5 + x6 ≥ 2.
122
Ее оптимальное решение x1 = 7, x2 = 4, x3 = 1, x4 = 0, x5 = 1, x6 = 0 с
величиной θmin = 13.
При этом одна работа выполняется с перерывом, так что полученное ре-
шение является оптимальным. Решение большого числа примеров показало,
что средняя относительная погрешность равна 5 %, причем с ростом числа
задач (команд) относительная ошибка уменьшается.
5.2. Сети с упорядоченными событиями
Рассмотрим задачу назначения команд для случая, когда существуют за-
висимости между работами. Эти зависимости будем описывать сетевым гра-
фиком, вершины которого соответствуют событиям, а дуги — работам. При-
мем, что события сетевого графика упорядочены, т.е. ti-1 ≤ ti, i = 1, r, где
ti — момент окончания i-го события.
Обозначим через RS множество работ, которые могут выполняться в
s-м интервале (интервал между s - 1 и s-м событиями, s = 1, r), Qi - множе-
ство интервалов, в которых может выполняться работа i, ys = {yis, i ∈ Rs} —
продолжительности работ, выполняемых в s-м интервале, △s(ys) — мини-
мальная длина s-го интервала как функция ys. Продолжительность проекта
равна
∑
(8)
θ (y) =
△s (ys
).
s=1
Теорема. θ(y) - выпуклая функция y.
Доказательство. Пусть y1 и y2 — два допустимых решения.
Возьмем y = ay1 + (1 - a)y2, 0 ≤ a ≤ 1. Это решение допустимо.
Обозначим через x1 оптимальное решение для y1, x2 — оптимальное ре-
шение для y2. Очевидно, что x = ax1 + (1 - a)x2 является допустимым реше-
нием для y. При этом продолжительность выполнения всех работ равна
T (x) = aΔy1 + (1 - a)Δy2.
Имеем
θ(y) ≤ T (x) = aΔy1 + (1 - a)Δy2.
Рассмотрим решение задачи для частного случая раздела 3. В этом случае
решение задачи для каждого интервала выписывается в явном виде:
⎧
⎨
yi,s,
если yi1,s > yin-1,s + yin,s,
(9)
Δs(ys) =
yi1,s + yin-1,s + yin,s
⎩
, если yi1,s ≤ yin-1,s.
2
Учитывая выпуклость целевой функции (8), задача может быть решена
методами градиентной оптимизации, в частности методом покоординатной
оптимизации.
Рассмотрим численный пример.
123
Рисунок.
Пример 5. Рассмотрим сетевой график, представленный на рисунке.
У дуг указаны номера работ. В табл. 5 приведены команды, выполняющие
работы проекта, а в табл. 6 — продолжительности работ.
Таблица 5
j i
1
2
3
τj
(1, 1)
0
1
1
-
(0, 2)
0
1
1
-
(1, 2)
1
0
1
-
(1, 3)
1
1
0
-
(2, 3)
0
1
1
-
Таблица 6
i
1
2
3
4
5
τj
24
10
8
28
8
1 шаг. Возьмем начальное решение
y11 = 12, y12 = 12, y42 = 14, y43 = 14,
продолжительность программы
12 + 8 + 14
θ1 = 12 +
+ 14 = 43.
2
2 шаг. Оптимизируем по первой работе. Оптимальное решение
y11 = 10, y12 = 14, y42 = 14, y43 = 14,
продолжительность программы
14 + 8 + 14
θ2 = 10 +
+ 14 = 42.
2
3 шаг. Оптимизируем по четвертой работе. Оптимальное решение
y11 = 10, y12 = 14, y42 = 20, y43 = 8,
124
продолжительность программы
14 + 20 + 8
θ3 = 10 +
+ 8 = 39.
2
4 шаг. Оптимизируя по первой работе, получаем то же самое решение.
Поэтому решение третьего шага является оптимальным.
В полученном решении имеется одно прерывание третьей работы. Если
прерывания запрещены, то применяем эвристический алгоритм по степени
критичности работ, т.е. начинаем в первую очередь критические работы. Кри-
тической является вторая работа.
1 шаг. В момент t1 = 0 выполняем работы (1) и (2).
2 шаг. В момент t2 = 10 начинаем выполнение критической работы (4).
3 шаг. В момент t3 = 24 начинаем выполнение работы (3).
4 шаг. В момент t4 = 32 начинаем выполнение работы (5).
Продолжительность программы T = 40.
Полученное решение является оптимальным, поскольку не существует ре-
шения без прерываний работ с продолжительностью 39.
6. Заключение
Полученные в статье результаты позволяют составлять оптимальные пла-
ны при допущении прерываний работы и достаточно хорошие планы при
запрещении прерываний работ. Представляется интересным развитие иссле-
дований в следующих направлениях:
1. Добавление числа специалистов, что приведет к росту затрат, но ускорит
выполнение работ;
2. Решение задачи по критерию минимизации максимального превышения
сроков выполнения работ или по критерию минимизации упущенной выгоды.
СПИСОК ЛИТЕРАТУРЫ
1. Бурков В.Н. Распределение ресурсов как задача оптимального быстродей-
ствия // АиТ. 1966. № 7. С. 119-129.
Burkov V.N. Resource Allocation as a Problem of Optimal Rapidity // Autom.
Remote Control. 1966. V. 27. No. 7. P. 1251-1260.
2. Burkov V.N. Problems of Optimum Distribution of Resources // Control Cybern.
1972. V. 1. No. 1-2. P. 27-41.
3. Чудров В.И. Задача о коммивояжере. М.: Изд-во “Знание”, 1969.
4. Баркалов С.А., Воропаев В.И., Секлетова Г.И. Математические основы управ-
ления проектами / Под ред. В.Н. Буркова. М.: Высш. шк., 2005.
Статья представлена к публикации членом редколлегии А.А. Лазаревым.
Поступила в редакцию 07.11.2017
После доработки 23.06.2018
Принята к публикации 08.11.2018
125
