Санкт-Петербургский государственный университет
Прикладная математика и информатика
Исследования операций и принятие решений в задачах оптимизации,
управления и экономики
Носкова Екатерина Эдуардовна
Метод имитации отжига для задачи о расписании с
параллельными процессорами
Бакалаврская работа
Научный руководитель:
к. ф.-м. н., доцент Григорьева Н. С.
Рецензент:
к. ф.-м. н., доцент Бухвалова В. В.
Санкт-Петербург
2016
Saint Petersburg State University
Applied Mathematics and Informatics
Operation Research and Decision Making in Optimisation,
Control and Economics Problems.
Noskova Ekaterina
Method of simulated annealing in scheduling
Bachelor’s Thesis
Scientific supervisor:
docent Grigorieva N. S.
Reviewer:
docent Buhvalova V. V.
Saint Petersburg
2016
3
Содержание
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
Глава 1.
Предварительные сведения . . . . . . . . . . . . . . . . . . .
5
1.1. Задача о расписании . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.2. Метод имитации отжига (Simulated annealing) . . . . . . . . . . . .
6
1.2.1.
Физическая мотивировка . . . . . . . . . . . . . . . . . . . .
6
1.2.2.
Обозначения . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.2.3.
Формальная схема метода . . . . . . . . . . . . . . . . . . .
7
Применение метода отжига к задаче о расписании . . .
9
2.1. Представление расписания . . . . . . . . . . . . . . . . . . . . . . .
11
2.2. Алгоритм генерации начального состояния . . . . . . . . . . . . . .
12
2.3. Операция преобразования расписания . . . . . . . . . . . . . . . . .
14
2.4. Функции перехода в новое состояние . . . . . . . . . . . . . . . . .
15
Глава 2.
2.4.1.
Первая функция перехода в новое состояние . . . . . . . .
15
2.4.2.
Вторая функция перехода в новое состояние . . . . . . . .
16
2.4.3.
Третья функция перехода в новое состояние . . . . . . . . .
16
Глава 3.
Статистические результаты применения метода к задаче 18
Заключительные замечания . . . . . . . . . . . . . . . . . . . . . . . . .
19
Список алгоритмов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
4
Введение
Известно, что общая задача о составлении расписания является NP-полной [1].
Существует два подхода к решению этой задачи: нахождение точного решения
(подходит для решения небольших задач или единовременного решения каких-то
конкретных задач, в силу своего происхождения требующих точного решения) и
поиск приближенного решения (подходит для автоматической обработки большо
го количества задач). В последнем случае мы хотим уменьшить среднюю ошибку
по большому массиву задач, при этом сохранив полиномиальную эффективность.
Первый подход реализуется такими алгоритмами как полный перебор или метод
ветвей и границ [1]. Второй подход реализуется бесчисленным множеством эври
стических алгоритмов, об одном из которых пойдет речь в данной работе.
Здесь мы будем обсуждать эффективность эвристического алгоритма имитации
отжига для решения общей задачи о расписании.
Работа поделена на разделы: “Введение”, “Глава 1: Предварительные сведения”,
“Глава 2: Метод имитации отжига”, “Глава 3: Статистические результаты приме
нения метода к задаче”, “Заключительные замечания” и “Список литературы”.
Наиболее важными из них являются Глава 2, в которой подробно описан алго
ритм, большей частью реализованный на псевдокоде, и Глава 3, в которой мы
приводим статистический анализ эффективности нашей реализации (про реали
зацию см. далее).
Описываемый алгоритм реализован нами в виде мультиплатформенной програм
мы на языке программирования C++, исходный код которой опубликован в сети
Интернет по адресу:
https://bitbucket.org/noscode/simulated_annealing_for_general_scheduling_
problem/.
5
Глава 1
Предварительные сведения
1.1. Задача о расписании
Нам дана система заданий 𝑈 = {𝑢1 , 𝑢2 , ..., 𝑢𝑛 }, на которой задано отношение ча
стичного порядка ≺: выражение 𝑢𝑖 ≺ 𝑢𝑗 означает, что выполнение задания 𝑢𝑗
может быть начато только после завершения задания 𝑢𝑖 . Заданы целочисленные
времена исполнения заданий {𝑡𝑖 }𝑛𝑖=1 . Для выполнения заданий имеется 𝑚 иден
тичных процессоров. Любое задание может выполняться на любом процессоре, и
каждый процессор может выполнять не более одного задания в каждый момент
времени. Прерывания выполнения заданий не допускаются.
Требуется составить расписание 𝑆 выполнения заданий процессорами так, чтобы
общее время выполнения было минимальным, то есть найти для каждого задания
𝑢𝑖 время начала выполнения задания 𝑠𝑖 и номер процессора 𝑝𝑖 , на котором оно
выполняется, так чтобы величина:
𝑡𝑆 = max{𝑠𝑖 + 𝑡𝑖 | 𝑢𝑖 ∈ 𝑈 }.
была минимальной.
(1.1)
6
1.2. Метод имитации отжига (Simulated annealing)
1.2.1. Физическая мотивировка
У каждого металла есть кристаллическая решетка. Совокупность позиций всех
атомов будем называть состоянием системы, каждому состоянию соответствует
определенный уровень энергии. Цель метода –– привести систему в состояние с
наименьшей энергией.
В ходе «отжига» металл сначала нагревают до некоторой температуры, что за
ставляет атомы кристаллической решетки покинуть свои позиции. Затем начина
ется медленное и контролируемое охлаждение. Атомы стремятся попасть в состоя
ние с меньшей энергией, однако, с определенной вероятностью они могут перейти
и в состояние с большей. Эта вероятность уменьшается вместе с температурой.
Переход в худшее состояние, как ни странно, помогает в итоге отыскать состоя
ние с энергией меньшей, чем начальная. Процесс завершается, когда температура
падает до заранее заданного значения.
Алгоритм имитации отжига не гарантирует нахождения минимума функции энер
гии, однако преимуществом метода является то, что он вытаскивает ее из локаль
ных минимумов.
1.2.2. Обозначения
Введем обозначения:
Пусть S —- множество всех состояний (решений) нашей задачи.
Пусть 𝑆𝑖 ∈ S —- состояние на i-м шаге алгоритма, а 𝑇𝑖 ∈ R - температура на i-м
шаге.
Также нам понадобится определить четыре функции:
∙ E : 𝑆 → R — функция энергии (то, что оптимизируем).
7
∙ T : N → R — убывающая функция изменения температуры с течением
времени.
∙ F : 𝑆 → 𝑆 — функция, порождающую новое состояние.
∙ P : R2 → (0, 1) — функция вероятности перехода в новое состояние. Если
функция энергии нового состояния меньше, чем старого, то вероятность пе
рехода равняется 1. Если больше, то чем больше эта разница, тем меньше
вероятность перехода.
Функция E каждому решению по какому-то правилу ставит в соответствие число.
Зависит от конкретной задачи.
Функция T ставит номеру итерации 𝑖 в соответствие температуру. Функция опре
деляет как долго будет работать наш алгоритм. Если T будет линейной функци
ей, то время работы будет относительно большим. В случае же со степенной функ
цией, скажем T (𝑖) =
𝑡1
𝛼𝑖 ,
всё закончится очень быстро, но мы можем застрять в
локальном минимуме, так и не добравшись до финиша.
Функция F на основе предыдущего состояния порождает новое состояние-канди
дат 𝑠𝑛𝑒𝑤 , в которое система может перейти, а может и отбросить.
Вероятность P перехода чаще всего задается функцией:
⎧
⎪
⎨1,
если ∆𝐸 ≤ 0
P(∆𝐸, 𝑇 ) =
.
⎪
⎩𝑒 Δ𝐸
𝑇 ,
если ∆𝐸 > 0
(1.2)
1.2.3. Формальная схема метода
На вход даются начальное состояние 𝑆0 , начальная температура 𝑇max и конечная
температура 𝑇min , на которой алгоритм прекратит работу.
8
На каждой итерации алгоритм вычисляет новое состояние 𝑆𝑛𝑒𝑤 = F (𝑆𝑖−1 ). Если
оно лучше (функция энергии E меньше), то алгоритм переходит в это состояние,
если нет, то переходит с некоторой вероятностью P(∆𝐸, 𝑇 ). Затем понижается
температура: 𝑇𝑖+1 = T (𝑖) — и начинается новая итерация.
На выход идет лучшее состояние за все время работы алгоритма.
SIMULATED-ANNEALING(𝑇max , 𝑇min , 𝑆0 )
1: 𝑖 := 1
2:
𝑇0 := 𝑇max
3:
𝑆𝑏𝑒𝑠𝑡 := 𝑆0
4:
while 𝑇𝑖 > 𝑇min do
5:
𝑆𝑛𝑒𝑤 := F (𝑆𝑖−1 )
6:
∆𝐸 := E (𝑆𝑛𝑒𝑤 ) − E (𝑆𝑖−1 )
7:
if P(∆𝐸, 𝑇𝑖 ) ≥ 𝑟𝑎𝑛𝑑𝑜𝑚(0, 1) then
8:
9:
10:
11:
12:
◁ Переходим ли в новое состояние
𝑆𝑖 := 𝑆𝑛𝑒𝑤
else
𝑆𝑖 := 𝑆𝑖−1
if E (𝑆𝑖 ) < E (𝑆𝑏𝑒𝑠𝑡 ) then
◁ Запоминаем лучшее состояние
𝑆𝑏𝑒𝑠𝑡 := 𝑆𝑖
13:
𝑖 := 𝑖 + 1
14:
𝑇𝑖+1 := T (𝑖)
15:
◁ Температура на 0 итерации
return 𝑆𝑏𝑒𝑠𝑡
◁ Понижаем температуру
9
Глава 2
Применение метода отжига к задаче о расписании
Пусть у нас есть задача о расписании:
∙ 𝑛 — количество заданий,
∙ 𝑚 — количество процессоров,
∙ 𝑈 = {𝑢𝑖 }𝑛𝑖=1 — множество заданий,
∙ {𝑡𝑖 }𝑛𝑖=1 — целочисленные времена выполнения заданий,
∙ 𝐺 = ⟨𝑈, 𝐸⟩ — ациклический граф, который задает отношение частичного
порядка на множестве 𝑈 : дуга 𝑒 = (𝑢𝑖 , 𝑢𝑗 ) принадлежит множеству 𝐸 дуг
графа 𝐺 тогда и только тогда, когда 𝑢𝑖 ≺ 𝑢𝑗 . Предполагаем, что множество
вершин графа топологически отсортировано: каждое ребро идет от вершины
с меньшим номером к вершине с большим.
Для применения метода отжига, у нас есть:
∙ S — множество состояний. Очевидно, что состоянием задачи о расписании
будет является любое допустимое расписание 𝑆.
∙ E (𝑆) = 𝑡𝑆 = max{𝑠𝑖 + 𝑡𝑖 | 𝑢𝑖 ∈ 𝑈 } — функция энергии, она же длина
расписания.
∙ 𝑇𝑚𝑖𝑛 = 1 — конечная температура, при достижении которой алгоритм пре
кращает работу.
∙ T (𝑘) = 𝑇𝑘 — функция изменения температуры на каждой итерации. В
смежных задачах часто используются показательные функции, например:
𝑇𝑘 = 0.999𝑘 · 𝑇𝑚𝑎𝑥 .
(2.1)
10
Но тогда количество итераций растет логарифмически при увеличении на
чальной температуры 𝑇𝑚𝑎𝑥 . Это не всегда удобно.
Поэтому будем рассматривать следующую функцию:
𝑇𝑘 = 𝑇𝑚𝑎𝑥 −
𝑇𝑚𝑎𝑥 − 𝑇𝑚𝑖𝑛
· 𝑘,
𝑓 (𝑇𝑚𝑎𝑥 )
(2.2)
для которой количеством итераций будет: 𝑘𝑚𝑎𝑥 = 𝑓 (𝑇𝑚𝑎𝑥 ).
Вполне интуитивно, что количество итераций для различных 𝑛 должно быть
разным: чем больше 𝑛, тем больше 𝑘𝑚𝑎𝑥 . Поэтому сделаем начальную тем
пературу зависимой от 𝑛.
В случае показательной функции изменения температуры в качестве началь
𝑛2
ной температуры возьмем функцию: 𝑇𝑚𝑎𝑥 =
. Она была подобрана по
1000
необходимому количеству итераций для среднего случая наших эксперимен
тальных данных.
Во втором случае в качестве 𝑓 (𝑇𝑚𝑎𝑥 ) выберем линейную функцию. Mетодом
проб и ошибок были найдены необходимое количество итераций для задач
и следующие функции:
𝑇𝑚𝑎𝑥 = 𝑛,
𝑓 (𝑇𝑚𝑎𝑥 ) = 7 · 𝑇𝑚𝑎𝑥 + 3000.
∙ F — функция, порождающая новое состояние. Ее варианты будут описаны
далее.
∙ P(∆𝐸, 𝑇 ) =
⎧
⎪
⎨1,
если ∆𝐸 ≤ 0
⎪
⎩𝑒 Δ𝐸
𝑇 ,
если ∆𝐸 > 0
вое состояние.
— функция вероятности перехода в но
11
2.1. Представление расписания
Можем представить наше расписание 𝑆 как некую перестановку 𝜋 заданий {𝑢𝜋(𝑖) }𝑛𝑖=1 ,
которая определяет порядок постановки заданий на выполнение, и вектор {𝑝𝑖 }𝑛𝑖=1 ,
где 𝑝𝑖 — номер процессора, выполняющего 𝑢𝑖 -ое задание. Перестановка должна
удовлетворять графу предшествования, то есть если 𝑢𝑖 ≺ 𝑢𝑗 , то 𝜋(𝑖) < 𝜋(𝑗).
Если это условие выполнено, то мы легко можем вычислить время начала 𝑠𝑖 лю
бого задания 𝑢𝑖 как максимум из времени освобождения процессора 𝑝𝑖 и мини
мального допустимого времени постановки задания. Допустимость времени опре
деляется предшественниками задания — оно не может начаться, пока они не вы
полнятся.
Подробнее алгоритм можно посмотреть в псевдокоде:
CALCULATE-START-TIMES()
1: for 𝑖 := 𝜋(1) : 𝜋(𝑛) do
2:
𝑗 := 𝑝𝑖
◁ Номер процессора
3:
𝑠1 := max{𝑠𝑘 + 𝑡𝑘 | 𝜋(𝑘) < 𝜋(𝑖), 𝑝𝑘 = 𝑗} ◁ Время освобождения процессора
4:
𝑠2 := max{𝑠𝑘 + 𝑡𝑘 | 𝜋(𝑘) < 𝜋(𝑖), 𝑢𝑘 ≺ 𝑢𝑖 }
◁ Минимальное время для
задания
5:
𝑠𝑖 := max{𝑠1, 𝑠2}
Легко понять, что такой способ вычисления времени начала задания строит со
ответствующее данной перестановке расписание минимальной длины. Поэтому
можно пренебречь вектором {𝑠𝑖 }𝑛𝑖=1 вообще.
Однако в нашем случае, на каждой итерации метода отжига нам необходимо вы
числять длину расписания, чтобы сравнивать ее. Для этого придется считать вре
мена начала для заданий, что потребует порядка 𝑛2 итераций. Поэтому для по
вышения эффективности будем хранить оба представления одновременно. Это
позволит немного оптимизировать процесс: надо будет пересчитывать времена не
для всех, а только для части заданий. Тогда можно переписать код как:
12
REFRESH-START-TIMES(𝑓 𝑟𝑜𝑚)
1: for 𝑖 := 𝜋(𝑓 𝑟𝑜𝑚) : 𝜋(𝑛) do
2:
𝑗 := 𝑝𝑖
◁ Номер процессора
3:
𝑠1 := max{𝑠𝑘 + 𝑡𝑘 | 𝜋(𝑘) < 𝜋(𝑖), 𝑝𝑘 = 𝑗} ◁ Время освобождения процессора
4:
𝑠2 := max{𝑠𝑘 + 𝑡𝑘 | 𝜋(𝑘) < 𝜋(𝑖), 𝑢𝑘 ≺ 𝑢𝑖 }
◁ Минимальное время для
задания
𝑠𝑖 := max{𝑠1, 𝑠2}
5:
2.2. Алгоритм генерации начального состояния
Для начала работы метода имитации отжига нам надо получить начальное состо
яние.
Для этого мы будем использовать жадный алгоритм: на каждой итерации на
ходим готовое к выполнению задание с максимальным временем исполнения и
ставим его на менее загруженный процессор.
Функция LONGEST-AVALIABLE-TASK() вычисляет доступное задание с макси
мальным временем исполнения. Для ее реализации необходимо каждому заданию
𝑢𝑖 поставить в соответствие флаг 𝑖𝑠𝐷𝑜𝑛𝑒(𝑖), который имеет значение 𝑡𝑟𝑢𝑒, если
задание уже поставлено на какой-то процессор.
LONGEST-AVALIABLE-TASK({𝑖𝑠𝐷𝑜𝑛𝑒(𝑖)}𝑛𝑖=1 )
1: 𝑖 := 1
2:
for 𝑗 := 2 : 𝑛 do
◁ Если все предшественники элемента выполнены, то сравниваем длины
3:
4:
if 𝑖𝑠𝐷𝑜𝑛𝑒(𝑘) = 𝑡𝑟𝑢𝑒, ∀𝑘 : 𝑢𝑘 ≺ 𝑢𝑗 then
if 𝑡𝑗 > 𝑡𝑖 then
𝑖 := 𝑗
5:
6:
return 𝑖
13
Теперь можем написать псевдокод жадного алгоритма:
GREEDY-ALGORITHM()
1: 𝑖𝑠𝐷𝑜𝑛𝑒(𝑝) := 𝑓 𝑎𝑙𝑠𝑒, 𝑝 = 1..𝑛
2:
𝑙𝑜𝑎𝑑𝑃 𝑟𝑜𝑐𝑒𝑠𝑠𝑜𝑟𝑠 := 𝑚-мерный вектор из 0
◁ Вектор загруженности
процессоров
3:
for 𝑘 := 1 : 𝑛 do
4:
𝑖 := LONGEST-AVALIABLE-TASK({𝑖𝑠𝐷𝑜𝑛𝑒(𝑝)}𝑛𝑝=1 )
5:
𝜋(𝑖) := 𝑘
6:
𝑗 := 1
7:
for 𝑙 := 2 : 𝑚 do
8:
◁ Создаем перестановку
◁ Найдем номер менее загруженного процессора
if 𝑙𝑜𝑎𝑑𝑃 𝑟𝑜𝑐𝑒𝑠𝑠𝑜𝑟𝑠(𝑙) < 𝑙𝑜𝑎𝑑𝑃 𝑟𝑜𝑐𝑒𝑠𝑠𝑜𝑟𝑠(𝑗) then
𝑗 := 𝑙
9:
10:
𝑝𝑖 := 𝑗
◁ Ставим задание на процессор
11:
𝑙𝑜𝑎𝑑𝑃 𝑟𝑜𝑐𝑒𝑠𝑠𝑜𝑟𝑠(𝑗) := 𝑙𝑜𝑎𝑑𝑃 𝑟𝑜𝑐𝑒𝑠𝑠𝑜𝑟𝑠(𝑗) + 𝑡𝑖
◁ Увеличиваем
загруженность
12:
𝑖𝑠𝐷𝑜𝑛𝑒(𝑖) := 𝑡𝑟𝑢𝑒
◁ Задание выполнено
14
2.3. Операция преобразования расписания
В методе имитации отжига нам также необходимо задать функцию F перехода
в новое состояние.
Для этого рассмотрим операцию преобразования расписания MOVE-TASK(𝑖, 𝑝𝑛𝑒𝑤 ,
𝜋𝑛𝑒𝑤 ) — она переносит задание 𝑢𝑖 ∈ 𝑈 на процессор с номером 𝑝𝑛𝑒𝑤 и меняет по
рядок выполнения задания 𝜋𝑖 = 𝜋𝑛𝑒𝑤 .
При этом на 𝜋𝑛𝑒𝑤 накладываются ограничения, так как перестановка должна удо
влетворять графу предшествования:
max{𝜋(𝑗) | 𝑢𝑗 ≺ 𝑢𝑖 } < 𝜋𝑛𝑒𝑤 < min{𝜋(𝑗) | 𝑢𝑖 ≺ 𝑢𝑗 }
MOVE-TASK(𝑖, 𝑝𝑛𝑒𝑤 , 𝜋𝑛𝑒𝑤 )
1: 𝑝𝑖 := 𝑝𝑛𝑒𝑤
2:
if 𝜋𝑛𝑒𝑤 < 𝜋(𝑖) then
3:
for 𝑗 := 𝜋(𝑖) : 𝜋𝑛𝑒𝑤 do
4:
𝜋(𝑗) := 𝜋(𝑗) + 1
5:
◁ Поменяли привязку задания к процессору
◁ Изменяем перестановку заданий
else
6:
for 𝑗 := 𝜋𝑛𝑒𝑤 : 𝜋(𝑖) do
7:
𝜋(𝑗) := 𝜋(𝑗) − 1
8:
(2.3)
𝜋(𝑖) := 𝑝𝑛𝑒𝑤
Заметим, что если новое расписание, полученное этой операцией, является допу
стимым, то операция обратима.
Теорема 2.3.1. Если 𝑆 и 𝑆¯ - два корректных расписания, то существует конечная
цепочка промежуточных корректных расписаний таких, что каждое получено
из предыдущего применением операции MOVE-TASK 𝐾 ≤ 2𝑛 раз.
Доказательство довольно тривиально, оно подробно изложено в [3].
15
2.4. Функции перехода в новое состояние
2.4.1. Первая функция перехода в новое состояние
Теперь мы можем построить функцию, которая будет возвращать нам новое близ
кое состояние системы.
Будем генерировать номер задания, номер процессора, новый номер перестановки
и применять операцию MOVE-TASK. Номера задания и процессора могут быть
любыми, ограничиваются только количеством каждого, а вот номер перестановки
должен удовлетворять требованию 2.3. Поэтому сначала нужно найти нижнюю и
верхнюю границы и затем сгенерировать число между ними.
GENERATE-NEW-POSITION(𝑖)
1: 𝑙𝑜𝑤𝑒𝑟𝐵𝑜𝑢𝑛𝑑 := 0
2:
𝑢𝑝𝑝𝑒𝑟𝐵𝑜𝑢𝑛𝑑 := 𝑛 + 1
3:
for 𝑗 := 1 : 𝑛 do
4:
5:
6:
7:
◁ Считаем точные границы
if 𝑢𝑗 ≺ 𝑢𝑖 then
𝑙𝑜𝑤𝑒𝑟𝐵𝑜𝑢𝑛𝑑 := max{𝑙𝑜𝑤𝑒𝑟𝐵𝑜𝑢𝑛𝑑; 𝜋𝑗}
if 𝑢𝑖 ≺ 𝑢𝑗 then
𝑢𝑝𝑝𝑒𝑟𝐵𝑜𝑢𝑛𝑑 := min{𝑢𝑝𝑝𝑒𝑟𝐵𝑜𝑢𝑛𝑑; 𝜋𝑗}
◁ Генерируем число между двумя границами
8:
𝜋𝑛𝑒𝑤 := 𝑟𝑎𝑛𝑑𝑜𝑚(𝑙𝑜𝑤𝑒𝑟𝑏𝑜𝑢𝑛𝑑 + 1; 𝑢𝑝𝑝𝑒𝑟𝐵𝑜𝑢𝑛𝑑 − 1)
9:
return 𝜋𝑛𝑒𝑤
16
GET-NEW-STATE-1()
1: 𝑖 := 𝑟𝑎𝑛𝑑𝑜𝑚(1, 𝑛)
2:
◁ “Выбираем” задание
𝑝𝑛𝑒𝑤 := 𝑟𝑎𝑛𝑑𝑜𝑚(1, 𝑚)
◁ и процессор
◁ Генерируем новый номер в очереди на выполнение
3:
𝜋𝑛𝑒𝑤 := GENERATE-NEW-POSITION(𝑖)
4:
𝑓 𝑟𝑜𝑚 := min{𝜋(𝑖), 𝜋𝑛𝑒𝑤 }
5:
MOVE-TASK(𝑖, 𝑝𝑛𝑒𝑤 , 𝜋𝑛𝑒𝑤 )
◁ Запоминаем для пересчета времен
◁ Перемещаем задание
◁ Пересчитываем времена начала заданий, которые могли передвинуться
6:
REFRESH-START-TIMES(𝑓 𝑟𝑜𝑚)
2.4.2. Вторая функция перехода в новое состояние
До этого для генерации номера задания было взято равномерное распределение.
Но можно взять распределение такое, чтобы вероятность выбора заданий с более
загруженных процессоров была больше.
Назовем такую функцию GET-NEW-STATE-2().
2.4.3. Третья функция перехода в новое состояние
Теперь обратимся обратно к жадному алгоритму, с помощью которого получили
начальное состояние. Этот алгоритм распределяет задания по процессорам до
вольно “равномерно”. Поэтому перенос одного задания на другой процессор ско
рее всего будет увеличивать длину расписания.
Приходим к новой идее: выбираем два задания на разных процессорах и меняем
их местами: переносим каждое из них на процессор другого.
17
GET-NEW-STATE-3()
1: 𝑖1 := 𝑟𝑎𝑛𝑑𝑜𝑚(1, 𝑛)
◁ “Выбираем” первое задание
2:
𝑖2 := 𝑟𝑎𝑛𝑑𝑜𝑚(1, 𝑛)
◁ “Выбираем” второе задание
3:
while 𝑝𝑖1 = 𝑝𝑖2 do
4:
𝑖2 := 𝑟𝑎𝑛𝑑𝑜𝑚(1, 𝑛)
5:
1
𝜋𝑛𝑒𝑤
:=GENERATE-NEW-POSITION(𝑖1 )
6:
1
}
𝑓 𝑟𝑜𝑚 := min{𝜋(𝑖1 ), 𝜋𝑛𝑒𝑤
7:
1
)
MOVE-TASK(𝑖1 , 𝑝𝑖2 , 𝜋𝑛𝑒𝑤
8:
2
𝜋𝑛𝑒𝑤
:= GENERATE-NEW-POSITION(𝑖2 )
9:
2
𝑓 𝑟𝑜𝑚 := min{𝑓 𝑟𝑜𝑚, 𝜋(𝑖2 ), 𝜋𝑛𝑒𝑤
}
10:
◁ Начинаем запоминать для пересчета времен
2
MOVE-TASK(𝑖2 , 𝑝𝑖1 , 𝜋𝑛𝑒𝑤
)
◁ Перемещаем первое задание
◁ Перемещаем второе задание
◁ Пересчитываем времена начала заданий, которые могли передвинуться
11:
REFRESH-START-TIMES(𝑓 𝑟𝑜𝑚)
18
Глава 3
Статистические результаты применения метода к
задаче
𝑁
Алгоритм
𝑇𝑚𝑎𝑥 𝑇𝑚𝑖𝑛
1
GREEDY-ALGORITHM()
2
GET-NEW-STATE-1()
3
T (𝑘)
𝑘𝑚𝑎𝑥
1
—
𝑛2
1000
—
—
1
0.999𝑘 · 𝑇𝑚𝑎𝑥
GET-NEW-STATE-1()
𝑛
1
4
GET-NEW-STATE-2()
𝑛2
1000
1
5
GET-NEW-STATE-2()
𝑛
1
6
GET-NEW-STATE-3()
𝑛2
1000
1
7
GET-NEW-STATE-3()
𝑛
1
𝑇𝑚𝑎𝑥 −
log0.999
𝑇𝑚𝑖𝑛
𝑇𝑚𝑎𝑥
𝑇𝑚𝑎𝑥 − 𝑇𝑚𝑖𝑛
· 𝑘 7 · 𝑛 + 3000
𝑘𝑚𝑎𝑥
0.999𝑘 · 𝑇𝑚𝑎𝑥
𝑇𝑚𝑎𝑥 −
𝑇𝑚𝑖𝑛
𝑇𝑚𝑎𝑥
𝑇𝑚𝑎𝑥 − 𝑇𝑚𝑖𝑛
· 𝑘 7 · 𝑛 + 3000
𝑘𝑚𝑎𝑥
0.999𝑘 · 𝑇𝑚𝑎𝑥
𝑇𝑚𝑎𝑥 −
log0.999
log0.999
𝑇𝑚𝑖𝑛
𝑇𝑚𝑎𝑥
𝑇𝑚𝑎𝑥 − 𝑇𝑚𝑖𝑛
· 𝑘 7 · 𝑛 + 3000
𝑘𝑚𝑎𝑥
Таблица 3.1: Список примененных методов.
𝑁
1
2
3
4
5
6
7
Средняя
Среднеквадратическое
Максимальная
В скольки процентах
Средняя
относительная
отклонение относительной
относительная
случаев получено
абсолютная
ошибка
ошибки
ошибка
оптимальное расписание
ошибка
1.57666
1.21511
1.13863
1.19298
1.10155
1.10944
1.06601
0.298644
0.198583
0.146999
0.182492
0.114651
0.110456
0.080904
2.19927
1.80246
1.62754
1.84848
1.53237
1.55246
1.36384
3.9%
11.3%
13.7%
5.8%
12.9%
11.7%
13.7%
837.263
309.965
182.337
218.918
125.604
138.906
67.702
Таблица 3.2: Статистические результаты.
19
Заключительные замечания
В работе были описаны, реализованы и проанализированы разные вариации мето
да имитации отжига применительно к общей задаче о расписании. Как и стоило
ожидать лучший результат дает вариант алгоритма, где для перехода к новому
расписанию два задания меняются местами, а количество итераций линейно зави
сит от количества заданий (этого следовало ожидать, так как жадный алгоритм,
используемый для получения начального решения старается распределить зада
ния равномерно по процессорам).
В итоге мы получили полиномиальный алгоритм, средняя ошибка которого на
наших экспериментальных данных составила всего 1.06601.
Как уже говорилось во введении наша программа опубликована в сети Интернет
по адресу:
https://bitbucket.org/noscode/simulated_annealing_for_general_scheduling_
problem/.
20
Список алгоритмов
SIMULATED-ANNEALING(𝑇max , 𝑇min , 𝑆0 ) . . . . . . . . . . . . . . .
8
CALCULATE-START-TIMES() . . . . . . . . . . . . . . . . . . . . .
11
REFRESH-START-TIMES(𝑓 𝑟𝑜𝑚) . . . . . . . . . . . . . . . . . . . .
12
LONGEST-AVALIABLE-TASK({𝑖𝑠𝐷𝑜𝑛𝑒(𝑖)}𝑛𝑖=1 ) . . . . . . . . . . . .
12
GREEDY-ALGORITHM() . . . . . . . . . . . . . . . . . . . . . . . .
13
MOVE-TASK(𝑖, 𝑝𝑛𝑒𝑤 , 𝜋𝑛𝑒𝑤 ) . . . . . . . . . . . . . . . . . . . . . . .
14
GENERATE-NEW-POSITION(𝑖) . . . . . . . . . . . . . . . . . . . .
15
GET-NEW-STATE-1() . . . . . . . . . . . . . . . . . . . . . . . . . .
16
GET-NEW-STATE-3() . . . . . . . . . . . . . . . . . . . . . . . . . .
17
21
Литература
1. Григорьева Н.С. Теория расписаний методические указания // СПбГУ кафедра
Исследования Операций 1995 г.
2. S. G. Ponnambalam, N. Jawahar, P. Aravindan A simulated annealing algorithm
for job shop scheduling, Production Planning & Control: The Management of
Operations, 10:8, 1999г, с. 767-777.
3. Костенко В. А. Задача построения расписания при совместном пректировании
аппаратных и программных средств // Программирование, 2002г, №3, с. 46-80.
4. http://www.kasahara.elec.waseda.ac.jp/schedule/
Отзывы:
Авторизуйтесь, чтобы оставить отзыв