Модифицированный алгоритм Романовского быстрого нахождения приближённого решения однородной распределительной задачи

Введение. Исследования в области классической теории расписаний (КТР) сохраняют актуальность, несмотря на большое количество научно-исследовательских работ, посвящённых этой теме [1, 2]. Для КТР характерны два типа задач, существенно отличающиеся постановкой задачи и методами решения: однородные (ОРЗ) и неоднородные (НРЗ) распределительные задачи (РЗ). Несмотря на более упрощённую форму, ОРЗ принадлежат к классу NP-полных задач с показательным ростом сложности при увеличении размерности. Одной из наиболее популярных и перспективных тем исследований является разработка эффективных приближённых алгоритмов, обладающих высокой скоростью решения РЗ.

Постановка задачи. В связи со сформулированной во введении проблемой в данной работе ставится задача создания приближённого алгоритма решения ОРЗ, который бы обладал достаточно хорошими точностными свойствами при низких требованиях к ресурсам. Общая математическая модель постановки и решения ОРЗ, предложенная в работе [3], выглядит следующим образом. Рассматривается исполнительная система (ИС), состоящая из m идентичных, параллельно работающих исполнителей Е = {elz...,em}. На вход ИС поступает множество п независимых за даний (работ) W = {и/1,...,и/я}, которые необходимо распределить между исполнителями. Изве'

стен ресурс выполнения каждого /-го задания г,, и он одинаков для любого >го исполнителя е_у. Таким образом, множеству И/сопоставлено //-множество ресурсов R = {r_lz...,r„}. Решением ОРЗ является множество D^w ={H/_lz...,kl/_m}_z в котором подмножества заданий И/ = {w_k jw_k е И/)отвечают обязательному свойству:

Vj,^ е [l,m] Qm/_; = И/; И/_;р|И4=0. 7=1 j#k

Запланированная вариантом D™ загрузка заданиями каждого исполнителя е_у оценивается ресурсом R., где Rj = ^r_k; r_k -.W_k eW_] . В результате решению ОРЗ в виде конкретного варианта

D™ сопоставляется оценочное множество Dr = {/?lz...,/?m}. Для оценки решения РЗ формируется функция Qm \_Dr~\, отражающая требования к свойствам этого решения. Например, максимальная по ресурсу загрузка одного из исполнителей

Q^m \D^rA = maxf/?, | j = l,m]

L J r V ¹              )

представляет собой оценку ресурсоёмкости решения и считается наиболее эффективной среди функционалов, а если в качестве ресурса выступает время, то выражение (1) является оценкой производительности ИС.

При любом критерии наилучшим способом конкретизации и обеспечения эффективности решения является оптимизационный подход. Например, от оценки (1) целесообразно задаться условиями минимальности значения в окончательном её решении. Это порождает минимаксный критерий (ММК) оптимизации:

<2™™ Гог1 = min maxi/?, | j = l,m).

L J E,W R l               )

Современные методы решения ОРЗ. Одним из подходов к решению поставленной задачи является разработка нового алгоритма решения РЗ на основе уже существующего метода путём его модификации с целью повышения его эффективности. Для решения ОРЗ зарубежными и российскими учёными разработано множество алгоритмов — как точных, так и приближённых. Наиболее известным и широко распространённым точным методом решения является алгоритм Романовского (АР), описанный и исследованный во многих источниках [4], [5]. Методологически АР принадлежит к классу методов «ветвей и границ», которые значительно снижают ресурс решения РЗ по сравнению с алгоритмом прямого перебора. Однако в худшем случае алгоритм осуществляет проверку всех возможных вариантов решений, что приводит к большим объёмам вычислений для нахождения оптимума. Таким образом, даже для задач невысокой размерности получение оптимального решения за приемлемое время становится невозможным. Несмотря на этот недостаток, АР обладает высокой скоростью сходимости к области решений, близких к абсолютному оптимуму, по сравнению с другими точными алгоритмами. Это обусловлено грамотным применением в АР механизма отсечения бесперспективных ветвей поиска. Поэтому, по мнению авторов, в качестве базового метода для создания эффективного приближённого алгоритма решения ОРЗ наиболее целесообразно использовать АР.

Алгоритм Романовского точного решения ОРЗ. АР заключается в последовательных попытках получения распределения заданий по исполнителям так, что загрузка каждого исполнителя не превышала максимально допустимой загрузки исполнителя z. Для выделения последующих z-задач используется итеративная формула zk = Fz(fak_vfbk_^

где fa — нижняя граница (оценка снизу) поиска, fb — верхняя граница (оценка сверху) поиска, F, — функция изменения z, причём z. е (fa,, „fb^ Л, к — шаг итерации. Если на к-м шаге итерации z-задача имеет решение, то значение верхней границы изменяется, т. е. fb_k =Q^m, иначе изменяется значение нижней границы, т. е. fa_k = z_k.

В результате последовательного рассмотрения z-задач происходит уменьшение интервала поиска оптимального распределения, которое завершается при выполнении условия fbk =fak+l

Для решения z-задач применяется метод ветвей и границ с односторонним обходом дерева вари антов. Если представить, что исполнители могут обеспечить ресурсами в количестве, равном z то у ИС должно оставаться свободное количество ресурсов slack = zm - R, где z — количество ресурса у исполнителя, т — количество исполнителей, R, — частичная загрузка исполнителей на определённом шаге алгоритма.

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

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

Модифицированный АР (МАР) быстрого нахождения приближённого решения ОРЗ. Основным недостатком АР является высокая требовательность к ресурсам при определённых условиях ОРЗ, поскольку в худшем случае он осуществляет перебор всех возможных вариантов решений, что ведёт к большим объёмам вычислений. Это присуще всем алгоритмам, построенным по схеме методов «ветвей и границ». Таким образом, для увеличения быстродействия АР наиболее целесообразно изменить алгоритм решения z-задачи, а итеративный принцип выделения z- задачи оставить без изменения. Более того, с целью получения наибольшей производительности разрабатываемого алгоритма решение z-задачи необходимо осуществлять по оригинальной стратегии АР до тех пор, пока не будет осуществлена отмена назначения текущего задания. Это обусловлено тем, что АР довольно быстро сходится к области решений, близких к абсолютному оптимуму.

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

Во-первых, необходимо назначать задания каждому >му исполнителю так, чтобы его загрузка /? была максимальна для значения z. Таким образом, необходимо формировать набор заданий И/, = {и^ | w_k е W^, где W — множество ещё не назначенных исполнителям заданий с максимальным значением загрузки среди всех возможных комбинаций заданий из множества W . Тогда как в АР исполнителю назначается первая рассмотренная комбинация заданий, удовлетворяющих условию (2). В отличие от оригинального алгоритма, в разрабатываемом алгоритме назначается такой набор заданий, который минимизирует дефицит загрузки исполнителя. По мнению авторов, этот эвристический подход позволит значительно быстрее достигать решения, удовлетворяющего z.

Во-вторых, если для исполнителя е_; не существует набора заданий и/_; = {и^ |и^ eiv}, который удовлетворяет условию (2), то алгоритм осуществляет процедуру отката не к предыдущему исполнителю e_jA, как в АР, а к первому исполнителю e_t. Эта стратегия позволит значительно сократить перебор вариантов решений за счёт максимального отсечения нижних ветвей дерева поиска. В то же время данный подход рассматривает широкий диапазон разнообразных решений, поскольку осуществляется проход по всем верхним ветвям дерева вариантов. Однако это не позволит перебрать все возможные решения, что в худшем случае может привести к пропуску искомого оптимума. Поэтому эта модификация АР является приближённым методом решения ОРЗ в отличие от исходного алгоритма.

Добавим вышеописанные изменения в оригинальный АР — и алгоритм решения z-задачи примет следующий вид.

Ш.1 Решаем z-задачу по оригинальной стратегии АР. Если на этапе выполнения алгоритма необходимо произвести отмену назначения текущего задания, т. е. не выполняется уело- вие (2), то осуществляем быстрый поиск решения z-задачи по модифицированной стратегии, т. е. переходим на Ш.2. Иначе решение z-задачи найдено, переходим на Ш.11.

Ш.2 W =W, j = 1.

Ш.З Пока j < т, иначе — на Ш.11.

Ш.4 W_tet = 0, R^ =0, где W_te5t — набор заданий, имеющих max значение загрузки V 1У, = {jv* | w_k g И/j.

Ш.5 Осуществляем перебор всех возможных и/, = lw_k I w_k е И/1.

Ш.б Если Rj=z , где Rj — загрузка И/, то И/^ = И/, R_best =R, — и переходим на Ш.8.

Ш.7 Иначе если slack > 0 и R_j. > R_best , то W_best = И/, R_best =Rj — и переходим на Ш.Б.

Ш.8 Если Wbast не пустое множество, то Wbest назначается исполнителю е^, W = W /Wk, j = j +1 — и переходим на Ш.З.

Ш.9 Иначе для исполнителя е, не найден набор заданий, удовлетворяющих условию (2). Если у =1, то просмотрены все рассматриваемые варианты решений, т. е. решение не найдено. Поэтому — выход из алгоритма.

Ш.10 В противном случае осуществляем откат к первому исполнителю elz т. е. у =1,

W -И/, w_best = 0,R_best =0, И/ = W_next, где W_next — набор заданий, который ещё не рассматривался алгоритмом, — и переходим на Ш.б.

Ш.11 Решение найдено, формируем результат.

Сравнительный анализ эффективности алгоритмов решения ОРЗ. Для сравнительного анализа эффективности алгоритмов решения ОРЗ помимо модифицированного и исходного АР также использовались метод критического пути (МКП) и эволюционно-генетический алгоритм (ЭГА). Эти алгоритмы являются приближёнными методами решения и характеризуются высокими ресурсно-точностными показателями среди алгоритмов этого класса. С целью исследования эффективности вышеуказанных алгоритмов были проведены вычислительные эксперименты при разных значениях параметров задачи. Такими параметрами являются: п — количество заданий, т — количество исполнителей, [z_lzz₂] — диапазон генерации ресурсов заданий. В качестве эволюционно-генетической модели используется модель, описанная в работе [5]. В ходе экспериментов были случайным образом сгенерированы по 100 векторов ресурсов заданий в диапазоне [z_lzz₂]. Для анализа точностных характеристик приближённых алгоритмов на малых размерностях ОРЗ используется процент нахождения оптимальных решений Р_0ПТ, а ресурсных — среднее время выполнения алгоритма £"_ф(в секундах) по 100 опытам (табл. 1).

По результатам, приведённым в таблице 1, видно, что точностные свойства МАР значительно лучше других приближённых алгоритмов. Поскольку при неблагоприятных условиях МАР находил оптимальные решения в 92 % случаев, тогда как МКП — 0 %, а ЭГА — 70 %. По ресурсным характеристикам МАР находится на уровне МКП и на порядок быстрее, чем АР и ЭГА.

Согласно исследованиям [5], для АР одним из самых неблагоприятных условий ОРЗ является случай, когда л? = 3, л = 17 и диапазон ресурсов заданий [25..30]. Поэтому проведены дополнительные вычислительные эксперименты, результаты которых подтвердили высокие точностные характеристики МАР: МАР в 100 % случаях находил оптимум, МКП — 0 %, ЭГА — 97 %.

Таблица 1

Результаты экспериментов на малых размерностях ОРЗ

m	п	k^z]	АР		МАР		МКП		ЭГА
			Ропт	tcp	Ропт	tcp	Ропт	tcp	Ропт	tcp
2	12	[50, 55]	100	<0.001	100	<0.001	94	<0.001	100	0.171
2	12	[30, 65]	100	<0.001	100	<0.001	36	<0.001	100	0.207
2	14	[50, 55]	100	0.001	100	<0.001	92	<0.001	100	0.239
2	14	[30, 65]	100	<0.001	100	<0.001	51	<0.001	100	0.196
3	13	[40, 60]	100	0.896	99	<0.001	0	<0.001	99	0.245
4	12	[50, 55]	100	0.032	1ОО	<0.001	85	<0.001	1ОО	0.221
4	12	[30, 65]	100	0.249	92	<0.001	36	<0.001	89	0.264
4	14	[50, 55]	100	25.329	1ОО	<0.001	0	<0.001	96	0.280
4	14	[30, 35]	100	3.618	99	<0.001	0	<0.001	70	0.333

Также проведены эксперименты на более высоких размерностях ОРЗ: m > 3, п > 31. Поскольку АР в поставленных экспериментах довольно часто не позволял получить решение за приемлемое время (менее 30 минут), в качестве показателя, оценивающего точностные характеристики алгоритмов, используется процент решений Р_мин, имеющих минимальную оценку по опыту (табл. 2).

Таблица 2

Результаты экспериментов на больших размерностях ОРЗ

m	n	Ezi'zz]	MAP		МКП		ЭГА
			p ' мин	tcp	p ' мин	tcp	p ' мин	tcp
3	31	[50, 55]	1OO	0.023	0	<0.001	57	0.795
3	31	[30, 65]	1OO	0.001	0	<0.001	93	0.703
3	51	[50, 55]	1OO	0.018	89	<0.001	1OO	0.609
3	51	[30, 65]	1OO	0.002	73	<0.001	81	0.823
4	41	[40, 60]	1OO	0.092	0	<0.001	31	0.802
5	31	[50, 55]	1OO	0.010	0	<0.001	26	0.848
5	31	[30, 65]	1OO	0.001	0	<0.001	90	0.548
5	51	[50, 55]	1OO	0.087	0	<0.001	1	1.535
5	51	[30, 35]	1OO	0.002	0	<0.001	0	1.139

По результатам, приведённым в таблице 2, МАР не только подтвердил, но и значительно улучшил свои точностные характеристики по сравнению с другими алгоритмами. Во всех проведённых экспериментах МАР находил решение с min оценкой по опыту, тогда как в других алгоритмах этот показатель сильно изменялся: МКП — от 0 до 89 %, ЭГА — от 0 до 100 % . Однако среднее время расчёта значительно увеличилось по сравнению с ранее проведёнными экспериментами на малых размерностях ОРЗ, а именно: с 1 мс до 92 мс. Согласно этому факту, можно сделать предположение, что МАР имеет экспоненциальный рост времени выполнения относительно размерности задачи. Таким образом, необходимы дальнейшие исследования алгоритма для проверки этой гипотезы. Хочется отметить, что ни в одном опыте количество вариантов, рассматриваемых МАР, при поиске решений не достигло полного перебора, что указывает на эффективность внесённых изменений в АР.

Выводы. МАР обладает высокими ресурсно-точностными характеристиками при решении ОРЗ невысоких размерностей (т<5,л<51) по сравнению с другими приближёнными алгоритмами. Разработанный алгоритм позволяет в большинстве случаев получать решения с более низкой оценкой по ММК, чем МКП (в среднем в 67,9 % случаев) и ЭГА (25,3 %). К тому же время выполнения МАР во всех экспериментах не превысило 100 мс, что указывает на эффективность внесённых в АР изменений. Однако быстрый рост времени работы алгоритма относительно размерности задачи требует дальнейшего исследования и улучшения МАР.