Автоматика и телемеханика, № 2, 2019

Интеллектуальные системы управления,

анализ данных

(Технологический институт Блекинге, Карлскрона, Швеция),

Ю.Н. СОТСКОВ, д-р физ.-мат. наук (sotskov@newman.bas-net.by)

(Объединенный институт проблем информатики НАН Беларуси, Минск),

Ф. ВЕРНЕР, д-р наук (frank.werner@mathematik.uni-magdeburg.de)

(Университет Отто фон Герике, Магдебург, Германия),

О.С. ЗАТЮПО (ztp-oksana100@ya.ru)

(СЗАО “Серволюкс”, Могилев, Беларусь)

ЭВРИСТИЧЕСКИЕ АЛГОРИТМЫ ДЛЯ МАКСИМИЗАЦИИ ДОХОДА

И КОЛИЧЕСТВА ТРЕБОВАНИЙ, ОБСЛУЖИВАЕМЫХ

НА ПАРАЛЛЕЛЬНЫХ ПРИБОРАХ

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

борах. Для каждого требования известно время готовности к обслужива-

нию и установлен срок, не позднее которого требование должно быть об-

служено. Если обслуживание требования завершается к установленному

сроку, то начисляется определенная прибыль. В противном случае требо-

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

начисляется. Рассматривается критерий максимизации взвешенной сум-

мы начисленной прибыли и количества требований, обслуженных в срок.

Исследованы свойства целевой функции, которые позволяют строить оп-

тимальные расписания обслуживания требований. Разработаны три эв-

ристических алгоритма: алгоритм имитации отжига, поиск с запретами

и генетический алгоритм. Разработанные программы протестированы на

задачах средней размерности (50 требований и 5 приборов) и на задачах

большой размерности (500 требований и 50 приборов). Даны рекоменда-

ции по использованию разработанных алгоритмов и полученных резуль-

татов в календарном планировании производства.

Ключевые слова: оптимальное расписание, параллельные приборы, мак-

симизация прибыли, генетический алгоритм, алгоритм имитации отжига,

поиск с запретами.

DOI: 10.1134/S0005231019020089

1. Введение

Планирование производства включает оптимизацию использования огра-

ниченных ресурсов (приборов) для обслуживания заданного множества тре-

бований. Оптимальное расписание является важным фактором эффективно-

сти производства, поскольку оптимальное расписание обеспечивает сокраще-

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

ков на продукцию предприятия, своевременное снабжение производственного

125

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

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

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

щих изделий и материалов и в итоге повысить эффективность использования

имеющихся ресурсов и капитала, а также сократить простои оборудования.

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

ния оптимальное расписание может быть построено с помощью универсаль-

ных точных методов оптимизации, таких как метод ветвей и границ, метод

динамического программирования, методы математического программирова-

ния. Однако точные методы, как правило, не применимы для задач, которые

возникают при планировании процессов для реальных промышленных пред-

приятий, поскольку практические задачи обычно имеют большую размер-

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

ются NP-трудными даже для двух или трех приборов [1]. Поэтому для реше-

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

используют эвристические алгоритмы.

В теории расписаний рассматривается задача составления оптимального

расписания, в которой каждое требование из заданного множества необхо-

димо обслужить на одном из заданных параллельных приборов. Параллель-

ные приборы могут быть либо идентичными, либо однотипными (однотип-

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

первая задача обозначается как I//Φ, где Φ — целевая функция, а вторая,

более сложная задача — как Q//Φ. Задача I//Φ является NP-трудной да-

же для двух приборов при критерии минимизации общего времени работы

обслуживающей системы Φ = max{C₁, . . . , C_n}, где C_i — время завершения

обслуживания требования J_i [2].

В данной статье рассматривается задача максимизации как дохода от об-

служивания требований, так и количества требований, обслуженных в срок

на параллельных неидентичных приборах. В разделе 2 приведен обзор науч-

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

приборах. В разделе 3 представлено описание исследуемой задачи и приве-

дены результаты исследования целевой функции с экстремальными значе-

ниями. Три эвристических алгоритма описаны в разделе 4. Результаты вы-

числительных экспериментов с анализом разработанных алгоритмов при-

ведены в разделе 5. Возможности применения полученных результатов на

практике описаны в разделе 6. Заключительные замечания содержатся в

разделе 7.

2. Обзор литературы

В [3] разработан метод нечеткого математического программирования для

минимизации общего времени работы обслуживающей системы при выпол-

нении множества операций на параллельных идентичных приборах при усло-

вии, что точные числовые данные задачи не известны при составлении распи-

сания. Та же задача с детерминированными (точными) числовыми данными

была исследована в [4]. В [5] для детерминированной обслуживающей си-

стемы разработан алгоритм “колонии муравьев” для планирования операций

на параллельных приборах. Статья [6] содержит результаты выбора правил

126

диспетчеризации при различных критериях оптимальности (при максимиза-

ции быстродействия, минимизации суммарной продолжительности обслужи-

вания требований и минимизации суммарных простоев приборов).

Задача планирования операций становится более сложной при рассмотре-

нии неидентичных параллельных приборов. В [7] для такой задачи был пред-

ложен оператор обмена в целях адаптации генетического алгоритма при пла-

нировании операций на неидентичных параллельных приборах. Результаты

вычислений сравнивались с результатами, полученными с помощью прави-

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

(LPT). Для сведения к минимуму взвешенной суммы наименьшей длительно-

сти и наибольшей длительности обслуживания требований на неидентичных

параллельных приборах в [4] был предложен метаэвристический алгоритм.

В [8] представлены результаты одновременного выбора операции и назначе-

ния ее на параллельные однотипные приборы. Для такой задачи разработан

алгоритм имитации отжига. Результаты приближенных вычислений сравни-

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

В [9] генетический алгоритм был использован в имитационной модели,

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

вались с результатами, полученными при использовании правила диспетчери-

зации LPT. В [10] разработаны модели и предложены упрощения для неиден-

тичных параллельных приборов при минимизации суммарной взвешенной

продолжительности выполнения операций. Задача максимизации быстродей-

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

ленного линейного программирования в [11]. Авторы статьи предложили ге-

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

случайных ключей. Статья [12] посвящена использованию неидентичных па-

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

тельности выполнения операций. В [13] исследована задача минимизации

суммы раннего времени выполнения операций относительно заданных ди-

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

заранее упорядочены, чтобы уменьшить размерность пространства допусти-

мых решений. Авторы предложили эвристический алгоритм для решения та-

кой задачи. Задача с параллельными неидентичными приборами исследована

в [14], где были разработаны шесть алгоритмов, основанных на поиске с за-

претами. Было исследовано влияние различных исходных решений на свой-

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

алгоритма имитации отжига в [15], где было показано, что алгоритм имита-

ции отжига более эффективен для обеспечения наилучшего использования

приборов. Для задачи планирования с параллельными приборами с перена-

ладками, зависящими от последовательности выполнения операций, и задан-

ными временами готовности требований к обслуживанию, в [16] предложен

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

времени выполнения операций относительно заданных директивных сроков

и запаздывания выполнения операций. В [17] предложен алгоритм поиска

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

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

поиска с запретами эффективнее генетического алгоритма, предложенного

127

в [16]. Многоцелевая модель планирования работы параллельных приборов

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

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

в [18] (параллельные приборы имели различные скорости выполнения опе-

раций). Задавались длительности выполнения операций и сроки их завер-

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

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

зависимости от начала их обработки и различных характеристик обслужи-

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

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

лочисленного линейного программирования. В [19] рассматривалась задача

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

их на параллельных однотипных приборах. Требовалось учитывать время на-

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

выполнению операций другого семейства. Было предложено несколько эври-

стических алгоритмов, оценена их эффективность путем сопоставления по-

лученных результатов с нижней границей оптимального значения целевой

функции и решениями, полученными с помощью точного алгоритма.

Другая важная область исследований связана с планированием работы па-

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

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

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

и получить от этого максимальной доход. Превышение установленного сро-

ка выполнения операции влечет за собой штраф, величина которого зависит

от длительности задержки в завершении операции. В [20] предложен алго-

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

Эффективность алгоритма сравнивалась в вычислительных экспериментах с

результатами, полученными с помощью алгоритма построения расписания

согласно определенному списку операций (list scheduling) и метода ветвей и

границ. Статья [21] посвящена задаче планирования выполнения параллель-

ных операций на суперкомпьютерах с целью максимизации дохода. Авто-

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

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

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

В [22] рассматривалась задача выбора и оценки фильмов для мультиплек-

са с целью максимизации суммарного дохода за фиксированный период вре-

мени (горизонт планирования). Были известны времена выпуска фильмов,

которые можно выбирать для проката. Если фильм выбран для его оценки,

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

может увеличиваться. Авторы [22] исследовали два основных принципа со-

ставления расписаний: допустимость прерываний с последующим возобнов-

лением обслуживания требования (preempt-resume) и запрещение таких пре-

рываний (non-preempt). Было показано, что задача оптимизации с принципом

preempt-resume является NP-трудной, в то время как задача оптимизации с

принципом non-preempt полиномиально разрешима. Для решения обеих за-

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

полученный в результате применения принципа preempt-resume, может быть

128

значительно больше дохода при применении принципа non-preempt. В [23]

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

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

глашения об уровне обслуживания, которое играет важную роль в облачных

вычислениях для подключения поставщиков услуг и клиентов. Авторы [23]

формализовали задачу выделения ресурсов с использованием теории массо-

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

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

доступные ресурсы. Эксперименты показали, что разработанные алгоритмы

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

3. Постановка задачи и обозначения

Рассматриваемая задача обозначается как Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)|, ес-

ли использовать трехпозиционное обозначение α/β/γ, введенное в [2]. В этом

обозначении поле α характеризует тип системы обслуживания, поле β — ис-

ходные данные и параметры, а поле γ — целевую функцию.

3.1. Постановка задачи

Задача Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)| формулируется следующим обра-

зом. Имеется множество m параллельных однотипных приборов M =

= {M₁, . . . , M_m}, на которых необходимо обслужить заданное множество

J = {J₁,...,J_n} требований. Каждое требование J_i ∈ J может быть обслу-

жено на любом приборе из множества M без прерываний. Скорости приборов

M_k ∈ M могут быть различными.

Для каждого требования J_i ∈ J задано время готовности к выполнению

r_i ≥ 0, а также время d_i > r_i, к которому его выполнение должно быть за-

вершено. Если требование J_i ∈ J выполняется целиком в период времени,

принадлежащий заданному отрезку [r_i, d_i], то получается прибыль b_i > 0.

В противном случае, прибыль b_i не получается и требование J_i из расписа-_∑

ния удаляется. Пусть w₁ ≥ 0 обозначает вес полученного доходаJi∈J (S)^bi

(суммарный доход за выполнение требований при расписании S), а w₂ ≥ 0 —

вес количества |J (S)| требований J_i ∈ J (S) ⊆ J , выполненных при расписа-

нии S в периоды времени, принадлежащие соответствующим отрезкам [r_i, d_i].

Будем предполагать, что w₁ + w₂ = 1.

В задаче Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)| требуется найти такое расписание S

выполнения требований из множества J на приборах из множества M, для_∑

которого будет максимальной сумма w1Ji∈J (S)^bi+w2|J(S)|взвешенной

прибыли от выполнения множества J (S) требований и взвешенного коли-

чества |J (S)| требований, выполненных при расписании S в интервалах вре-

мени [r_i, d_i], J_i ∈ J .

Приборы из множества M однотипны и параллельны, иными словами,

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

же требования J_i ∈ J . Пусть прибор M_k ∈ M имеет скорость v_k > 0, тогда

время p_ik, необходимое для выполнения требования J_i на приборе M_k, опре-

деляется следующим равенством: p_ik =piv_k ,гдеpi>0обозначаетнормальное

время, необходимое для выполнения требования J_i ∈ J . Пусть требование J_i

129

выполняется на приборе M_k ∈ M при расписании S. Выполнение требова-

ния J_i на приборе M_k может быть начато после времени r_i готовности требо-

вания к обслуживанию, а также после времени завершения выполнения c_lk(S)

предыдущего требования J_l (если оно есть в расписании S), которое выпол-

нялось на том же приборе M_k при расписании S. Таким образом, время нача-

ла s_ik(S) выполнения требования J_i на приборе M_k при расписании S может

быть рассчитано следующим образом: s_ik(S) = max{r_i, c_lk(S)}.

Поскольку прерывания при выполнении требований не допускаются, вре-

мя c_ik(S) завершения обслуживания требования J_i на приборе M_k при распи-

сании S может быть вычислено как сумма времени начала s_ik и длительности

выполнения p_ik требования J_i на приборе M_k, т.е. c_ik(S) = s_ik(S) + p_ik. Вклю-

чение J_i ∈ J (S) имеет место, если r_i ≤ s_ik(S) < s_ik(S) + p_ik = c_ik(S) ≤ d_i._∑

Первое слагаемое ц∑евой функции Φ(S) := w1Ji∈J (S)bi+w2|J(S)|—это

взвешенная сумма

b_i(S) прибыли, полученной при выполнении требова-

∑

ний из множества J в установленный срок:

b_i(S) =Ji∈J (S)^bi.Второе

слагаемое целевой функции Φ(S) связано с удовлетворенностью клиентов в

результате увеличения количества |J (S)| требований J (S), начатых и завер-

шенных в установленный срок при расписании S.

Если w₁ = 1, то w₂ = 0, и задача Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)| превращается

в известную задачу Q/r_i, d_i/

^∑b_i максимизации прибыли [20, 21].

3.2. Экстремальные значения целевой функции Φ(S) = w₁

^∑b_i + w₂|J(S)|

Максимально возможное значение целевой функции Φ(S) достигается в

случае, когда для задачи Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)| существует расписа-

∑

ние S, для которого оба слагаемых w1Ji∈J (S)^biиw2|J(S)|целевойфунк-

ции Φ(S) достигают своих максимально возможных значений, а именно:_∑∑

w₁

b_i = w₁

b_i и w₂|J (S)| = w₂n.

J_i∈J (S)

J_i∈J

Теорема 1. Для задачи Q/r_i,d_i/w₁

^∑b_i + w₂|J(S)| существует распи-

сание S, для которого целевая функция Φ(S) достигает своего максимально

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

J (S) = J .

Доказательство. Достаточность. Пусть для задачи Q/r_i,d_i/w₁

^∑b_i+

+ w₂|J (S)| существует расписание S, для которого выполняется равенство

J (S) = J . Тогда получаем следующее равенство:

∑

(1)

w₁

b_i + w₂|J (S)| = w₁

b_i + w₂

J_i∈J (S)

J_i∈J

∑

Очевидно, что значение w1Ji∈J^bi+w2nвправойчастиравенства(1)

равно максимально возможному значению целевой функции Φ(S). Таким об-

разом, расписание S, указанное в равенстве (1), обеспечивает максимально

возможное значение целевой функции Φ(S). Отметим, что в этом случае рас-

писание S является оптимальным для задачи Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)|.

Необходимость. Пусть для задачи Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)| существует

расписание S, для которого целевая функция Φ(S) достигает своего макси-

мально возможного значения, т.е. выполняется равенство (1).

130

От противного предположим, что J (S) = J . Тогда существует требова-

ние J_k ∈ J , которое не может быть обслужено в течение интервала времени

[r_k, d_k] при расписании S, т.е. множество J (S) не содержит требования J_k:

J_k ∈ J (S). Поскольку w₁ ≥ 0, w₂ ≥ 0 и выполняется равенство w₁ + w₂ = 1,

то по крайней мере один вес w₁ или w₂ не равен нулю в целевой функции_∑

Φ(S) = w1Ji∈J (S)^bi+w2|J(S)|.

Если w₁ > 0, то, используя неравенство b_k > 0, получаем соотношение

∑

w₁

b_i ≤ w₁

b_i - w₁b_k < w₁

b_i.

J_i∈J (S)

J_i∈J

Если же w₂ > 0, то получаем неравенства w₂|J (S)| ≤ w₂(|J | - 1) < w₂n.

Таким образом, в обоих возможных случаях получаем противоречие, состоя-

щее в том, что равенство (1) не выполняется для расписания S. Следователь-

но, предположение J (S) = J не верно, что и требовалось доказать.

В приведенном доказательстве теоремы 1 получено следующее утвержде-

ние.

Следствие 1. Если выполняется равенство J(S) = J, то расписание S

является оптимальным для задачи Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)|.

Следующая теорема характеризует другое экстремальное значение целе-

вой функции Φ(S), а именно, минимально возможное значение функции Φ(S).

Теорема 2. Оптимальное значение целевой функции Φ(S) равно нулю

для задачи Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)| тогда и только тогда, когда не суще-

ствует требования J_i ∈ J , которое может быть полностью обслужено в

течение заданного интервала времени [r_i,d_i].

Доказательство. Достаточность. Предположим, что не существует

требования J_i ∈ J , которое может быть обслужено в течение заданного ин-

тервала времени [r_i, d_i]. Из этого следует, что должно выполняться равенство

J (S) = ∅ для любого допустимого расписания S. Следовательно, оптималь-

ное значение целевой функции Φ(S) равно нулю (т.е. минимально возможно-

му значению целевой функции Φ(S)):

∑

Φ(S) = w₁

b_i + w₂|J (S)| = w₁0 + w₂0 = 0.

J_i∈J (S)

Необходимость. Пусть оптимальное значение целевой функции Φ(S) рав-

но нулю для рассматриваемой задачи Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)|. От против-

ного предположим, что существует требование J_i ∈ J , которое может быть

полностью обслужено в течение интервала времени [r_i, d_i]. Следовательно,

существует расписание S, для которого требование J_i ∈ J обслуживается

в течение интервала времени [r_i, d_i]. Далее оценим значение целевой функ-

ции Φ(S) для такого расписания S. Поскольку w₁ ≥ 0, w₂ ≥ 0 и равенство

w₁ + w₂ = 1 выполняется, то по крайней мере один вес w₁ или w₂ не равен_∑

нулю для целевой функции Φ(S) = w1Ji∈J (S)^bi+w2|J(S)|.

Если w₁ > 0, то, используя неравенство b_i > 0, получаем Φ(S) ≥∑

≥w₁

b_i ≥ w₁b_i > 0. Если же w₂ > 0, то получаем Φ(S) ≥ w₂|J (S)| ≥

J_i∈J (S)

131

≥ w₂ > 0. Таким образом, в обоих случаях есть противоречие тому, что оп-

тимальная величина целевой функции Φ(S) равна нулю. Это означает, что

предположение о том, что существует требование J_i ∈ J , которое может быть

полностью обслужено в течение интервала времени [r_i, d_i], опровергнуто, что

и требовалось доказать.

Покажем, что проверка условия теоремы 2 может быть реализована за вре-

мя O(n) при естественном предположении о том, что n ≥ m. Действительно,

для проверки условия теоремы 2 достаточно выбрать прибор M_z с максималь-

ной скоростью v_z = max{v_k | M_k ∈ M} и для требований J_i из множества J

проверить неравенство

p_i

(2)

≤d_i -r_i.

v_z

Если хотя бы для одного требования из множества J неравен-

ство (2) выполняется, то для задачи Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)| существу-

ет расписание S, для которого Φ(S) > 0. В противном случае равенство

Φ(S) = 0 выполняется для любого расписания S, существующего для задачи

Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)|.

4. Эвристические алгоритмы для задачи

Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)|

В этом разделе описываются алгоритмы имитации отжига, поиска с

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

Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)|. Применение этих алгоритмов для решения за-

дачи Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)| может начинаться с любого эвристического

решения задачи (допустимого расписания). Исследование различных аспек-

тов разработанных алгоритмов (таких как число итераций, число соседей,

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

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

Φ(S) = w₁

^∑b_i + w₂|J(S)| для задач средней размерности.

4.1. Генетический алгоритм

Генетический алгоритм является эволюционным алгоритмом, представ-

ляющим решение (индивидуум) задачи в виде кода, называемого хромосо-

мой или геномом. Аналогично процессу эволюции в живой природе хромосо-

мы скрещиваются и мутируют для создания новых индивидуумов в каждом

поколении. Новые хромосомы создаются путем присоединения сегментов, вы-

бранных поочередно от каждой из хромосом двух родителей, которые име-

ют фиксированную длину. При таком процессе, соединив лучшие хромосомы

лучших индивидуумов, можно получить лучший индивидуум. Оператором

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

происходить определенные трансформации.

При решении задачи Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)| n требований множе-

ства J должны быть назначены на приборы из множества M. Последователь-

ность геномов g_k в хромосоме X_i = [g₁g₂g₃ . . . g_u] определяет упорядоченное

132

множество требований, которые обслуживаются на приборе M_i ∈ M в ука-

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

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

сти к возникновению конфликтов при обслуживании требований из хромо-

сомы X_i. Например, рассмотрим хромосому X_i = [g₆g₇g₃g₁₀g₅g₉g₈g₁₁g₁g₂g₄] в

качестве упорядоченного списка требований, которые должны быть обслу-

жены на приборе M_i. Требования должны обслуживаться на приборе M_i

в порядке слева направо при условии, что не нарушаются заданные вре-

мена готовности требований к обслуживанию и директивные сроки их об-

служивания. Пусть Y_i = {g₆g₇g₁₀g₉g₈g₁₁g₂g₄} обозначает множество обслу-

женных в срок требований, а Z_i = {g₃g₅g₁} — множество требований, ко-

торые не были обслужены в срок, X_i = Y_i ∪ Z_i. Для того, чтобы обеспе-

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

лельных приборах из множества M, используются разделители d. Раздели-

тели определяют разбиение последовательности X_i на подпоследовательно-

сти требований, назначенных на различные приборы. Для того чтобы на-

значить требования на m параллельных приборов, необходимо использовать

m - 1 разделителей d = {d₁d2 ...dm-1}. Разделители добавляются в хромо-

сому X_i случайно по равномерному закону распределения вероятностей. Рас-

сматривая хромосому X_i = [g₆g₇g₃g₁₀g₅g₉g₈g₁₁g₁g₂g₄] для назначения требо-

ваний на два (три) прибора, необходим один разделитель (два разделите-

ля). Для случая двух приборов M₁ и M₂ можно получить случайную по-

следовательность X_a = [g₆g₇g₃g₁₀d₁g₅g₉g₈g₁₁g₁g₂g₄], определяющую две под-

последовательности {g₆g₇g₃g₁₀} и {g₅g₉g₈g₁₁g₁g₂g₄} параллельного обслужи-

вания требований на двух приборах M₁ и M₂ соответственно. Для случая

трех приборов M₁, M₂ и M₃ можно получить случайную последовательность

X_b = [g₆g₇d₁g₃g₁₀g₅g₉d₂g₈g₁₁g₁g₂g₄], определяющую три подпоследовательно-

сти {g₆g₇}, {g₃g₁₀g₅g₉} и {g₈g₁₁g₁g₂g₄} параллельного обслуживания требова-

ний на трех приборах M₁, M₂ и M₃ соответственно.

Рассмотрим две хромосомы X_a = [g₆g₇g₃g₁₀d₁g₅g₉g₈g₁₁g₁g₂g₄] и X_c = [g₈g₇g₁

g₉g₃d₁g₅g₁₀g₆g₂g₄], определяющие случайно сгенерированные последователь-

ности обслуживания требований на двух приборах M₁ и M₂ соответственно.

Оператор скрещивания работает следующим образом. Выбирается случай-

но позиция в хромосоме X_a = [g₆g₇g₃g₁₀d₁g₅g₉g₈g₁₁g₁g₂g₄]. Например, выбран

геном g₉. Тогда первая часть [g₆g₇g₃g₁₀d₁g₅g₉] хромосомы X_a копируется в

порождаемую хромосому X_e = [g₆g₇g₃g₁₀d₁g₅g₉]. Затем последовательно про-

сматриваются геномы хромосомы X_c, начиная с первого генома g₈. Если оче-

редной геном g_k не содержится в уже сгенерированной части новой хромосо-

мы X_e = [g₆g₇g₃g₁₀d₁g₅g₉ . . .], то геном g_k добавляется в новую хромосому в

том же порядке, как и в хромосоме X_c. В рассматриваемом примере получает-

ся следующая новая хромосома X_e = [g₆g₇g₃g₁₀d₁g₅g₉g₈g₁g₂g₄]. Заметим, что

в построенной хромосоме X_e изменился порядок требований и разделителей.

Для оператора мутации случайно выбираются два генома в рассматриваемой

хромосоме (при этом разделитель также может быть выбран). Затем выбран-

ные геномы (или геном и разделитель) меняются местами в новой хромосоме.

Например, следующая хромосома X_e = [g₆g₇g₃g₄d₁g₅g₉g₈g₁g₂g₁₀] получена из

хромосомы X_e в результате перемены мест геномов g₁₀ и g₄.

133

Алгоритм 1 представляет собой псевдокод генетического алгоритма, раз-

работанного для эвристического решения задачи Q/r_i, d_i/w₁

^∑bi +w₂|J (S)|.

Алгоритм 1. Псевдокод генетического алгоритма

Require: Максимальное число (itr_max) итераций; количество хромосом в каж-

дом поколении (n_pop); число m = N приборов; список требований J; X —

процент скрещиваний; Y — процент мутаций; Z — процент частей для но-

вого поколения.

n_itr ← 1 // счетчик генераций

Cn1 = null // Cnitr — множество хромосом в генерации n_itr

for i=1 to n_pop do

q_c ← случайное решение (J)

Cnitr ← Cnitr ∪ (q_c,evaluate(q_c))

end for

while (n_itr ≤ itr_max) do

n_itr ← n_itr + 1

for i=1 to n_pop × X% do

q_c ← crossover(roulette-wheel(Cnitr -1), roulette-wheel (Cn_itr-1))

Cnitr ← Cnitr ∪ (q_c,evaluate(q_c))

end for

for i=1 to n_pop × Y % do

q_c ← mutate(roulette-wheel(Cnitr -1))

Cnitr ← Cnitr ∪ (q_c,evaluate(q_c))

end for

Cnitr ← Cnitr ∪ elites(Cnitr-1,Z%) // добавляем в новую совокупность

Cnitr Z% лучших Cnitr-1 хромосом как элитные

if лучшее решение не изменяется (Cnitr , itr_max × 10%) then

exit

end if

end while

return лучшее решение (n_itr)

В генетическом алгоритме 1 используются следующие параметры: коли-

чество хромосом в первом поколении n_pop, вероятность операции скрещива-

ния p_c, вероятность операции мутации p_m, максимальное число допустимых

поколений itr_max. В данном эксперименте количество хромосом в первом по-

колении составило 500, вероятность операции скрещивания p_c = 0,6, вероят-

ность операции мутации p_m = 0,04, максимальное число итераций 1000. Пер-

вое поколение состоит из n_pop хромосом. Длина хромосомы n_var равна сумме

количества требований и количества приборов минус один: n_var = n + m - 1.

Числа между 1 и n_var были случайно распределены в хромосоме по равно-

мерному закону распределения вероятностей.

После первого шага алгоритма вычисляется функция приспособленности.

Для выбора родителей из популяции используется функция “колесо рулет-

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

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

134

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

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

обмениваются коды внутри этих мест. В хромосоме натуральные числа от 1

до n представляют собой индекс i для соответствующего требования J_i ∈ J ,

1 ≤ i ≤ n. Если число g в хромосоме больше n, g > n, то число g определяет

индекс k используемого прибора M_k следующим образом: k = g - n. Наиболь-

ший ген ограничен числом n + m.

Функция приспособленности вычисляется следующим образом: F itness =_∑

=w₁

b_i + w₂|J (S)|, что соответствует значению целевой функ-

J_i∈J (S)

ции Φ(S). Генетический алгоритм выполняется до заданного максимально-

го числа поколений (itr_max). Однако если полученное рекордное расписа-

ние не улучшается в течение определенного числа построенных поколений,

то генетический алгоритм может быть также остановлен. В вычислитель-

ных экспериментах использовался вес w₁ = 0,7 для суммарного дохода и вес

w₂ = 1 - w₁ = 0,3 для количества |J (S)| требований, обслуженных в срок при

расписании S.

4.2. Алгоритм имитации отжига

Благодаря своей простоте, алгоритм имитации отжига часто используется

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

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

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

для того, чтобы найти лучшее расписание S^′ [26]. Если построенное распи-

сание S^′ будет иметь большее значение целевой функции, чем предыдущее

рекордное (лучшее из построенных) расписание S, то расписание S^′ будет ис-

пользоваться как новое рекордное расписание (S ←- S^′). Если же новое рас-

писание S^′ не лучше расписания S, то расписание S будет приниматься с веро-

ятностью P (S, S^′, T ) в качестве рассматриваемого расписания. После каждо-

го шага система отжига “остывает”, уменьшая “температуру”, и принятие но-

вого расписания к рассмотрению происходит с вероятностью P (S, S^′, T ). В ал-

горитме имитации отжига используются следующие параметры: количество

новых соседей NN за одну итерацию; начальная температура T₀; конечная

температура T_f ; процедура для уменьшения температуры T_rf ; максимальное

количество итераций itr_max, разрешенных для реализации алгоритма ими-

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

используются процедуры обмена. После создания NN соседей лучшее из по-

лученных расписаний будет выбрано как новое расписание S^′, которое будет

рассматриваться далее. При этом вероятность принятия нового расписания

P (S, S^′, T ) определяется следующим образом: P_r = e(-E)/T .

Алгоритм 2 представляет собой псевдокод алгоритма имитации отжига

для решения задачи Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)|.

Алгоритм 2. Псевдокод алгоритма имитации отжига

Require: Количество новых соседей NN; начальная температура T₀; конеч-

ная температура T_f ; максимальное число итераций itr_max; количество m =

= N приборов; список требований J.

135

n_itr ← 1 // счетчик итераций

T ←T₀

S ← случайно найденное решение (J)

while (n_itr ≤ itr_max) do

n_itr ← n_itr + 1

S^′ ← swap(S) // возврат расписания (S)

ΔF ← (Fit(S^′) - Fit(S))/Fit(S)

if (ΔF < 0) then

S←S^′

else

r ← random(0,1)

P_r ← e(-ΔF)/T

if (r < P_r) then

S←S^′

end if

T_rf = (T₀ - T_f)/itr_max

T = T - T_rf // контроль за температурой

if not-changed(S, itr_max × 10%) then

exit

end if

end while

return лучшее решение S

После реализации очередного шага алгоритма случайным образом выбира-

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

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

енное расписание будет принято. После завершения описанного шага темпе-

ратура будет понижена до значения T := T - T_rf , где T_rf = (T₀ - T_f )/itr_max

определяет величину, на которую произойдет снижение температуры. Реали-

зация алгоритма продолжается до максимального числа itr_max разрешенных

итераций. Если полученное наилучшее расписание не улучшается в пределах

заданного количества итераций, то алгоритм имитации отжига может быть

остановлен.

4.3. Алгоритм поиска с запретами

Алгоритм поиска с запретами является мета-эвристическим алгоритмом,

предложенным в [24] в 1986 г. Выполнение алгоритма начинается с эвристиче-

ски построенного расписания S. Как и алгоритм имитации отжига, алгоритм

поиска с запретами определяет наилучшее соседнее расписание S^′ относи-

тельно рассматриваемого расписания. Если новое расписание S^′ не входит в

список расписаний с запретами, то оно будет выбрано как текущее решение:

S ← S^′. В противном случае будет проверено следующее условие на принятие

расписания S^′. Если новое соседнее расписание S^′ лучше, чем текущее рас-

писание S, то оно будет принято как новое решение S^′, несмотря на то, что

расписание S^′ может попасть в список расписаний с запретами. Фактически,

136

список запретов используется для выхода из локального оптимума. Если но-

вый переход добавляется в список запретов, то некоторые другие переходы

могут быть удалены из него. Параметр, называемый списком запретов T L,

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

список запретов. Такой переход к новому соседнему расписанию будет про-

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

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

ся путем добавления нового запрещенного перехода с целью предотвращения

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

вания алгоритма поиска с запретами).

Алгоритм 3 представляет собой псевдокод поиска с запретами для решения

задачи Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)|.

Алгоритм 3. Псевдокод алгоритма поиска с запретами

Require: Количество NN соседних перестановок; максимальное число lim_t

запрещенных переходов в списке запретов; максимальное число реализуе-

мых итераций itr_max; количество m = N приборов; список требований J.

n_itr ← 1; // счетчик выполненных итераций

set neighbors ← NULL // множество соседей

S_now ← случайно найденное решение (J)

clear-history(H)

while (n_itr ≤ itr_max) do

n_itr ← n_itr + 1

for i=1 to NN do

S^′ ← swap(S_now) // обратная перестановка (S_now)

neighbors ← neighbors ∪ S^′

end for

for all S_candid ∈ neighbors do

if (F it(S_candid) < F it(S_new)) and (S_candid ∈ H) then

S_new ← S_candid

end if

end for

if (F it(S_new) < F it(S_now)) then

S_now ← S_new

update-history(H, S_now)

end if

if not-changed(S_now , itr_max × 10%) then

exit

end if

end while

return лучшее решение S_now

Число соседних перестановок NN за одну итерацию, ограничение перехо-

дов в списке lim_t и максимальное число реализуемых итераций itr_max — это

три основных параметра в алгоритме поиска с запретами. Запреты на перехо-

ды — это переходы, которые уже были реализованы на предшествующих ите-

137

рациях. Если алгоритм поиска с запретами достиг максимально возможного

количества переходов в построенном списке запретов (tabu list), то переходы

с индексами больше единицы, T L > 1, становятся запрещенными для новых

переходов.

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

метр lim_t показывает, что в следующих lim_t итерациях этот переход бу-

дет запрещен. Например, назначение lim_t = 5 для какого-то перехода бу-

дет означать, что в следующих пяти итерациях алгоритма этот переход бу-

дет запрещен. В нашем алгоритме поиска с запретами предполагалось, что

NN = 1000, itr_max = 1000, а параметр lim_t вычислялся следующим образом:

lim_t = ⌈itr_max × 0.05⌉.

Исходное решение в алгоритме поиска с запретами генерируется каким-

либо эвристическим алгоритмом. Затем алгоритм поиска с запретами созда-

ет несколько соседей (путем применения функции замены). После создания

NN соседних перестановок выбираются лучший разрешенный сосед и луч-

ший запрещенный сосед. Если лучший разрешенный сосед лучше, чем луч-

ший запрещенный сосед, то лучший разрешенный сосед будет выбран как но-

вое решение (даже если оно не лучше текущего рекордного решения). С дру-

гой стороны, если лучший запрещенный сосед лучше, чем лучший разрешен-

ный сосед и лучшее построенное рекордное решение, то лучший запрещенный

сосед лучше и будет принят в качестве нового решения. Если все созданные

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

честве нового решения. После замещения текущего рекордного решения его

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

щий выполненный переход, в результате которого получилось новое решение,

будет добавлен в список запретов. Это добавление перехода в список запретов

позволяет алгоритму предотвратить возвращение текущего решения в преж-

нее состояние. При этом индексы всех переходов в списке запретов уменьша-

ют на единицу: T L_i := max{T L_i - 1, 0}. После такого изменения новый пере-

ход будет добавлен в список запретов со следующим индексом, рассматрива-

емым как ограничение: T L_k(solm1, solm2) = Limit; T L_l(solm2, solm1) = Limit.

Выполнение алгоритма 3 продолжается до тех пор, пока не будет достиг-

нуто максимальное количество допустимых итераций itr_max. Если рекордное

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

будет остановлен.

5. Вычислительный эксперимент

Для того чтобы оценить эффективность разработанных алгоритмов (ге-

нетического алгоритма, алгоритма имитации отжига и алгоритма поиска

с запретами), было сгенерировано случайным образом 20 примеров задачи

Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)| с одинаковой средней размерностью n × m, где

n = 50 и m = 5. Для сравнения разработанных алгоритмов решения задач

Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)| большой размерности, которые могут возникать

на практике, случайным образом были сгенерированы 10 задач с количеством

требований n = 500 и количеством приборов m = 50.

138

Таблица 1. Характеристики входных данных четырех классов задач с 50 требова-

ниями и 5 приборами

Класс Длительность Время готовности

Директивный

Прибыль от

задач обслуживания

требования к

срок обслуживания обслуживания

требования

обслуживанию

требования

[1-10]

[0-40]

[1-10]

[1-20]

[1-10]

[0-70]

[1-10]

[1-20]

[1-10]

[0-40]

[1-20]

[1-10]

[0-70]

[1-20]

Задачи средней размерности были пронумерованы последовательно:

1, 2, . . . , 20. Задачи большой размерности пронумерованы последователь-

но: 21, 22, . . . , 30. Входные данные для задач средней размерности состо-

ят из n = 50 требований J_i ∈ J = {J₁, . . . , J₅₀}, которые должны быть об-

служены на m = 5 параллельных однотипных приборах. Скорости прибо-

ров v_k ∈ {0,5; 0,8; 1; 1,1; 1,3} выбирались случайным образом для приборов

M_k ∈ M = {M₁,... ,M₅}. В табл. 1 указаны интервалы генерации длитель-

ностей обслуживания требований J_i ∈ {J₁, . . . , J₅₀} (столбец 2), интервалы

генерации времени r_i готовности требований J_i ∈ J к обслуживанию (стол-

бец 3), интервалы генерации директивных сроков d_i окончания обслужива-

ния требований J_i ∈ J (столбец 4), а также интервалы генерации прибыли,

полученной от своевременного обслуживания требований J_i ∈ J (столбец 5).

Наборы входных данных для 20 случайно сгенерированных задач 1, . . . , 20

средней размерности можно разделить на четыре класса в соответствии с их

характеристиками. В первом классе задач (примеры 1-5) времена готовности

требований к обслуживанию и директивные сроки окончания обслуживания

требований были сгенерированы достаточно близкими между собой. Во вто-

ром классе задач (примеры 6-10) времена готовности требований к обслужи-

ванию были сгенерированы относительно далекими одно от другого, а ди-

рективные сроки окончания обслуживания требований были сгенерированы

более близкими. В третьем классе задач (примеры 11-15) времена готовности

требований к обслуживанию были сгенерированы достаточно близкими, а ди-

рективные сроки окончания обслуживания требований были сгенерированы

более далекими одно от другого. В четвертом классе задач (примеры 16-20)

времена готовности требований к обслуживанию и директивные сроки окон-

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

одно от другого. Длительности обслуживания требований случайным обра-

зом выбирались из множества {1, . . . , 10}. Времена готовности требований к

обслуживанию генерировались случайным образом в пределах разрешенных

для них интервалов, которые указаны в табл. 1. Директивный срок оконча-

ния обслуживания требований определялся как сумма времени готовности

требования к обслуживанию, длительности обслуживания требования и слу-

чайного числа random.range из допустимого интервала положительной дли-

ны: d_i = r_i + p_i + random.range. Отсюда следует, что условие теоремы 2 не

выполняется ни для одного из сгенерированных примеров, решенных в вы-

числительных экспериментах. Поэтому оптимальное значение целевой функ-

139

ции Φ(S) было строго положительным, Φ(S) > 0, для любого из решенных

примеров задачи Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)|. Диапазоны возможных пара-

метров для задач перечисленных классов представлены в табл. 1.

Вычислительные эксперименты были реализованы на компьютере со сле-

дующими характеристиками: Pentium 4, Dual Core, 1,8 ГГц и Рам 4 ГБ.

5.1. Определение приемлемых параметров

разработанных алгоритмов

Различные свойства разработанных алгоритмов такие, как число ите-

раций, количество соседей, размер популяции, время работы компью-

тера (CPU-time) и качество построенных расписаний, исследовались в

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

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

ных алгоритмов для задач

1, . . . , 30. Результаты предварительных вы-

числительных экспериментов по применению генетического алгоритма по-

казали, что увеличение размера популяции (n_pop) и вероятности мута-

ций (p_m) положительно влияет на качество построенных расписаний. Уве-

личение размера популяции n_pop до 1000 родителей может улучшить ка-

чество построенных расписаний. Однако после достижения определенно-

го предела в количестве построенных поколений данный фактор уже не

имел существенного эффекта. На рис. 1 представлены первое слагаемое

(Obj1 = w₁

^∑b_i) и второе слагаемое (Obj2 = w₂|J (S)|) целевой функции

Φ(S) = w₁

^∑b_i + w₂|J(S)| = Obj1 + Obj2 для экспериментов с различными

входными параметрами.

(w₁,w₂) = (1,0)

(w₁,w₂) = (0,1)

(w₁,w₂) = (0,7;0,3)

(w₁,w₂) = (1,0)

n_pop = 100

n_pop = 1000

p_c = 0,4

p_c = 0,6

p_c = 0,8

p_c = 1

p_m = 0,6

p_m = 0,8

p_m = 1

Obj1 Obj2

Рис. 1. Качество расписаний с различными исходными параметрами для ге-

нетического алгоритма.

140

Таблица 2. Результаты решений примеров с диапазонами (w₁, w₂) = (1, 0)

и (w₁, w₂) = (0, 1), полученных с помощью алгоритма имитации отжига

при n_itr = 100, NN = 100, T₀ = 100 и T_f = 0

(w₁, w₂) = (1, 0)

(w₁, w₂) = (0, 1)

^∑b_i J_ok CPU-time n_itr

502

2572

539

495

2802

548

496

2485

638

456

1729

384

499

4985

661

455

1901

436

495

1543

389

472

1421

335

499

2005

500

455

1627

406

Для настройки алгоритма имитации отжига количества NN соседей, рас-

сматриваемых на каждой итерации алгоритма, начинались с 5, a допусти-

мые количества итераций n_itr начинались с 10. Большое число повторных

применений алгоритма имитации отжига показало, что лучшие расписания

получаются при количестве соседей NN = 100 и при допустимом количестве

итераций, равном n_itr = 100. Было установлено, что при увеличении этих па-

раметров качество расписаний существенно не улучшается, а время работы

алгоритма значительно увеличивается.

На основе результатов предварительных вычислительных экспериментов

было установлено, что существует значительная корреляция между двумя

слагаемыми w₁

^∑b_i и w₂|J(S)| целевой функции Φ(S) = w1 ∑b_i + w₂|J(S)|

при условии, что веса w₁ и w₂ имеют близкие значения. Это означает, что

при увеличении числа |J (S)| =: J_ok требований J_i ∈ J (S), обслуженных в

течение заданных интервалов времени [r_i, d_i] при построенном расписании S,

следует ожидать и увеличение прибыли, полученной за выполнение множе-

ства требований в срок. Аналогично, при увеличении прибыли увеличивается

и число J_ok требований во множестве J (S) при условии, что веса w₁ и w₂ име-

ют достаточно близкие значения.

Указанная корреляция существенно слабеет, если веса w₁ и w₂ значительно

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

та для n_itr = 100, NN = 100, (w₁, w₂) = (1, 0) и (w₁, w₂) = (0, 1). Сравнивая

полученные результаты, можно заметить, что большую прибыль можно по-

лучить, если большинство требований J_i ∈ J принадлежат множеству J (S)

при расписании S.

5.2. Обсуждение полученных вычислительных результатов

Максимальное число itr_max разрешенных итераций (поколений) эвристи-

ческого алгоритма является важным фактором качества наилучшего из по-

строенных расписаний. Проведенные вычислительные эксперименты показа-

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

функции Φ(S) = w₁

^∑b_i + w₂|J(S)| для наилучшего построенного расписа-

ния S не увеличивается (см. рис. 2). Для двух других разработанных алго-

ритмов существует аналогичная связь, т.е. увеличение числа разрешенных

итераций itr_max, существенно не влияет на качество наилучших из получен-

ных расписаний, но при этом может существенно увеличиваться время реа-

141

Генетический алгоритм

10³

1 --- Лучшее

2 --- Среднее

10²

10¹

100

150

200

250

Итерация

Рис. 2. Значения целевой функции после каждой итерации генетического ал-

горитма.

лизации алгоритма (CPU-time). В эксперименте исследовалась скорость из-

менения значений целевой функции Φ(S) после каждой итерации алгоритма.

Большое число применений разработанных алгоритмов показало, что под-

ходящее количество итераций для алгоритмов имитации отжига и поиска с

запретами находится около 500 (см. рис. 3 и 4).

На рис. 4 для алгоритма поиска с запретами среднее и лучшее значения

целевой функции одинаковы, поскольку в этом алгоритме используется толь-

ко одно решение задачи Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)| на каждой из итераций.

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

ляется вероятность построения хорошего по критерию Φ(S) расписания при

каждой реализации алгоритма. Вычислительные результаты для десяти при-

менений трех разработанных алгоритмов для одного и того же примера 1 из

первого класса задач (примеры 1-5) представлены в табл. 3. Из этой таб-

лицы следует, что дисперсия результатов в алгоритме имитации отжига ни-

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

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

w₁

^∑b_i целевой функции не менее 495, то применение алгоритма имитации

отжига дает желаемый результат в 8 случаях из 10 реализаций алгоритма.

Применение генетического алгоритма позволило бы достичь желаемого ре-

зультата в 5 случаях из 10 реализаций алгоритма, а применение алгоритма

поиска с запретами — в 4 случаях из 10 реализаций алгоритма. Таким об-

разом, можно сделать вывод, что для решенных в эксперименте примеров

средней размерности вероятность достижения желаемого расписания с по-

142

Таблица 3. Результаты вычислений, полученные в 10 случаях применения трех

алгоритмов для решения примеров класса 1

Алгоритм

Генетический алгоритм

Поиск с запретами

имитации отжига

^∑b_i J_ok CPU-time n_itr

491

294

264

495

1279

614

502

370

648

492

307

262

488

1162

576

471

370

761

498

334

395

496

1733

543

491

213

421

487

404

347

472

1421

335

483

220

452

488

282

495

2802

548

500

317

627

495

298

250

502

2572

539

484

328

385

502

720

227

496

2485

638

506

884

1000

499

416

371

499

4985

661

495

552

388

507

315

279

495

1543

389

444

404

441

491

269

237

499

2005

500

491

669

462

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

генетического алгоритма (n_itr = 1000), алгоритма имитации отжига (n_itr = 50 и

NN = 100) и алгоритма поиска с запретами (NN = 1000 и lim_t = 50)

Алгоритм

Генетический алгоритм

Поиск с запретами

имитации отжига

^∑b_i J_ok CPU-time n_itr

507

315

279

502

2572

539

506

884

1000

554

657

295

546

1526

669

551

299

535

525

1010

362

525

2028

897

524

611

608

561

584

282

561

1716

831

565

297

523

557

351

292

560

2501

884

557

341

576

555

367

231

555

1415

633

557

477

890

501

475

258

505

1770

670

505

280

419

411

422

272

411

1465

682

413

525

767

506

359

282

506

1768

680

506

437

607

551

559

266

552

1547

571

551

221

454

526

590

288

529

1146

587

529

340

634

573

790

307

573

2781

699

572

401

698

512

761

337

513

1486

452

511

303

480

566

644

239

566

1969

510

566

432

671

485

655

260

487

1440

436

492

399

589

540

447

206

540

819

279

540

266

363

515

385

206

515

710

229

515

327

454

510

589

243

510

1249

291

510

242

405

514

601

262

514

1226

347

513

196

376

564

483

214

564

1264

373

564

207

393

144

Таблица 5. Сравнение полученных результатов для 10 примеров большой размер-

ности

Генетический

Алгоритм

Поиск с запретами

алгоритм

имитации отжига

n × m J_ok CPU-time

^∑b_i J_ok CPU-time

^∑b_i

100 × 5

718

652

2852

639

356

571

100 × 10

743

872

4092

892

1265

903

200 × 5

1441

831

6873

789

2026

729

200 × 10

1538

1274

7453

1316

1511

1209

200 × 15

120

2180

1644

115

8582

1624

114

3428

1625

200 × 20

139

2141

1780

145

10375

1807

148

4036

1842

300 × 25

176

5147

2592

180

12964

2573

199

5211

2788

300 × 30

195

5325

2579

199

12430

2593

228

4470

2807

500 × 40

269

8114

4094

270

26368

4012

283

8739

4198

500 × 50

318

8402

4451

319

20601

4385

337

9231

4573

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

других разработанных алгоритмов. Отметим, что сравнение алгоритмов бы-

ло ограниченно рассмотренными в эксперименте примерами.

Второе отличие между алгоритмами — это время реализации алгорит-

ма (CPU-time) на компьютере, необходимое для поиска достаточно хорошего

расписания. Для примера 1 из первого класса все алгоритмы могут обес-

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

^∑b_i ≥ 502. При этом оказалось, что

|J (S)| ≥ 45 требований обслуживалось в установленные сроки при реализа-

ции наилучшего из построенных расписаний. С помощью генетического алго-

ритма такое расписание строится через 385 с, а с помощью алгоритма поиска

с запретами — через 370 с, а при использовании алгоритма имитации отжи-

га — через 2572 с. Таким образом, для построения расписания S, при котором

∑

b_i ≥ 502 и |J (S)| ≥ 45, алгоритм имитации отжига требует почти в 6 раз

больше времени, чем любой из двух других алгоритмов. Отметим, что та-

кие результаты были получены при построении 283 поколений генетическим

алгоритмом, для 647 итераций алгоритма поиска с запретами и для 539 ите-

раций алгоритма имитации отжига. В табл. 2 курсивом выделено наибольшее

время работы алгоритмов (CPU-time) в секундах.

Аналогичная взаимосвязь по времени (CPU-time) работы алгоритмов на-

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

меры 6-10), третьего класса (примеры 11-15) и четвертого класса (приме-

ры 16-20) (табл. 4), а также при решении всех примеров большой размерно-

сти 21-30 (табл. 5).

На основе предварительных вычислительных экспериментов параметры

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

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

ченные в результате 10 реализаций алгоритмов для решения 20 задач средней

размерности с помощью генетического алгоритма, алгоритма имитации от-

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

ные при использовании трех алгоритмов, можно заметить, что все алгоритмы

145

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

при решении примеров 1 и 2 с помощью генетического алгоритма получены

наибольшие значения J_ok. Лучшие результаты были получены при решении

примеров 5 и 13 с помощью алгоритма имитации отжига. Алгоритм поиска с

запретами дал лучшие решения для примеров 4 и 15.

В табл. 2-4 подчеркнуты наилучшие из полученных значений

^∑b_i и

|J (S)| = J_ok. В табл. 4 жирным шрифтом выделены полученные наиболь-

шие (оптимальные) значения |J (S)| = J_ok = |J | = 50. В силу теоремы 1 из

равенства |J (S)| = |J | следует, что и прибыль

^∑b_i также будет наибольшей

(оптимальной) при расписании S. Оптимальные значения для прибыли

^∑b_i

выделены жирным шрифтом в табл. 4.

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

ных алгоритмов, было построено расписание с лучшим значением

^∑b_i и

|J (S)| = J_ok. Оптимальное значение J_ok = 50 было получено генетическим

алгоритмом 6 раз (для примеров 9, 16-20), 7 раз (для примеров 9, 10, 16-20)

при использовании алгоритма имитации отжига и 7 раз при использовании

алгоритма поиска с запретами (для примеров 8, 9, 16-20). Из табл. 4 следу-

ет, что алгоритм имитации отжига построил расписание с лучшим значени-

ем

^∑b_i и (или) лучшим значением |J(S)| = J_ok 31 раз для примеров 1-20

средней размерности, алгоритм поиска с запретами — 27 раз и генетический

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

средней размерности, которые были решены в вычислительном эксперимен-

те, алгоритм имитации отжига превосходит алгоритм поиска с запрета-

ми при нахождении лучших значений целевой функции, тогда как алгоритм

поиска с запретами превосходит генетический алгоритм. Все три разрабо-

танных алгоритма могут показать наилучшую эффективность при решении

примеров средней размерности второго и четвертого классов.

5.3. Результаты вычислительного эксперимента

для задач большой размерности

Разработанные алгоритмы были протестированы на примерах 21-30 для

решения задач Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)| большой размерности. Получен-

ные результаты представлены в табл. 5. Для задач большой размерности

5 раз было построено лучшее расписание с помощью алгоритма поиска с

запретами, 4 раза с помощью генетического алгоритма и один раз с помо-

щью алгоритма имитации отжига (тaбл. 5). Было проведено сравнение, чтобы

определить, сколько раз с помощью каждого разработанного алгоритма было

построено расписание с лучшими значениями

^∑b_i и (или) |J(S)| = J_ok для

примеров большой размерности 21-30. В табл. 5 подчеркнуты лучшие полу-

ченные значения

^∑b_i и |J(S)| = J_ok. Из табл. 5 следует, что расписания, по-

строенные с помощью алгоритма имитации отжига, имели наибольшее значе-

ние

^∑b_i и (или) |J(S)| = J_ok для трех примеров большой размерности 21-30,

с помощью генетического алгоритма — для 6 примеров, с помощью алгоритма

поиска с запретами — для 12 примеров. На основе решенных задач большой

размерности можно заключить, что алгоритм поиска с запретами превосхо-

дит генетический алгоритм, а генетический алгоритм превосходит алгоритм

имитации отжига.

146

С помощью разработанных алгоритмов не было найдено расписаний S с

максимально возможными значениями |J (S)| = J_ok = n для примеров боль-

шой размерности 21-30 (см. табл. 5). К сожалению, пока нет точного алгорит-

ма для нахождения расписания S с наибольшим (оптимальным) значением

целевой функции Φ(S). Поэтому, если |J (S)| < |J |, нельзя оценить, как часто

достигнутые значения целевой функции Φ(S), представленные в табл. 2-5,

являются оптимальными значениями.

6. Практическое значение разработанных алгоритмов

На реально существующих предприятиях задача Q/r_i, d_i/w₁

^∑b_i+

+w₂|J (S)| может возникать, когда необходимо получить максимально воз-

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

рые реализует компания за приемлемое время (на горизонте планиро-

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

ние ресурсов (в данном случае ресурсами являются параллельные одно-

типные приборы) для реализации наиболее подходящих запросов клиен-

тов на горизонте планирования для получения платежа (соответствующее

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

са клиента). Если поток клиентских запросов превышает производствен-

ные возможности компании, некоторые запросы должны быть заранее от-

клонены как нерентабельные, поскольку любая компания имеет ограни-

ченные ресурсы (обслуживающие приборы, станки, оборудование). Один

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

пании, связан с определением соответствующих весов w₁ и w₂ целевой

функции Φ(S) = w₁

^∑b_i + w₂|J(S)| при условии, что выполняется равен-

ство w₁ + w₂ = 1. Следует отметить, что увеличение первого слагаемого

(Obj1 = w₁

^∑b_i) целевой функции Φ(S) = w1 ∑b_i + w₂|J (S)| = Obj1 + Obj2

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

количество клиентов компании на горизонте планирования может быть неиз-

менно или даже уменьшено. С другой стороны, увеличение второго слагае-

мого (Obj2 = w₂|J (S)|) целевой функции Φ означает, что компания пред-

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

сохранена или даже уменьшена на горизонте планирования.

Как показано в проведенных вычислительных экспериментах, если зна-

чения весов w₁ и w₂ близки друг к другу, то существует высокая кор-

реляция между двумя слагаемыми w₁

^∑b_i и w₂|J(S)| целевой функции

Φ(S) = w₁

^∑b_i + w₂|J(S)|. В частности, при увеличении числа |J(S)| тре-

бований (запросов клиентов) J_i ∈ J (S), выполненных в заданные интервалы

времени [r_i, d_i] при расписании S, ожидается увеличение и прибыли компа-

нии. Аналогично, при увеличении прибыли компании увеличивается и число

выполненных в срок требований J (S), если значения весов w₁ и w₂ доста-

точно близки один к другому. Однако если веса w₁ и w₂ различаются суще-

ственно, то часто можно отметить сравнительно низкую корреляцию между

этими слагаемыми для оптимального расписания S.

Решая задачу Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)| с различными множествами тре-

бований J , можно строить различные множества требований J^∗(S), которые

соответствуют удовлетворенным запросам клиентов. Предлагается использо-

147

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

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

рены компанией на горизонте планирования. У принимающих решения лиц

есть возможность выбирать множество J = {J₁, . . . , J_n} требований, которые

включаются в подмножество множества R = {ρ₁, . . . , ρ_λ} всех доступных за-

просов клиентов, где λ ≥ n. Для каждого выбранного требования J_i условие

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

ентов ρ_i ∈ R, которые не могут быть реализованы в течение разрешенных

интервалов времени [r_i, d_i]. Как было доказано в разделе 3.2, такой тест мо-

жет быть реализован за время O(n). Чтобы быстрее реализовать такие тесты,

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

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

После выбора множества требований J , задача Q/r_i, d_i/w₁

^∑b_i+

+w₂|J (S)| должна быть решена для множества J требований с использо-

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

писания S, выполняется равенство J (S) = J , то это расписание S является

оптимальным для выбранного множества J требований (согласно теореме 1).

Однако в построенном расписании S может быть простой приборов. В таком

случае, если выполняется строгое неравенство λ > n, то существуют запро-

сы клиентов, которые не принадлежат множеству J . Лицо, принимающее

решения, может увеличить множество J = {J₁, . . . , J_n} путем выбора подхо-

дящих запросов клиентов из множества R и добавления соответствующих

требований к множеству J . Обозначим расширенное множество требований

через J^′. Тогда задача Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)| может быть снова реше-

на для расширенного множества требований J^′ при условии, что J ⊂ J^′.

Если для построенного расписания S выполняется равенство J (S) = J , то

расписание S является оптимальным для множества требований J^′.

Описанная итерационная схема может быть продолжена до тех пор, по-

ка не будет выполняться неравенство J^∗(S) < J^∗. Полезно решать задачу

Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)| для последнего наибольшего множества J^∗ с ис-

пользованием более эффективного алгоритма, чем тот, который использо-

вался на предыдущих итерациях описанной схемы. С помощью более эф-

фективного алгоритма можно найти и оптимальное расписание S. Однако

процесс более точного решения задачи Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)|, как пра-

вило, требует больше времени. Описанная схема может использоваться и на

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

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

реализуются компанией, состоящей из m фабрик. В этом случае фабрика

соответствует одному из параллельных однотипных приборов множества M.

В рассмотренной задаче Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)| все параметры компа-

нии предполагаются фиксированными. Однако в реальной компании могут

существовать неопределенные параметры, которые трудно определить до ре-

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

расширить с помощью различных инструментов, чтобы учесть неопределен-

ность максимизации доходов компании на основе более эффективного плани-

рования.

148

7. Заключение

Исследована задача максимизации взвешенной суммы прибыли

∑

w₁

b_i и числа требований w₂|J (S)|, обслуженных в срок при рас-

i∈J (S)

писании S. Требования из заданного множества J = {J₁, . . . , J_n} должны

быть обслужены на множестве параллельных однотипных приборов. J (S)

обозначает подмножество требований J , обслуженных в срок при расписа-

нии S. Для каждого требования J_i ∈ J заданы время готовности к обслужи-

ванию r_i > 0 и директивный срок d_i > r_i обслуживания требования. Каждое

требование J_i должно быть обслужено на одном из m заданных однотипных

параллельных приборов. Если требование J_i будет обслужено (т.е. будет на-

чато и завершено) в течение интервала времени [r_i, d_i], то прибыль b_i будет

получена. В противном случае это требование будет удалено из расписания,

а прибыль b_i получена не будет.

Разработаны генетический алгоритм, алгоритм имитации отжига и алго-

ритм поиска с запретами для приближенного решения рассматриваемой зада-

чи. Исследовано влияние различных параметров этих алгоритмов, например

количество поколений (итераций), количество сгенерированных соседей за

одну итерацию, размер популяции для генетического алгоритма, время ра-

боты алгоритма. Было проведено сравнение разработанных алгоритмов по

значению целевой функции Φ(S) = w₁

^∑b_i + w₂|J(S)| и затраченного вре-

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

размерности.

В дальнейших исследованиях было бы полезно найти верхнюю грани-

цу значений целевой функции Φ(S) = w₁

^∑b_i + w₂|J(S)|. Интересная об-

ласть исследований связана с различными критериями оптимальности пла-

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

Представляет интерес разработка точного алгоритма для решения задачи

Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)| средней размерности. Такой алгоритм позволит

сравнивать оптимальные расписания с расписаниями, полученными эвристи-

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

рования имеют неопределенные параметры, было бы полезно исследовать

задачу Q/r_i, d_i/w₁

^∑b_i + w₂|J(S)| с неопределенными длительностями опе-

раций аналогично тому, как это было реализовано в [25] для планирования

множества операций на одном приборе.

СПИСОК ЛИТЕРАТУРЫ

1. Brucker P., Sotskov Y.N., Werner F. Complexity of shop-scheduling problem with

fixed number of jobs: a survey // Math. Methods Oper. Res. 2007. V. 65. No. 3.

P. 461-481.

2. Graham R.E., Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G. Optimization and

approximation in deterministic sequencing and scheduling: a survey // Ann. Discret.

Math. 1979. V. 4. P. 287-326.

3. Anglani A., Grieco A., Guerriero E., Musmanno R. Robust scheduling of parallel

machines with sequence-dependent set-up cost // Eur. J. Oper. Res. 2005. V. 161.

No. 3. P. 704-720.

4. Feng G., Lau H.C. Efficient algorithm for machine scheduling problems with earliness

and tardiness penalties // Ann. Oper. Res. 2008. V. 159. No. 1. P. 83-95.

149

Berrichi A., Yalaoui F. Efficient bi-objective ant colony approach to minimize total

tardiness and system unavailability for a parallel machine scheduling problem // Int.

J. Advanced Manufact. Technol. 2013. V. 68. No. 9-12. P. 2295-2310.

Lin Y.K., Lin C.W. Dispatching rules for unrelated parallel machine scheduling with

release dates // Int. J. Advanced Manufact. Technol. 2013. V. 67. No. 1-4. P. 269-279.

Balin S. Non-identical parallel machine scheduling using genetic algorithm // Expert

Syst. Appl. 2011. V. 38. No. 6. P. 6814-6821.

Juraszek J., Sterna M., Pesch E. Revenue maximization on parallel machines,

Institute of Computing Science, Poznan Univer. Technol. Piotrowo 2, Poznan,

Poland. P. 960-965.

Balin S. Non-identical parallel machine scheduling with fuzzy processing times using

robust genetic algorithm and simulation // Int. J. Innovat. Comput. Inform. Control.

2012. V. 8. No. 1-B. P. 727-745.

10.

Li K., Yang S.-L. Non-identical parallel-machine scheduling research with

minimizing total weighted completion times: models, relaxations and algorithms //

Appl. Math. Modell. 2009. V. 33. No. 4. P. 2145-2158.

11.

Xu S., Bean J.C. A genetic algorithm for scheduling parallel non-identical batch

processing machines // Comput. Intelligen. Scheduling, SCIS ’07. IEEE Sympos.

2007. P. 143-150.

12.

Rodriguez F.J., Blum C., Garcia-Martinez C., Lozano M. GRASP with path-

relinking for the non-identical parallel machine scheduling problem with minimising

total weighted completion times // Ann. Oper. Res. 2012. V. 201. No. 1. P. 383-401.

13.

Supithak W., Plongon K. Memetic algorithm for non-identical parallel machines

scheduling problem with earliness and tardiness penalties // Int. J. Manufactur.

Technol. Management. 2011. V. 22. No. 1. P. 26-38.

14.

Logendran R., McDonell B., Smuckera B. Scheduling unrelated parallel machines

with sequence-dependent setups // Comput. Oper. Res. 2007. V. 34. No. 11.

P. 3420-3438.

15.

Anagnostopoulos G., Rabadi G. A simulated annealing algorithm for the unrelated

parallel machine scheduling problem // Autom. Congr. 2002. Proc. 5 Biannual World.

2002. V. 14. P. 115-120.

16.

Sivrikaya-Serifoglu F., Ulusoy G. Parallel machine scheduling with earliness and

tardiness penalties // Comput. Oper. Res. 1999. V. 26. No. 8. P. 773-787.

17.

Bilge U., Kirac F., Kurtulan M., Pekgun P. A tabu search algorithm for parallel

machine total tardiness problem // Comput. Oper. Res. 2004. V. 31. No. 3.

P. 397-414.

18.

Tavakkoli-Moghaddam R., Taheri F., Bazzazi M. Multi-objective unrelated machines

scheduling with sequence-dependent setup times and precedence constrains // IEE

Transactions A: Basics, 2008. V. 21. No. 3. P. 269-278.

19.

Dunstall S., Wirth A. Heuristic methods for the identical parallel machine problem

with set-up times // Comput. Oper. Res. 2005. V. 32. No. 9. P. 2479-2491.

20.

Sterna M., Juraszek J., Pesch E. Revenue maximization on parallel machines, Book

Chapter // Oper. Res. Proc. 2008. P. 153-158.

21.

Islam M., Khanna G., Sadayappan P. Revenue maximization in market-based

parallel job schedulers, Technical Report, Ohio State University, OSU-CISRC-4/08-

TR16, Ohio, USA, 2008, 1-13.

22.

Dawande M., Drobouchevitch I., Rajapakshe T., Sriskandarajah C. Analysis of

revenue maximazation under two movie-screening policies

// Product. Oper.

Management. 2010. V. 19. No. 1. P. 111-124.

150