Приближенные схемы Задачи теории расписаний

Полиномиальная приближенная схема (PTAS) Семейство приближенных алгоритмов для задачи Π, {A ε } ε называется полиномиальной приближенной схемой, если алгоритм A ε (1+ε)-приближенный алгоритм и время его работы ограничено полиномом от размера входа при фиксированном ε.

Вполне полиномиальная приближенная схема (FPTAS) Семейство приближенных алгоритмов для задачи Π, {A ε } ε называется вполне полиномиальной приближенной схемой, если алгоритм A ε (1+ε)-приближенный алгоритм и время его работы ограничено полиномом от размера входа и 1/ε.

Как построить PTAS Упрощение примера I. Разбиение пространства решений. Структурирование работы алгоритма A. Пример I Алгоритм AРешение A(I)

Упрощение примера I. Первая идея превратить трудный пример в более простой в котором легче найти оптимальное решение. Затем мы используем оптимальное решение простого примера для получения приближенного решения для трудного примера. Упростить Решить OPT # Вернуться OPT App I I #

P2||C max J={1,..., n} – работы. {M 1, M 2 } – одинаковые машины. j : p j > 0 (i=1,…, n). Каждая работа должна быть выполнена на одной из двух машин. Минимизировать длину расписания (C max ). Прерывания запрещены. Каждая машина обслуживает не более одной работы одновременно.

Нижняя оценка

Как упростить пример? ( I I # ) Big = { j J| p j εL} –Новый пример I # содержит все большие работы из I. Small = { j J| p j < εL} –Пусть X= Σ j Small p j. –Новый пример I # содержит X/εL работ длины εL. Маленькие работы, как бы склеиваются вместе и разрезаются на маленькие одинаковые кусочки.

Оценка на оптимум Лемма 6.1 OPT(I # ) (1+ ε)OPT(I).

Доказательство X i – размер всех маленьких работ, выполняемых на машине M i в оптимальном расписании для I. Оставим все большие работы на тех машинах, где они были в оптимальном расписании. Заменим все маленькие работы на машине M i на X i /εL работ длины εL. X 1 /εL + X 2 /εL X 1 /εL + X 2 /εL = X/εL X i /εL εL – X i (X i /εL + 1) εL – X i εL OPT(I # ) OPT + εL (1+ ε)OPT(I)

Как решить упрощенный пример? Как много работ в I # ? p j εL для всех работ в I #. Общая длина всех работ в I # p sum 2L. Число работ в I # 2L/εL= 2/ε. Число работ в I # не зависит от n! Найдем все возможные расписания. Число различных расписаний 2 2/ε !

Как вернуться к исходной задаче? Пусть σ # – оптимальное расписание для I #. L i # – нагрузка машины M i в σ #. B i # – общая длина больших работ на M i в σ #. X i # – размер всех маленьких работ на M i в σ #. L i # = B i # + X i #.

Процедура ( σ # (I # ) σ(I) ) Большие работы выполняются на той же машине, что и в σ #. Выделим интервал длины X 1 # + 2εL на машине M 1 и X 2 # на машине M 2. Будем последовательно упаковывать маленькие работы в выделенный интервал на M 1, пока не встретим работу, которая туда не поместится. Оставшиеся маленькие работы упакуем в выделенный интервал на M 2.

Оценка качества

Алгоритм PTAS-1 Input ( J={1,..., n}, p: J Z + ) 1)Определим Big = { j J| p j εL} и Small = { j J| p j < εL} 2)Заменим все маленькие работы на машине M i на X /εL работ длины εL. 3)Найдем оптимальное расписание σ # в новом примере I #, перебрав все допустимые назначения работ по машинам. 4)По расписанию σ # построим допустимое расписание σ исходной задачи, используя описанную выше процедуру ( σ # (I # ) σ(I) ). Output (σ )

Точность алгоритма PTAS-1 Теорема 6.2 Алгоритма PTAS-1 – (1+ε)-приближенный алгоритм для задачи P2||C max.

Разбиение пространства решений Вторая идея разбить пространство решений на несколько меньших областей, в которых проще найти хорошее приближенное решение. Решив задачу отдельно для каждой маленькой области и взяв среди них лучшее есть шанс получить хорошее приближенное решение. * * * * * * * * * * *

Общая схема 1.Разбиение на области. 2.Выбор «хорошего» представителя в каждой области. 3.Выбор из множества хороших представителей наилучшего.

P2||C max J={1,..., n} – работы. {M 1, M 2 } – одинаковые машины. j : p j > 0 (i=1,…, n). Каждая работа должна быть выполнена на одной из двух машин. Минимизировать длину расписания (C max ). Прерывания запрещены. Каждая машина обслуживает не более одной работы одновременно.

Как разбить на области Big = { j J| p j εL} Small = { j J| p j < εL} Φ – множество допустимых расписаний Расписание σ Φ – назначение работ на машины. Определим области Φ (1), Φ (2),…согласно назначению больших работ: σ 1 и σ 2 лежат в одной области тогда и только тогда, когда каждая большая работа выполняется в σ 1 на той же машине, что и в σ 2.

Сколько получилось областей? Число больших работ 2L/εL= 2/ε. Число способов разместить большие работы по двум машинам 2 2/ε. Число различных областей 2 2/ε ! Число различных областей зависит от ε и не зависит от размера входа!

Как выбрать «хорошего» представителя? Назначение больших работ зафиксировано в Φ (l). OPT (l) – длина оптимального расписания в Φ (l). B i (l) – общая длина больших работ на M i. T := max{B i (1), B i (2) } OPT (l) Пусть B i (l) начальная загрузка машины M i. Назначим маленькие работы одну за другой по следующему правилу: каждый раз работа назначается на машину с меньшей нагрузкой на этот момент. Полученное расписание σ (l) длины A (l) выберем представителем от Φ (l).

А хорош ли представитель? 1.Если A (l) =T, то A (l) = OPT (l). 2.Пусть A (l) >T. Рассмотрим машину с большей загрузкой в σ (l). Последняя назначенная на нее работа маленькая и ее длина меньше εL. В момент назначения этой работы загрузка этой машины не превышала p sum / 2. A (l) (p sum / 2) + εL (1 + ε)OPT (1 + ε)OPT (l)

Алгоритм PTAS-2 Input ( J={1,..., n}, p: J Z + ) 1) Определим Big = { j J| p j εL} и Small = { j J| p j < εL} 2) Определим области Φ (1), Φ (2),…, Φ (h) согласно назначению больших работ по машинам. 3)Сформируем задачи I (1), I (2),…, I (h), в которых назначение больших работ по машинам фиксировано и задано на входе. 4)Решим каждую из задач I (k), k = 1,…,h, назначая маленькие работы одну за другой на машину с меньшей нагрузкой на текущий момент. 5)Пусть σ* - лучшее из полученных расписаний на шаге 4. Output (σ* )

Точность алгоритма PTAS-2 Теорема 6.3 Алгоритма PTAS-2 – (1+ε)-приближенный алгоритм для задачи P2||C max.

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

P2||C max J={1,..., n} – работы. {M 1, M 2 } – одинаковые машины. j : p j > 0 (i=1,…, n). Каждая работа должна быть выполнена на одной из двух машин. Минимизировать длину расписания (C max ). Прерывания запрещены. Каждая машина обслуживает не более одной работы одновременно.

Краткая запись решения Обозначим через σ k допустимое расписание k первых работ {1,..., k}. Закодируем расписание σ k с нагрузками машин L 1 и L 2 двумерным вектором [L 1, L 2 ]. Пусть V k обозначает множество векторов, соответствующих допустимым расписаниям k первых работ {1,..., k}.

Алгоритм «Динамическое программирование» Input ( J={1,..., n}, p: J Z + ) 1) Положим V 0 ={[0,0]}, i=0. 2) While i n do: для каждого вектора [x,y] V i добавить вектора [x + p i,y] и [x,y + p i ] в V i+1 ; i:= i +1; 3) Найти [x*,y*] V n, который минимизирует величину max [x,y] V n {x,y} Output ([x*,y*])

Трудоемкость алгоритма Координаты всех векторов целые числа от 0 до p sum. Число различных векторов в V i ограничено (p sum ) 2. Общее количество векторов, вычисляемых алгоритмом не превосходит n(p sum ) 2. Трудоемкость алгоритма O(n(p sum ) 2 ). Размер входа |I| ограничен O(log(p sum ))=O(ln(p sum )) или O(n log p max ). Трудоемкость алгоритма не ограничена полиномом от размера входа!

Как упростить множество векторов? Все вектора соответствуют точкам плоскости в квадрате [0, p sum ]×[0, p sum ]. Разделим этот квадрат вертикальными и горизонтальными линиями на клетки (квадратики). В обоих направлениях линии имеют координаты Δ i, где Δ = 1+ (ε/2n), i = 1, 2, …, K. K = log Δ (p sum ) = ln(p sum )/ln Δ = ((1+2n )/ε) ln(p sum )

Отсев векторов Пусть два вектора [x 1,y 1 ] и [x 2,y 2 ] попали в одну клетку. x 1 /Δ x 2 x 1 Δ и y 1 /Δ y 2 y 1 Δ. Из каждой клетки, имеющей непустое пересечение с V i, выберем один вектор и добавим его в «урезанное» множество векторов V i #.

Алгоритм FPTAS Input ( J={1,..., n}, p: J Z + ) 1) Положим V 0 # ={[0,0]}, i=0. 2) While i n do: для каждого вектора [x,y] V i # добавить вектора [x + p i,y] и [x,y + p i ] в V i+1 ; i:= i +1; Преобразовать V i в V i #. 3) Найти [x*,y*] V n #, который минимизирует величину max [x,y] V n # {x,y} Output ([x*,y*])

Трудоемкость алгоритма FPTAS Множество векторов в V i # содержит не более одного вектора из каждой клетки. Всего клеток K 2. Трудоемкость алгоритма FPTAS O(nK 2 ). nK 2 = n ((1+2n )/ε) ln(p sum ) 2 Алгоритм FPTAS – полиномиален от размера входа и 1/ε.

Оценка на вектора в V i и V i # Лемма 6.4 Для каждого вектора [x,y] V i существует вектор [x #,y # ] V i #, такой что x # Δ i x и y # Δ i y.

Доказательство (по индукции) i =1: (x 1 /Δ x 2 x 1 Δ и y 1 /Δ y 2 y 1 Δ ) i 1 i: Пусть [x,y] V i. Тогда [a,b] V i-1, и либо [x,y]= [a+p k,b], либо [x,y]= [a,b+p k ]. Тогда [a #,b # ] : a # Δ i 1 a, b # Δ i 1 b. Алгоритм FPTAS строит вектор [a # +p k,b # ] и выбирает [α,β], такой что α Δ(a # +p k ) и β Δb #. Имеем α Δ(a # +p k ) Δ i a + Δp k Δ i (a+p k ) =Δ i x и β Δ i y.

Точность алгоритма FPTAS Теорема 6.5 Алгоритма FPTAS – (1+ε)-приближенный алгоритм для задачи P2||C max.

Доказательство

Практика При построении PTAS-1 маленькие работы склеивались в одну и разрезались на одинаковые кусочки. Рассмотрим другой способ построения упрощенного примера. Рассмотрим множество маленьких работ. Если в нем есть две работы длины меньше чем εL склеим их, то есть две работы с длительностями p, p < εL заменим одной работой с длительностью p + p. Продолжим склеивание до тех пор пока в примере останется не больше одной работы с p < εL. Приведет ли такое упрощение к приближенной схеме? –Выполняется ли аналог леммы 6.1 ? –Можно ли оценить число работ в упрощенном примере ? –Как трансформировать оптимальное решение упрощенного примера в приближенное решение исходного примера? 39