Решение задачи равномерного распределения ресурсов методом динамического программирования

DOI: 12737/21706 УДК 519.115.5

РЕШЕНИЕ ЗАДАЧИ РАВНОМЕРНОГО РАСПРЕДЕЛЕНИЯ РЕСУРСОВ МЕТОДОМ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

кандидат технических наук О.А. Коновалов1 кандидат технических наук, доцент Е.В. Коновальчук1 доктор технических наук, профессор Ю.С. Сербулов2 1 - Военный учебно-научный центр ВВС «Военно-воздушная академия им. профессора Н.Е. Жуковского и Ю.А. Гагарина», г. Воронеж, Российская Федерация 2 - ФГБОУ ВО «Воронежский государственный лесотехнический университет имени Г.Ф. Морозова», г. Воронеж, Российская Федерация

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

Ключевые слова: распределение ресурсов, сетевая модель, оптимизация, алгоритм.

THE PROBLEM SOLUTION OF THE UNIFORM DISTRIBUTION OF RESOURCES BY THE DYNAMIC

PROGRAMMING METHOD

PhD in Engineering O. A. Konovalov1 PhD in Engineering, Associate Professor E. V. Konovalchuk1 DSc in Engineering, Professor Yu. S. Serbulov 2 1 - Federal Public State Military Educational Institution of Higher Education Military Educational Scientific Center of the Air Force «Air Force Academy named after professor N.E. Zhukovsky and Yu.A. Gagarin», Voronezh, Russian Federation 2 - Federal State Budget Education Institution of Higher Education «Voronezh State University of Forestry and Technologies named after G.F. Morozov», Voronezh, Russian Federation

Abstract

One of the topical issues of the theory of projects management is the development of effective methods, models and algorithms of solving the uniform distribution problems of limited resources on networks. The article deals with the approach to solving the problem of the uniform distribution of resources with the discrete intensity of work performance. The following restrictions are introduced in order to solve this problem: the consumption of a resource at each work happens during the integer time periods; one type of a resource is consumed at all works; any work has the fixed volume demanding a resource in certain quantity

for its performance. The root-mean-square deviation of intensity of the consumed resource at the present moment from the intensity of its average consumption is given as an index of unevenness of a resource consumption in the network model. Solving the set objective in the field of the given restrictions is achieved using R.Bellman s optimality principle by solving the recurrent equation. The solution of two problems is considered for this purpose in the article: the achievements of a conditional minimum and the achievement of an absolute minimum according to the developed algorithms. At the same time the problem solution of achieving the conditional minimum is reduced to theproblem of integer quadratic programming and the problem of achieving the absolute minimum - to minimization of the utility function in the field of the set restrictions and to the search of the fixed number of variables. The considered algorithm of solving the problem of limited resources distribution on networks with the use of the dynamic programming method will allow implementing the considered approach in practice in various fields of activity and problems of the projects management.

Keywords: distribution of resources, network model, optimization, algorithm.

Пусть задана сетевая модель в виде ориентированного графа GK(MK, LK) где Мк = {т0, -частично упорядоченное множество вершин и LK={ly. I = 0,...Д-1; у=1,...,К} - множество дуг, i и у - вершины дуги (/', у) соответственно. Подмножество вершин Мк ={т0, ть...,тк} и дуг Lk={у . i = 0,...,£ - 1} будем называть подграфом Gk(Mk, Lk) графа GN(MK, LK). Каждой дуге Ц е LK поставлена в соответствие некоторая работа с фиксированным объемом, требующим для ее выполнения ресурса в количестве Ху. Примем, что на всех работах потребляется один вид ресурса.

При этом потребление ресурса Ху на каждой работе 1у происходит в течение целочисленных промежутков времени у ау<Ц<Ьу, где ау и Ьу - заданные целые числа. Интенсивность потребления qу ресурса Ху работой 1у определим как отношение qу=Ху / tу.

Для независимых операций В.Н. Бурковым доказано, что распределение ресурсов будет оптимальным в случае, если все операции выполняются с постоянной интенсивностью и если они начинаются и заканчиваются одновременно [3]. Отметим, что применительно к данной задаче интенсивность qу потребления ресурса Ху работой 1у принимает дискретные значения из отрезка [су, dу], где Су = qiJ/ Ьу, dij= qij / ау.

В качестве показателя неравномерности потребления ресурса в сетевой модели примем среднее квадратичное отклонение (СКО) интенсивности потребления ресурса в данный момент времени от интенсивности его среднего потребления [1].

Обозначим через Л£ (к = 1,2,...,К) множество тех временных значений tу (ау < tу < Ьу), г = 0,...,к-1, ] = 1,.,к, которые образуют критический путь сетевого графа из вершины т0 в вершину тк равный значению

Vsk , где Sk принимает все целочисленные значения из отрезка [0, Sk ]: Л kS =

={t,J :max (vS-+tk-ikv\ + 4k, Чк )=vlk}.

На отрезке | fJ.kSt 1, Vst \, к = 1,.. ,,K определим фронт

работ К как К ={h : V'sí <1 < Vs, + tj }•

nk

Множеству RS поставим в соответствие ин-

тенсивность фронта работ

QSt = Z % •

А средняя интенсивность потребления ресурса будет определяться как

К. =X = 2  Qk,

VSK к=1

Sk = 0,..., Sk , X =2

x„.

e NK

Тогда СКО вычисляется по формуле

K ¡n ¡к —

^ = Y ^^ Q - Di )2

' ¿-i

к=1

Vs

Минимизация (3) сводится к нахождению минимума величины

1 K

-JT (

Msk к=1

- vS- )

Для каждого фиксированного набора у^ = {¿у |еЛ ^ определим множество р всех

возможных разбиений р^ множества

K

Lk = {/„ :} = 0,..., k — 11 на подмножества ^

Р1 = { Рк = ( ^ ^ П): = 4 },

Бк = 0,..., ^ ; к = 1,...,К.

Сформулируем задачу оптимизации сетевого

плана:

< = , pl ) =

Z(ßSz - )(Ql )2 ^ mm.

При этом на функцию (6) наложим следующие ограничения (7)-(9):

к к

гк -л ^ pl - рк,

= 0,1,...,£к ; к = 1,2,...,К.

Таким образом, необходимо получить решение задачи равномерного распределения ресурсов [4, 7].

Множество Л ^ представим в виде объединения двух непересекающихся множеств вк^ и Л^ 1 ,

где соответственно

0 =К , i = 0,1,...,к — 1} и

Л— =к ™(<:2+tk—2,к—^АЧк—l,to,k—1 )=С}.

Тогда имеет место рекуррентное соотношение

(10):

Л^к = 0 и Л- Бк = 0,..., Бк; к = 1,..., К. (10) Так как каждое подмножество рк8 множества

пк тк | | ,лк—1 „„.к—1 _ г)к—1

рк есть Ч иР5к^ где Р5к—1 £ рк—, , то справед-

ливо выражение (11):

Рк = пк. иPk-1,

где

Vst =

r : Lkst и Pt:=pk - pk}

Бк = 0,..,Бк; к = 1,...,К.

Введем следующее обозначение

К, Pl)

ck = с К ) = « - С )•( Qk )2.

Bk = B(лS ,PSk )= min min ((--k ~k

Sk 1 Sk Sk> А-л^к -Рк

°к \ °к ' °к / V °к ' к—1 / \ °к

Исходя из известного принципа оптимальности Р. Беллмана [2], рекуррентное уравнение (12) дает

решение задачи (6) при ограничениях (7)-(9).

B К,Р1 ) = «n |с

"Sk ->к

+

+в (л Sk, Рк \<)_

" k = 1,..., K.

Sk = 0,..., Sk

Для подграфа Ек (Мк, Ьк) определим функцию полезности

к

К = р К, К ) = у Р - )

^Ик ,рк г=1

Sk = 0,..., Sk,

к = 1,..., К.

Рекуррентное уравнение для функции полез-

ности имеет вид:

k nk

р

_<р(гк0, Р0 )—р(гк, Рк8к)]+

+р (л ^ ч, рк ч),

= 0,..., , к = 1,..., К.

Очевидно, значения В (Л^, р ), в^тчислен-

н^1е с помощью рекуррентных уравнений (12), будут решениями уравнений (13).

Таким образом, для функций полезности справедливо соотношение

~>к 5к.

F

в

+f (л Sk , pi wSk),

" k = 1,...,K.

+

Sk = 0,..., Sk

к а к

Определение 1. Множество чисел у8 £ Л 5 и

разбиение рк^ £ Р^к , удовлетворяющие условиям

задачи (6) при ограничениях (7)-(9), будем называть (к,5к)-оптимальным планом графа Gk при

8к = 0,...,8к ; к= 1,_,К.

Решение уравнения (12) при данном значении к и Бк предлагается проводить в два этапа, соответствующих задачам достижения условного минимума (задача 1) и достижения абсолютного минимума (задача 2).

Задача 1. При фиксированном разбиении отрез-

г к п 12 к

ка [ 0, / ] точками /и8 , /и8 ,..., / определим та-

кое распределение дуг , р$ с, при котором правая часть рекуррентного уравнения (10) достигает условного минимума.

Задача 2. Выбираем такое множество ук^ , при

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

Рассмотрим задачу 1. Отметим, что для каждой дуги 1у существует конечное число значений интенсив-

д! ) (у = 1,..., и у ), с которыми эта дуга мо-

ности

жет входить в множество (2 = 1,..., к). При

этом

и)

для некоторых и значение интенсивности Цу может равняться нулю. Эти значения )

V \ г '

определяются для каждой дуги иу по отношению к рассматриваемому отрезку | ¡к-1, /и^ ^ при формирова-

тк

нии множества .

лк

Введем неизвестные у(! летворяющие условиям.

и = 1,

, иц, удов-

уу) =

0, при и Ф и;

1, иначе.

1у(и) = 1, V = 0,.,к-1.

Перепишем правую часть (12) при фиксирован-

ном множестве / в виде.

тт

г=1

и

2 (

1« еЬ 4

у(°-...+!)-уг

2

Таким образом, решение задачи 1 сводится к задаче целочисленного квадратичного программирования (15)-(16). При этом функция

*({41)=2/ /

2=1

1)

_ у . . .

„ (-(")) некоторой точке < уу >.

Полагаем, что на основании ограничений (16),

((и)\2 (и) (и) (и ) п г гг

уу )) = у(у) и Уу>  уу = 0 при и ф и .

После группировки слагаемых с одинаковыми переменными функцию * запишем в виде

иу ( "и, Л

* =2 2>?)+ 2 2

1гуе4. и=1 I (ММ^ у) г=1

О _/

у(и) + сот1.

Таким образом, минимизация функции * при ограничениях (15) сводится к перебору числа вариантов (числу переменных), равного 2

и

V '

№

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

1 этап. Принять у(") = 1, у(в) = 0 при

м Ф м.

2 этап. Выбрать значения остальных переменных у^, (И, s) Ф (V, у), ? = 1,..., из условий

1, если ? = ?, 0, если ? Ф ?.

Т

Х(< )=

При

этом

такое,

что

а

+ ^) = Г (О? + А?).

3 этап. Вычислить значение функции * при выбранных значениях переменных.

4 этап. Повторение процедуры на 1-м, 2-м и 3-м

этапах для всех и е |1, и у | и для всех таких (/',/), что

/у е 1% .

гу лк

5 этап. Выбрать тот набор переменных, при которых функция * достигает минимального значения.

Решение задачи 2 сводится к тому, что переход

от множества у',^ к множеству ук^ ^ возможен только

двумя способами [9]. Рассмотрим их ниже.

Необходимо отметить, что множество дуг Lk, на котором строится (к,5к)-оптимальный план, состоит из

Г0 7-1

двух непересекающихся множеств Ьк и Ьк, где Ь = {/ : / е и } и£={/ : / е и } . При этом ик

при ограничениях (15) достигает минимума в

Лесотехнический журнал 3/2016

)

2

)

есть множество дуг Ц, лежащих на критическом пути из т0 в тк.

Первый способ, с помощью которого осуществляется переход от множества у',^ к множеству ук^ ^,

1 к—1

заключается в том, что к значению л„ и к тем значе-

дк-1

ниям tk (г = 0,1,..., к — 2), для которых величина

¡и'8 ^ = 0,1,..., к — 2) остается неизменной при уве-

,,к—1 Г0 личении и^ 1 и которые принадлежат множеству Ьк,

прибавляется единица [9].

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

i i—1 гч

и5,1 сопровождается увеличением и5 1, и 0, если этот

переход совершается без увеличения и51.

Второй способ заключается в увеличении на единицу всех значений переменных tk ^ = 0,1,..., к — 1), которые еще не достигли предельных значений и д ля которых £ ¿к [8, 10].

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

При решении уравнений (12) выбирается тот способ перехода, который дает наименьшее значение

функции Вк . В случае совпадения этих значений

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

Так как рекуррентное уравнение (12) дает решение задачи (6) при ограничениях (7)-(9), а также позволяет получить решение уравнения (13), составим алгоритм решения уравнений (6) и (12).

Пусть (0, 50) - оптимальный план, являющийся пустым множеством для к = 0. При к = 1 получим выражение для множества значений образующих критический путь сетевого графа и рекуррентного уравнения (12) соответственно:

Л5 =Ы, р1 ={р4 =(ч), 111= А},

В11= В (л^, р!)-Ш1И с [е]^ ) =

= Ш1П t0

1з1

(е;,)22

= t01  Ш1П

131

^ ^0 7еЬ51

0 з

При этом кроме дуги 101 множество Ь5 содержит все дуги 10д ( > 1), которые выходят из начальной вершины т0.

Минимизация выражения () сводится к

следующим правилам.

Правило 1. Если выполняется условие, при котором t0 з < t00 = и1^ , то тогда необходимо увеличить

t0 до значения Ш1П

1п ( Ь0 з, ).

Правило 2. Если выполняется условие, при ко-

тором t0 з > и^ , то тогда необходимо увеличить ^

0 з

до значения Ъ,

0 з

При этом множество (1, 51) является множеством оптимальных планов, которое, в свою очередь, определяется множеством значений /01 на интервале

а01 < t01 < Ъ01 и множеством , сформированным

согласно правилам 1 и 2.

Значение функции полезности в этом случае вычисляется по формуле

Р11 =

5 = аи^ и0 = а01; и = а01 + и- и°1 = V

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

I этап. Вычислить значения и0 и .

II этап. Для 5к= 0 необходимо определить мно-

жество

Лк = ук =

у0к = К: Ж

Решая задачу 1 для у0 , получим (к, 0)-оптимальный план.

2

III этап. Предположим, что построен (к, Бк - 1)-оптимальный план.

Рассмотрим ниже порядок построения (к, £к)-оптимального плана.

1. Перейти от множества ук^ ^ к множеству у',^

двумя рассмотренными выше способами.

2. Решить задачу 1 для каждого из этих способов.

3. Выбрать тот способ перехода, которому соответствует меньшее значение функции Вк (задача 2).

4. Вычислить значение функции полезности.

5. Если значения функции Вк в п. 3 одинаковы, то необходимо выбрать способ перехода, которому соответствует большее значение функции полезности.

IV этап. Запомнить (к, 5к)-оптимальные планы

при 8к = 0,...,£к ; к=1,2,...,К.

V этап. Для £К е |0,8К ^ определить параметры (К, 5К)-оптимальных планов при обратном просмотре всех (к, 5к)-оптимальных планов (к=К, К-

Таким образом, разработанный алгоритм решения задачи равномерного распределения ресурсов на сетях найдет применение как в области информационных технологий, так и в различных производственных и бытовых сферах деятельности. При этом определенный интерес с практической точки зрения представляет решение задачи динамического распределения ресурсов на сетях с переменными объемами работ, зависящих от значений неопределённых факторов [5, 6].

Библиографический список

1. Афанасьев, М. Ю. Прикладные задачи исследования операций [Текст] : учеб. пособие / М. Ю. Афанасьев, К. А. Багриновский, В. М. Матюшок. - М. : ИНФРА-М, 2006. - 352 с.

2. Беллман, Р. Прикладные задачи динамического программирования [Текст] / Р. Беллман, С. Дрейфус ; под ред. А. А. Первозванского. - М. : Наука, 1965. - 460 с.

3. Бурков, В. Н. Модели и методы мультипроектного управления [Текст] / В. Н. Бурков, О. Ф. Квон, Л. А. Цитович. - М. : ИПУ РАН, 1997. - 62 с.

4. Косоруков, О. А. Исследование операций [Текст] : учеб. / О. А. Косоруков, А. В. Мищенко ; под общ. ред. д. э. н., проф. Н. П. Тихомирова. - М. : Экзамен, 2003. - 448 с.

5. Коновалов, О. А. Задача динамического распределения ресурсов с неопределенными факторами [Текст] / О. А. Коновалов, Ю. С. Сербулов // Информатика: проблемы, методология, технологии: материалы ХШ Междунар. науч.-метод. конф. ; 7-8 февраля 2013 г. - Воронеж, 2013. - Т. 2. - С. 171-175.

6. Сербулов, Ю. С. Управление распределением и потенциалом трудовых ресурсов организации при оптимизации структур сетевых моделей [Текст] : моногр. / Ю. С. Сербулов, О. А. Коновалов, О. В. Курипта. -Воронеж, 2014. - 191 с.

7. Лю, Б. Теория и практика неопределенного программирования [Текст] / Б. Лю ; пер. с англ. - М. : БИНОМ. Лаборатория знаний, 2005. - 416 с.

8. Herroelen, W. Resource-constrained Project Scheduling: A Survey of Recent Developments [Text] / W. Herroelen, B. D. Reyck, E. Demeulemeester // Computers and Operations Research. - 1998. - Vol. 25. - no. 4. - pp. 279-302.

9. Kall, P. Stochastic Programming [Text] // P. Kall, S. W. Wallance. - John Wiley and Sons, Chichester, 1994. - 317 p.

10. Shen, X. Mathematical Modeling and Multiobjective Evolutionary Algorithms Applied to Dynamic Flexible Job Shop Scheduling Problems [Text] / X. Shen, X. Yao // Information Sciences. - 2015. - Vol. 298. - pp. 198-224.

References

1. Afanasev M.Yu, Bagrinovskiy K.A., Matyushok V.M. Prikladnye zadachi issledovaniya operatsiy [Applied Research Problems of Operations]. Moscow, 2006, 352 p.

2. Bellman R., Dreyfus S. Prikladnye zadachi dinamicheskogo programmirovaniya Pod red. A.A. Pervozvansko-go. [Applied Problems of Dynamic Programming Edited by A.A. Pervozvansky]. Moscow, 1965, 460 p.

3. Burkov V.N., Kvon O.F., Tsitovich L.A. Modeli i metody mul'tiproektnogo upravleniya [Models and Methods

of Multiproject Management]. Moscow, 1997, 62 p.

4. Kosorukov O.A., Mishchenko A.V. Issledovanie operatsiy [Research of Operations]. Moscow, 2003, 448 p.

5. Konovalov O.A., Serbulov Yu.S. Zadacha dinamicheskogo raspredeleniya resursov s neopredelennymi faktorami [Problem of Dynamic Distribution of Resources with Uncertain Factors] Informatika: problemy, metodologiya, tekhnologii: materialy XIII Mezhdunarodnoy nauchno-metodicheskoy konferentsii, 7-8 fevralya 2013 [Informatics: Problems, Methodology, Technologies: Materials XIII of the International Scientific and Methodical Conference, On February 7-8, 2013]. Voronezh, 2013, Vol. 2, pp. 171-175.

6. Serbulov Yu.S., Konovalov O.A., Kuripta O.V. Upravlenie raspredeleniem ipotentsialom trudovykh resursov organizatsii pri optimizatsii struktur setevykh modeley [Management of Distribution and Potential of a Manpower of the Organization by Optimization of Structures of Network Models]. Voronezh, 2014, 191 p.

7. Teoriya i praktika neopredelennogo programmirovaniya [Translation from the English language edition: Theory and Practice of Uncertain Programming by B. Liu]. Moscow, 2005, 416 p.

8. Herroelen W., Reyck B. D., Demeulemeester E. Resource-constrained Project Scheduling: A Survey of Recent Developments. Computers and Operations Research, 1998, Vol. 25, no. 4, pp. 279-302.

9. Kall P., Wallance S.W. Stochastic Programming. John Wiley and Sons, Chichester, 1994, 317 p.

10. Shen X., Yao X. Mathematical Modeling and Multiobjective Evolutionary Algorithms Applied to Dynamic Flexible Job Shop Scheduling Problems. Information Sciences, 2015, vol. 298, pp. 198-224.

Сведения об авторах

Коновалов Олег Анатольевич - преподаватель 121 кафедры ФГКВОУ ВПО Военного учебно-научного центра ВВС «Военно-воздушная академия имени профессора Н.Е. Жуковского и Ю.А. Гагарина», кандидат технических наук, г. Воронеж, Российская Федерация; e-mail: Oleg-070707@yandex.ru.

Коновальчук Евгений Викторович - начальник 12 факультета ФГКВОУ ВПО Военного учебно-научного центра ВВС «Военно-воздушная академия имени профессора Н.Е. Жуковского и Ю.А. Гагарина», кандидат технических наук, доцент, г. Воронеж, Российская Федерация; e-mail: Oleg-070707@yandex.ru.

Сербулов Юрий Стефанович - профессор кафедры вычислительной техники и информационных систем ФГБОУ ВО «Воронежский государственный лесотехнический университет имени Г.Ф. Морозова», доктор технических наук, профессор, г. Воронеж, Российская Федерация; e-mail: userbulov@vglta.vrn.ru.

Information about authors

Konovalov Oleg Anatolyevich - Teacher of 121 departments of the Federal Public State Military Educational Institution of Higher Education Military Educational Scientific Center of the Air Force «Air Force Academy Professor N.E. Zhukovsky and Y.A. Gagarin», PhD in Engineering, Voronezh, Russian Federation; e-mail: Oleg-070707@yandex.ru.

Konovalchuk Evgeniy Victorovich - Chief of the 12th faculty of the Federal Public State Military Educational Institution of Higher Education Military Educational Scientific Center of the Air Force «Air Force Academy Professor N.E. Zhukovsky and Y.A. Gagarin», PhD in Engineering, Associate Professor, Voronezh, Russian Federation; e-mail: Oleg-070707@yandex.ru.

Serbulov Yury Stefanovich - Professor of department of computer facilities and information systems, Federal State Budget Education Institution of Higher Education «Voronezh State University of Forestry and Technologies named after G.F. Morozov», DSc in Engineering, Professor, Voronezh, Russian Federation; e-mail: userbulov@vglta.vrn.ru.