Метод динамического программирования в минимаксной задаче распределения заданий с равноценными исполнителями

Одним из классических способов исследования задачи дискретной оптимизации является метод динамического программирования (МДП) [1]. На сегодняшний день этот метод относительно редко используется собственно для нахождения оптимального решения. Для решения большинства, задач либо разработаны более эффективные методы математического программирования, либо достаточными оказываются многочисленные приближенные и эмпирические алгоритмы. Способом точного решения МДП остается лишь в ряде прикладных задач, обладающих сложной структурой. В этом случае создание соответствующего МДП представляет самостоятельную сложность и является существенным шагом вперед по сравнению, например, с более простыми переборными или эмпирическими алгоритмами. Особый интерес представляют случаи, когда, сложные ограничения на. задачу, доставляющие трудности в формализации задачи на. языке, например, линейного программированя, оказываются выгодны в процедуре МДП. Так, например, в обобщенной задаче курьера. [2] удается использовать условия группировки « городов ^ в « мегаполисы ^ и условия предшествования для существенного уменьшения количества, вычислений, обеспечивая высокую прикладную эффективность МДП в труднорешаемой задаче.

Несмотря на. указанные ограничения, МДП остается как удобным инструментом оценки вычислительной сложности комбинаторной задачи [3, 4], так и способом ее дальнейшего качественного исследования. Так, например, в ряде работ автора. [5, 6] близкие к МДП схемы используются для построения условий устойчивости в задачах комбинаторной оптимизации при изменении множества начальных данных. Также интерес представляют различные смешанные схемы решения сложных комбинаторных задач, в которых динамическое программирование используется ограниченным образом в комбинации с быстрыми приближенными алгоритмами [7].

Настоящая работа посвящена построению специфических схем МДП, используемых для решения минимаксной задачи распределения заданий среди конечного числа равноценных исполнителей. Насколько известно автору, впервые МДП для минимаксной распределительной задачи был изложен в работе [8] и, далее, в [2, 9]. Представленные в работе алгоритмы учитывают «симметричность» распределительной задачи с равноценными исполнителями, благодаря чему удается сократить объем вычислений по сравнению с классической схемой, а также реализовать идею «встречного» динамического программирования (впервые, по-видимому, кратко описанную в работе [10] при учете ограничений в задаче линейного целочисленного программирования). Полученные результаты представляют в первую очередь теоретический интерес, углубляя представление о структуре МДП в задаче распределения заданий.

Минимаксная постановка (или bottleneck в англоязычной литературе) относительно редко рассматривается в работах, посвященных задаче распределения заданий. Между тем, существует большое число важных приложений, связанных именно с этой задачей. В качестве одного из примеров можно привести задачу мультикоммивояжер (mTSP [И]). В минимаксной постановке этой задачи требуется разбить множество « городов ^ между коммивояжерами таким образом, чтобы длина пути самого загруженного коммивояжера была минимальна. Задачи подобного плана возникают, например, при оптимизации перемещений бригады исполнителей в агрессивной внешней среде [7, 11]. Другой областью приложения минимаксной задачи распределения заданий является формирование наиболее вероятных эволюционных деревьев с приложениями в области биологии и лингвистики.

1.    Обозначения и классическая схема

Пусть X - конечное множество распределяемых заданий, N Е N - количество исполнителей. Далее будем считать, что |X| > N. Для всякого подмножества K С X задана функция d ( K ) трудоемкости выполнения заданий этого подмножества одним исполнителем (в настоящей постановке мы считаем всех исполнителей равносильными, что, например, является весьма распространенным условием в прикладных постановках задачи мультикоммивояжера)

d : P ( X) ^ R+ ,                                     (1)

где d (0) = 0. а под P ( X ) мы традиционно понимаем лпюжество всех подмножеств X.

Для любого K С X , любого к Е 1 , N через Mk ( K ) будем обозначать совокупность всех разбиений множества K , содержащих не более к непустых подмножеств:

Mk ( K ) A {Ke P ( P ( K )) | ( |K| < к )&( J S = K )&( VA EKVB EK ( A П B = 0) V ( A = B )) }.

S ∈ K

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

Всякий элемент а Е Mk(K) будем называть распределением множества заданий K по к исполнителям; перечисляя все непустые подмножества распределения а, будем писать а = {K i,...,KiY ____ ''

При заданных к Е 1 ,N,K С X стоимостью всякого распределения а Е Mk ( K ) будем называть функцию D : Mk ( K ) ^ R+ , определяемую как максимум трудоемкости по составляющим распределение подмножествам:

Vа = {Ki,...,Ki}E Mk(K) D(а) = maxd(Kj).(2)

j e i ,i

Распределение а о E Mk ( K ) будем называть оптимальным на Mk ( K ), если справедливо

D (а о) = min D (а).(3)

a e M k ( K )

Минимаксная задача распределения заданий заключается в нахождении стоимости оптимального распределения на M n ( X ) при заданных X, N, d. Отметим, что излагаемый классический метод динамического программирования и рассматриваемые ниже его модификации, позволяют помимо расчета стоимости оптимального распределения восстановить также и само оптимальное распределение, однако этой части метода динамического программирования в настоящей работе мы не касаемся. В схеме 1 изложен классический вариант МДП для нахождения стоимости оптимального распределения заданий из множества X среди N исполнителей.

Замечание. Здесь мы не станем останавливаться на подробном рассмотрении данного классического соотношения. Отметим лишь без доказательства, что всякая величина Vi ( K ) совпадает со стоимостью оптимального распределения заданий из множества K среди i исполнителей и, в частности, величина v n ( X ) совпадает с искомой стоимостью оптимального распределения заданий множества X среди N исполнителей. Строгое доказательство этих фактов, а также корректности рекурсивной схемы 1 можно найти в работе [2]. В последующих же разделах сосредоточимся на сокращении количества итераций в схеме 1 при нахождении стоимости оптимального распределения на M n ( X ) в условиях равноценности исполнителей.

Схема 1

• 1)   VK С X V 1(K) = d(K);

• 2)    VK С X v₂(K) = k rnin k (max{d(K 1), vi(K₂)}) ;

• 3)   VK С Xvз(K)= 1 min (max{d(Ki),v2(K2)});

2.    Сокращенная схема МДП

K 1 r K 2 = K

···     ···      ···      ···

N — 1)    VK С X v_N - ₁( K ) = _k п к п _k (max {d ( K 1) , v_N _ ₂( K ₂) } );

N )     v n ( X )= min (max {d ( K 1) ,v n - i( K 2) } ) .

K 1 r K 2 = X

Выражение K 1 U K 2 = K означает разбиение множества K на два подмножества K 1 11 K 2: K 1 nK 2 = 0 , K 1 UK 2 = K , в котором порядок подмножеств K 1 , K 2 полагается существенным.

Сокращение количества итераций в схеме 1 будем проводить в три последовательных этапа. Первые два сокращения, описываемые в разделах 2.1 и 2.2, очевидно следуют из отказа от учета порядка и различий на множестве исполнителей. Эти ссокращения если и не излагались ранее теоретически, то, вероятно, были учтены при написании соответствующих алгоритмов и программ. Третье сокращение, рассматриваемое в разделе 2.3, развивает идею «встречного» динамического программирования.

• 2.1.    Отбрасывание множеств « малой » мощности

Начнем усечение схемы 1 с отказа от расчета таких значений vi ( K ), для которых справедливо |К| < i В этом случае вместо трэдовмного перебора подмножеств P ( K ) при вычислении соответствующего минимума, достаточно приравнять vi ( K ) значению vi - 1( K ), расчитанному на предыдущем шаге.

Схема 2

···

N - 1)

N )

VK с X V* ( K ) = d ( K );

∀K ⊆ X	V * ( K ) = <	min (max {d ( K 1) ,V * ( K 2) } ) , К i U K 2 = К _ V * ( K ) ,	если если	|K|> 2 |K| <  2
		, min ,. (max {d ( K 1) ,V * ( K 2) } ) ,	если	|K| >  3
∀K ⊆ X	v * ( K ) = *	К 1 U K 2= К             2
		_ V * ( K ) ,	если	|K| <  3

∀K ⊆ X

vN ( X ) =

min   (max{d(K),v*_2(K2)}) , vN- 1(K) = К1 UK2=Kv             N 2V

^VN - 2^{( K} ) ,

|K| > N - 1:

|K| 1:

,min (^{max {d (} K 1) ^,vN - 1⁽ K 2)^})

К 1 U K 2= X

учитывая, что |X| > N.

Действительно, раз i > |K| , значит, по меньшей мере, один исполнитель остался без заданий. Пусть а Е Mi ( K ) — некоторое оптималг>иое распределение на Mi ( K ). обладающее в силу сказанного в разделе 1 стоимостью vi ( K ). Отбрасывая из этого распределения работника без заданий, получим распределение в Е Mi — 1( K ), содержащее тот же самый набор непустых подмножеств, что и а , а, значит, справедливо D ( а ) = D ( в )• Распределение в оптимально на Mi - 1( K ) (если бы это было не так и существовало бы распределение в Е Mi - 1( K ): D ( в ) < D ( в )■ ^т0- учитывая. что D ( а ) = D ( в ) п добавляя к в исполнителя без заданий, можно было бы получить распределение а' Е Mi ( K ): D ( а' ) < D ( а ), что противоречит оптимальности а ), следовательно, D ( в ) = vi - 1( K ), а, значит, и Vi ( K ) = vi — 1 ( K ).

• 2.2.    Отбрасывание подмножеств « большой » мощности

Продолжим сокращение количества операций в итерационной схеме метода динамического программирования, взяв за основу теперь уже рекурсивную схему 2. Рассмотрим новую схему 3, в котором на каждом i -том шаге для всякого K С X будем искать минимум, перебирая только такие разбиения K = K 1 U K 2, в которых |K 1 | < |K|/i:

Схем а 3 1) VK с X V**(K) = d(K); min (max{d(K1),V**(K2)}), 2) К1 UK2 = К VK с X V* (K) =  |K 1 |<|K|/2 _ v * *( K), min (max{d(K1),V**(K2)}), 3) v           К1 UK2=К VK с X v3 (K) =  |к 1 |<|K|/3 _ V 2 *( k ), если |K| > 2:

если |K| <  2:

если |K| >  3:

если |K| <  3:

N — 1)

N )

VK С X

VN - 1 ( K ) =

min к 1 U K 2 = к \ к 1 |<| K | / ( N - 1)

vN — 2 ( K ) ,

(^{max {}d ⁽ K 1 ) ,vN - 2 ⁽ K 2 ) }) ,

|K| > N — 1:

|K| < N - 1:

^vN X X ) = min _v (^{max {d ( K} i ) ^,VN - 1 ^{( K} 2 ) ^}) •

K 1 U K 2 = X \ к 1 \<\ X \ /N

Действительно, если на i -м шаге мощность множества K 1 превосходит величину |K|/i, значит, в распределении заданий множества K 2 между i — 1 исполнителем (стоимости которого соответствует функция v *— 1( K 2)) присутствует хотя бы одно подмножество мощности не более |K|/i. Меняя местами это подмножество и K 1, получим идентичное исходному распределение, которое встретится при переборе разбиений K 1 U K 2 = K , при этом будет выполнено |K 1 | < |K|/i. Запишем сказанное строго.

Докажем для начала простую техническую лемму, в которой будем писать и* =1 Ki = K, обозначая разбиение множества K на k подмножеств: UL1 Ki = K 11 Vi, j G 1 , k ( i = j ) ^ ( Ki^Kj = 0) . Порядок следования подмножеств в записи суммы полагаем существенным. В отличие от записи {K 1 ,..., K*} , где перечислялись только непустые подмножества, в записи U* =1 Ki = K всякое подмножество Ki может быть пустым.

Лемма 1. Пусть задано конечное мноснсество K С X: |K| > 1, функуия d из (1) и величина k G N: |K| > k. тогда min uk=1 Ki=к \K 1 \<\к\/k v

(max {d ( Ki ) } ) =

\ i E 1 ,k           /

“^^

( )

✓

min к i с к \ K 1 \<\ K \ /k ^

( max d ( K 1 ) ,    min    (max {d ( Ki ) } )     .

U k =2 K i = к \ к 1 i E 2 ,*

■^г"— ( * * )

✓

Доказательство. Пусть Uk =1 K ⁰ = K — разбиение K, доставляют,ее минимум в ( * ), причем |K ⁰ | < |K|/k. тогда ( * ) = max _iE 1*{d ( K ⁰) } = max {d ( K 0 ) , max _iE 2^ {d ( K ⁰) }} >  ( ** ) . С другой стороны, если Uk =1 L ⁰ = K — разбиение K, доставляют, ее минимум в ( ** ), где в новь |L ⁰ | < |K|/k, тогда ( ** ) = max {d ( L 1 ) , max _iE 2 *{d ( L ⁰) }} = max _iE у*{d ( L ⁰) } >  ( * ) . Из приведенных рассуждений следует, что ( * ) = ( ** ). □

Предложение 1. ( Vk G 1 , N — 1 , VK С X v * ( K ) = v ** ( K )) & ( vN ( X ) = vN * ( X )).

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

Б.И. k = 1 . VK С X v* * ( K ) = d ( K ) = v * ( K ).                _______

Ш.И. Пусть для некоторого k G 1 , N — 1 справедливо: Vi G 1 , k — 1 , VK С X v * ( K ) = v ** ( K ). Покажем, что VK С X v* ( K ) = v ** ( K ). Рассмотрим произвольное подмножество K С X. Ес ли |K | < k, то по индукции и в силу схем 2 и 3 имеем v* ( K ) = v* - 1 ( K ) ^П=' v* — 1 ( K ) = v ** ( K ) . Пусть |K| > k. Величина v* ( K ) (будучи равна согласно рассуждениям раздела 2.1 величине v* ( K )) соответствует стоимости оптимального распределения заданий множества K среди k работников, а значит из определений (2), (3)

v* (K) =  min uk=1 Ki=к

I max {d ( Ki ) } I .

V i E 1 ,*

Хотя бы одно подмножество из всякого разбиения и*=1 Ki = K должно иметь мощность, не превосходящую |K|/k, поскольку иначе и*=1 |Kj| > |K|. Правая часть (4) не зависит от порядка следования подмножеств в разбиении, а значит без ограничения общности подмножество, содержащее \K\/k элементов будем обозначать как K1, иными словами min

□ = =1 K i = K

( max {d ( Ki ) } ^ =

\ i E 1 ,k           /

min    max {d ( Ki ) } .

□ L1 K i = k V i c 1 ,k        /

\ K 1 \<\ K | /k

Согласно лемме min

□ = =1 K i = к \ K 1 \<\ к \ /k

(max {d ( Ki ) } ^ = \ i E 1 ,k

min

K 1 E K \ K 1 \<\ K \ /k

max

d ( K 1 ) ,

min    (max {d ( Ki ) } )

□ = =2 K i = K \ K 1 i E 2 ,k

li

Величина vk-1(K \ K1) совпадает co стоимостью оптимального распределения заданий мно жества K \ K1 между k — 1 исполнителем, а значит min

K 1 E K \ K 1 \<\ K \ /k

max

d ( K 1 ) ,

min    (max {d ( Ki ) } )

□ = =2 K i = K \ K 1 i E 2 ,k

=

min

K 1 E K \ K 1 \<\ K \ /k

(^max { d ^{( K} 1 ) , v k- 1 ^{( K} \ ^K 1 )})

По индукции имеем min

K 1 E K \ K 1 \<\ K \ /k

(max { d ⁽ K 1 ) ,vk - 1 ⁽ K \ K 1 )})

min

K 1 E K \ K 1 \<\ K \ /k

(^max { d ^{( K} 1 ) ^,vk - 1 ^{( K} \^K 1 )})

и, наконец, из схемы 3

min (max { d ⁽ К 1 ) , v *- 1 ⁽ К \ К 1 )}) = v*_k * ⁽ К ) .

K 1 E K

\ K 1 \<\ K \ /k

Вторая часть утверждения vN ( X ) = vN * ( X ) доказывается аналогично при k = N,K =

X.                                                                           □

• 2.3.    Сокращение числа « слоев »

Покажем, наконец, что в схеме 3 вычисления достаточно проводить лишь «до середины»: для i < V = [( N — 1) / 2] + 1. Запишем суженную таким образом схему 4.

С х е

м

а 4

VK C X

VK с X

v k * ( K ) = d ( K )

^min,^{(max {d ( K} 1) ^,v ** ^{( K} 2) } ) , ec.ли \K \ >  2;

** ( TZX      K1 ^K2= K v2 (K) =   \K 1 \<\K\/2

v Г ( K ) ,

если \K\ <  2;

. . .

V )

VK с X

VK C X

v 3 * ( K ) =

vV * ( K ) =

min K 1 □ K 2 = K \ K 1 \<\ K \ / 3

v ** ( K ) ,

^{(max {}d ⁽ K 1 ) ,v ** ⁽ K2)^} ) ,

min K 1 □ K 2 = K \ K 1 \<\ K \ /V

если \K\ >  3;

если \K\ <  3;

(^{max {d ( K} 1 ) ^,vV - 1 ^{( K} 2 ) ^}) ,

если \K\ > V;

vV *- 1 ( K ) ,

если \K\ < V.

Дополним схему 4 последним шагом vN* (X) =   min max {vV* (К1) ,v**-v (К 2)}.                     (5)

K 1 U K 2 = X

В силу того, что N — V < V, оба выражения vV * ( К 1) и v* _ v ( К 2) конструктивно определены из итерационной схемы 4 для всех К 1 , К 2 С X.

Предложение 2. Величина v*** ( X ) выраснсает стоимость оптимального распределения на M* ( X ).

Доказательство. Рассмотрим произвольное распределение а £ M* ( X ): L* ₌₁ Li = X. Разобьем распределение а на две части а 1: ui =i Li = X 1 и а 2: L* v +1 Li = X 2, г де X 1 = U V =1 Li 11 X 2 = U * v +1 Li. В таких обозначениях очевидно X 1 L X 2 = X, а 1 £ M v ( X 1) , а 2 £ M* - v ( X 2) , и. как следствие, учитывая определение (2). имеем D ( а ) = max {D ( а 1) , D ( а 2) }.

Учитывая, что а 1 £ M v ( X 1), а 2 £ M* - V ( X 2), а согласно предложению 1 величины v ** ( X 1) и v* _ v ( X 2) совпадают со стоимостями оптимальных распределений на M v ( X 1) и M n - V ( X ₂) соответственно, получаем неравенства D ( а 1) > vV * ( X 1) и D ( а ₂) > v* _ v ( X 2), а значит имеем

D ( а ) = max {D ( а 1) , D ( а 2) } >  max {vV * ( X 1) , v* - v ( X 2) } >

।min max{vv*(к1) ,vN*-v(К2)} = v***(X), K1 UK 2= X справедливое для всякого а £ M* (X).

Итак, стоимость всякого а £ M* ( X ) не менее v* * ( X ). Покажем, что найдется а о £ M* ( X ): D ( а 0) = v* * ( X ) . Пусть на множествах К ⁰ 11 К ⁰ = X \ Ку достигается минимум правой части выражения (5). Пусть далее а ⁰ — оптимальное распределение на M v ( К ⁰): Li =1 L 1 = К 0. а а ⁰ — оптимальное распределение на M* - V ( К ⁰): L* - ^V L 2 = К ⁰. Учитывая, что К ⁰ L К ⁰ = X, составим распределение а 0 £ M* ( X ): ( L^V ₌₁ L ¹) Ц( L* - ^VL 2) = К ⁰ L К ⁰ = X. По построению

D ( а 0) = max {D ( а ⁰) , D ( а 2) } = max {vV * ( К ⁰) ,v* *- v ( К ⁰) } =

_।min max ^{vV * ^{( К} 1) ^,v* - V ^{( К} 2 ) ^} = ^vN * ^{( X} ) .

K 1 U K 2 = X

z

3.    Сравнение числа операций

Проведем численное сравнение количества « единичных: операций » , требующихся для расчета стоимости оптимального распределения заданий из множества X среди N исполнителей с использованием схем 1 и 4. Единичной операцией будем считать взятие максимума из двух чисел. Именно такие операции составляют основу вычислений в схемах 1 и 4 на всех шагах, следующих за первым. Число иных операций в обеих схемах будем считать пропорциональным числу единичных операций.

Пусть далее |X| = п. На каждом из шагов 2 ,..., N — 1 схемы 1 перебираются всевозможные подмножества К С X. Для всякого i £ 0 , п существует СП подмножеств К мощности i. Для всякого подмножества К : |К| = i сутнествует 2 i ра:?>биепий вида К 1 L К 2 = К. каждому из которых соответствует одна единичная операция. Таким образом, суммарное число единичных операций на шагах 2 ,... ,N — 1 схемы 1 можно записать в виде

n

• ( N — 2) £ 2 iCn.

i =0

Таблица

Сравнение числа операций в различных вариантах МДП

n	Классический	Встречный	Отношение
10	178171	47316	3,765
12	1598419	412110	3,878
14	14365291	3588409	4,003
16	129205699	31307602	4,126
18	1162523611	273844200	4,245
20	10461401779	2401589556	4,356
22	94147373131	21113768572	4,459
24	847305386659	186039820510	4,554
26	7625664593851	1642544688531	4,642
28	68630645800339	14527969382181	4,724
30	617674470025771	128701822410531	4,799
100	1,546е+048	2,721е+047	5,681
250	5,720е+119	9,828е+118	5,820

На последнем шаге производится перебор 2 n подмножеств множества X, каждому из которых вновв соответствует одна единичная операция. Итоговое количество единичных операций в схеме 1 можно выразить формулой

2 n + ( N — 2) ^Е 2 iCn.

i =0

В схеме 2 на всяком шаге j Е 2 ,..., N — 1 исключается расчет значений функции Vj ( K ) в случае, когда количество распределяемых заданий \К | превосходит числ о исполнителей j

N -1 ( nх

2 n +

ЕЕ 2 с }• j=2 1 i=j

Далее, в схеме 3, исключая на j -том шаге из рассмотрения все разбиения K i U K 2 = K , где \К 1 | > \K\/j. имеем

[n/N]        N-1 z n /[

Е cn + Е ЕД -БсП}• k =0        j =2 i = j k =0

Наконец, сужая количество насчитываемых слоев, в схеме 4 имеем:

[( N - 1) / 2]+1 n           [ i/j ]

• 2 n + Е ЕД - Е Д •

  
  

j =2        i = j       k =0

В таблице п как и прежде обозначает количество распределяемых заданий; количество исполнителей N принимается равным 5; в колонке « классический » представлено значение функции (6); в колонке « встречный » - значение функции (7); в колонке « отношение » приводится отношение величины (6) к величине (7) для соответствующего значения п.

Работа проводилась при финансовой поддержке РФФИ (гранты 10-08-004 84-а, 10-01-96020-р-урал-а) и программы Президиума УрО РАН (проект 09-П-1-10Ц).