ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2007, том 47, < 6, с. 1087-1098
УДК 519.853.6
РЕШЕНИЕ NP-ТРУДНОЙ ЗАДАЧИ ТЕОРИИ РАСПИСАНИЙ МИНИМИЗАЦИИ СУММАРНОГО ЗАПАЗДЫВАНИЯ1^
© 2007 г. А. А. Лазарев
(119991 Москва, ул. Вавилова, 40, ВЦ РАН) e-mail: Alexandr.Lazarev@mail.ru Поступила в редакцию 15.08.2006 г.
Рассматривается классическая NP-трудная в обычном смысле задача теории расписаний для одного прибора минимизации суммарного запаздывания 1|PT'. Проведен полный анализ NP-трудного случая задачи. Предлагается процедура разбиения исходного множества требований на подмножества. Построены алгоритмы нахождения оптимального расписания в зависимости от количества подмножеств. Трудоемкость алгоритмов не превышает O(n2'Lpj) операций, где n - количество требований, а Pj - продолжительность обслуживания j-го требования, j = 1, 2, ..., n. Библ. 11.
Ключевые слова: теория расписания, один прибор, минимизация суммарного запаздывания, псевдополиномиальные алгоритмы.
1. ВВЕДЕНИЕ
Рассматривается задача, в которой необходимо обслужить n требований на одном приборе. Прерывания при обслуживании и обслуживание более одного требования в любой момент времени запрещены. Для требования j е N = {1, 2, ..., n} заданы продолжительность обслуживания
Pj > 0, Pj е Z+, и директивный срок окончания обслуживания dj, где N - множество требований. Все требования поступают на обслуживание одновременно в момент времени t0, с которого прибор готов начать обслуживание требований. Расписание обслуживания требований п строится с момента времени t0 и однозначно задается перестановкой элементов множества N.
Требуется построить расписание п* обслуживания требований множества N, при котором достигается минимум функции F(n) = = 1 max{0, Cj(п) - dj}, где Cj(п) - момент завершения обслуживания требования j при расписании п. Пусть п = (j1, ..., jn), тогда Cj (п) = t0 + pji и Cj (п) = = ch i (п) + Pj для k = 2, 3, ..., n. Величина Tj(п) = max{0, Cj(п) - dj} называется запаздыванием
требования j при расписании п, а ^(п) - суммарным запаздыванием требований при расписании п. Если обслуживание требования i предшествует обслуживанию требования j при расписании п, то для этого будем использовать запись (i —- j )п. Множество требований, обслуживаемых при расписании п, будем обозначать через {п}. Множество оптимальных расписаний обслуживания требований множества N с момента времени t0 будем обозначать через n*(N, t0).
Исследуемая задача является NP-трудной в обычном смысле (см. [1]). В [2] предложен псевдополиномиальный алгоритм решения с трудоемкостью O(n4Zpj) операций. В [3], [4] построены алгоритмы решения задачи, которые были протестированы для примеров при n < 600 (тестовые примеры из [5]). Исследование приближенных алгоритмов решения задачи было проведено в [6], где построены примеры, на которых известные приближенные алгоритмы находят решение с относительной погрешностью целевой функции порядка размерности примера n.
В настоящей работе исследуется частный случай задачи, когда параметры требований удовлетворяют условиям
Pi Pn, di <...< dn. (1)
Данный случай является NP-трудным в обычном смысле (см. [7]). Подходы к решению данной задачи были предложены в [8], [9]. Здесь предлагается процедура разбиения множества требо-
1) Работа выполнена в рамках научной школы академика Ю.И. Журавлёва (НШ-5833.2006.1).
ваний произвольного примера задачи, удовлетворяющего условиям (1), и последующего его решения с учетом количества подмножеств, полученных с помощью процедуры разбиения.
Мы полагаем, что классу примеров, параметры требований которых удовлетворяют условиям (1), принадлежат "наиболее трудоемкие" для решения примеры. В частности, "плохие" (в оригинале bad) примеры из [6] удовлетворяют ограничениям (1). Если p < pj и di < dj, то существует оптимальное расписание п*, при котором обслуживание требования i предшествует обслуживанию требования j, т.е. (i —► j)п* (см. [10]), что является еще одним аргументом в пользу "сложности" случая (1).
2. ПОДХОДЫ К РЕШЕНИЮ ЗАДАЧИ
В работах [2]-[4], [8] применялся декомпозиционный подход к решению примеров общего случая задачи (без ограничений (1) и целочисленности Pj). При этом исходный пример задачи разбивается на множество подпримеров и процесс решения сводится к обходу дерева решения полученных подпримеров.
Без ограничения общности предположим, что требования множества N пронумерованы в порядке неубывания директивных сроков d1 < ... < dn, если dk = dk + ь то pk < pk + j. Через j *(N") обозначим требование с наибольшей продолжительностью обслуживания среди требований множества N с N; если таких требований несколько, то выбирается требование с наибольшим директивным сроком, т.е. j*(N) = argmax{d, : pt = maxpi}. Для сокращения записи j*(N) будем
j е N i е n
обозначать через j *.
Пусть x = ({pj, dj}j е N, t0} пример задачи, для которого требуется построить оптимальное расписание. Подпримером примера x будем называть пару {N t'}, где N с N, N Ф 0, и t' > t0. В случае если величины Cj (п), Tj (п) и F(n) вычисляются для момента времени t' > t0, то будем использовать запись Cj(п, t'), Tj(п, t') и F(n, t') соответственно (при этом cj (п, t') = t' + pj). Будем предполагать, что суммарное запаздывание пустого расписания по = 0 равно т.е. F( по) :=
Определение. Рассмотрим пример (подпример) обслуживания требований множества N с N, N = {1, 2, ..., n'}, с момента времени t > t0. Множество L(N, t') есть множество всех индексов к е е {1, 2, ..., n'}, к>j*(N), таких, что верно следующее:
к
(а) t' + = 1 pj < dk + 1, где + i := +<~,
к -
(б) dt + pj < t' + Zj = 1 pj для всех i = j * (N) + 1, к.
Теорема 1 (см. [8]). Для любого примера (подпримера) ({pj, dj}j 6 N, t0} множество L(N, t0) не пусто.
Декомпозиционная теорема (см. [2], [5], [8]). Для любого примера ({pj, dj}j 6 N, t0} существует оптимальное расписание п* обслуживания требований множества N, при котором (j —► j *)п* для всех требований j е {1, 2, ..., к}\{/ *} и (j * —► j )п*, для всех требований j е {к + 1, 2, ..., n} для некоторого к е L(N, t0).
Опишем алгоритм нахождения оптимального расписания на основе использования декомпозиционной теоремы.
Процедура PorcL(N, t).
0. Дан пример {N, t} с множеством требований N = {1, 2, ..., n} и моментом начала обслуживания t, d1 < . < dn;
1. IF N = 0 THEN п* := пустое расписание, GOTO 5;
2. Найдем требование j * из множества N и множество L(N, t) для этого требования;
3. FOR ALL к е L(N, t) DO:
пк := (ProcL(N\ t'), j*, ProcL(N", t")), где N := {1, 2, к}\{j* }, t := t, N := {к +1, ...,n}, t" := Sk;
4. п* := arg min {F(%, t)};
к е L (N, t)
5. RETURN п*.
Алгоритм A:
п* := ProcL(N, t0).
Необходимо заметить, что для примеров случая (1) правила доминирования, предложенные в [11], не сокращают перебора в дереве поиска. В данной работе мы предлагаем подход к решению задачи, когда исходное множество требований разбивается на подмножества, а затем на основе этого разбиения строится оптимальное расписание.
Процедура разбиения множества требований на подмножества.
0. k := 1, ak := 1;
1. FORj = 2, 3, ...,n DO:
IF dj - dak >Pj THEN Pk :=j - 1; k := k + 1; ak :=j;
2. Pk = n.
Данная процедура однозначно разбивает исходное множество N на k подмножеств, k < n, за O(n) операций. В результате работы процедуры будут выделены подмножества требований Ыъ ..., Mk, где M = {a, a + 1, ..., в}, ax = 1, pk = n. При этом M^...^ Mk = N и Mi ^ Mj = 0, если i Ф j.
Например, для множества из трех требований с параметрами p1 = 10, p2 = 10, p3 = 2, d1 = 7, d2 = 9, d3 = 10 будет получено разбиение на подмножества M1 = {1, 2} и M2 = {3}.
В следующих разделах предлагаются алгоритмы решения задачи в зависимости от значения k (количества подмножеств, выделенных процедурой разбиения).
3. СЛУЧАЙ k = 1
В случае k = 1 параметры требований исходного примера удовлетворяют соотношениям
Pi >• > Pn, d 1 <• < dn, dn - d 1 < Pn, (2)
т.е. dx < ... < dn < dx + pn.
Нами были построены примеры (см. [7]) случая (2), для которых алгоритм A находит оптимальное расписание за O(n2(n - 1)/3 - х) операций.
Введем следующее обозначение: dj(t) = dj - dn + t - t0, j e N. При учете (2) для любого t е U выполняется d1(t) < ... < dn(t) < d1(t) + p1. Известно, что для двух примеров с одинаковыми наборами продолжительностей обслуживания требований x1 = {{pj, dj}j е N, t) и x2 = ({pj, dj + C}je N, t + C), где C - некоторая константа, множества оптимальных расписаний и оптимальные значения целевой функции совпадают. Такие примеры xx и x2 будем называть равными примерами. Согласно определению величин dj(t), пример {{pj, aj(t)}j е N, 0) равен примеру {{pj, dj }е N, dn - t + t0)). Также пример {{pj, dj(t)}j e N, 0) при t = dn равен исходному примеру {{pj, dj}j e N, t0). Если t < t0 + pn, тогда для примера {{pj, dj(t)}j e N, 0) будем иметь dj(t) < dn(t) = t - t0 <pn <pj, j e N. В этом случае при любом расписании, построенном с момента времени 0, все требования множества N будут запаздывать, поэтому оптимальным будет SPT (shortest processing йте)-расписание (n, n - 1, ..., 1). Если t > t0 +
nn
+ ^pj, то для примера {{pj, dj(t)}je N, 0), учитываяpn > dn - d1, будем иметь t+pn > t0 + ^pj + dn - d1. j=i j=i Отсюда следует неравенство
n
£ p} - pn < d 1- dn + t - to = di (t)< dj (t), j e N,
j = 1
т.е. при любом расписании запаздывающим будет не более одного требования, которое обслуживается последним по порядку, поэтому EDD (earliest due date)-расписание (1, 2, ..., n) будет оп-
n
тимальным. Таким образом, при изменении t от t0 + pn до t0 + £ pj оптимальное расписание для
j = 1
примера {{pj, dj(t)}j eN, 0) изменяется от (n, n - 1, ..., 1) до (1, 2, ..., n). Интересно выяснить в каких точках происходит изменение оптимального расписания и как много таких точек. Приведем алгоритм решения примеров, параметры требований которых удовлетворяют условиям (2).
Пусть п (г) и р (0 - оптимальное расписание и соответствующее ему значение суммарного запаздывания для примера с множеством требований N = {/, I + 1, ..., п}, моментом начала обслуживания, равным 0, и дире
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.