2.3.Параллельные машины.Приближенное решение
.pdf
Курс Основы теории расписаний |
07/19 |
Система с параллельными машинами. Приближенное решение задачи на быстродействие. Списочные расписания
Тахонов Иван Иванович
Новосибирский государственный университет Механико-математический факультет
ÍÃÓ, 2015
FPTAS для задачи Pm||Cmax Списочные расписания
Ранее:
Установили, что P m||Cmax NP-трудна, но не в с. смысле.
Установили, что P ||Cmax NP-трудна в с. смысле.
Показали, что P |prmp|Cmax полиномиально разрешима.
Описали псевдополиномиальный точный алгоритм (ДП) для P m||Cmax.
Сегодня:
Опишем F P T AS äëÿ P m||Cmax.
Рассмотрим приближенный (жадный) алг.для P ||Cmax. 
Исследуем свойства полученных расписаний.
Тахонов Иван Иванович |
Параллельные машины. Приближенное решение |
|
|
FPTAS для задачи Pm||Cmax Списочные расписания
FPTAS для задачи P m Cmax
Тахонов Иван Иванович |
Параллельные машины. Приближенное решение |
|
|
FPTAS для задачи Pm||Cmax Списочные расписания
Далее считаем, что длительности всех работ целые числа.
Упорядочим множество работ и рассмотрим задачу с tJ1; : : : ; Jju первыми j работами.
Пусть j некоторое расписание для этой задачи,
Поставим в соответствие j кортеж rt1; t2; : : : ; tms, ãäå
ti время освобождения машины Mi.
Vj trt1; t2; : : : ; tms| кортежу соотв. некот. расп. ju.
Каждому кортежу может соответствовать несколько расп. Будем хранить только одно.
Тахонов Иван Иванович |
Параллельные машины. Приближенное решение |
|
|
FPTAS для задачи Pm||Cmax Списочные расписания
Algorithm 1 (Точного решения P m||Cmax)
Положить V0 tr0; 0; : : : ; 0su. for j 1 Ñ n do
перебрать все rt1; : : : ; ti; : : : ; tms P Vj 1;
@i добавить в Vj кортежи rt1; : : : ; ti pj; : : : ; tms.
Найти P |
Vn |
: |
arg min max t |
. |
|||
t |
|
t |
P |
1¤i¤m |
i |
|
|
|
|
|
|
t |
Vn |
|
|
Восстановить решение. |
|
|
|
||||
|
|
|
|
|
|
|
|
Очевидно, Алгоритм найдет точное решение задачи. Но |
|||
mq, ãäå |
n |
||
pj. |
|||
трудоемкость очень велика: OpnC |
C |
||
j°1
Попробуем упростить.
Тахонов Иван Иванович |
Параллельные машины. Приближенное решение |
|
|
FPTAS для задачи Pm||Cmax Списочные расписания
Элементы множеств Vj точки с целочисленными
sm. Точек много, некоторые из координатами из куба B r0; C
них близки друг к другу и определяют расписания, примерно одинаковые по длине.
Èäåÿ:
разобь¼м B на полиномиальное число параллелепипедов,
модифицируем Алгоритм 1: строим множества Vj1 , содержащие не более одного кортежа из каждой области.
Тахонов Иван Иванович |
Параллельные машины. Приближенное решение |
|
|
FPTAS для задачи Pm||Cmax Списочные расписания
Обозначения |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
" |
|
|
|
Выберем " ¡ 0. Положим 1 |
|
2n . |
N Plog CT. |
|||||||||
I0 t0u, IN r |
N 1 |
|
|
|
k 1 |
; |
kq, ïðè |
|||||
|
|
; Cs, Ik r |
|
|
|
|||||||
k ¤ N 1. |
|
|
|
|
|
|
|
|
|
|
|
|
Очевидно, |
|
|
|
|
|
|
|
|
|
|
|
|
N |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
I |
k X |
I |
l H ïðè k l, |
|
||||||
k r0; Cs, |
|
|||||||||||
k 0 I |
|
|
|
|
|
|
|
|
|
|
||
|
N |
|
|
|
|
|
|
|
|
|
|
|
|
k не содержит целочисленных точек. |
|||||||||||
r0; Csz |
||||||||||||
|
k 0 I |
|
|
|
|
|
|
|
|
|
|
|
Bk1k2:::km Ik1 Ik2 Ikm, âñå ki P t0; 1; : : : Nu. |
||||||||||||
Очевидно, |
|
|
|
|
|
|
|
|
|
|
|
|
|
Bk1k2:::km B |
|
|
|
|
|
||||||
k1;k2;:::;km |
Bk1k2:::km не содержит точек с целочисл. |
|||||||||||
Bz |
|
|||||||||||
k1 |
;k2;:::;km |
|
|
|
|
|
|
|
|
|
|
|
координатами |
|
|
|
|
|
|
|
|
|
|
||
Тахонов Иван Иванович |
Параллельные машины. Приближенное решение |
|
|
FPTAS для задачи Pm||Cmax Списочные расписания
Заметим, что
|
|
2n |
T Q ln C |
||
N Plog C |
ln U ¤ P 1 |
" ln CT. |
Длина входа P m||Cmax ограничена сверху величиной |
||
|
|
|
Opn ° ln pjq=Opn ln Cq. |
|
|
Таким образом, количество параллелепипедов полиномиально |
|||||
от длины входа и 1{": N |
m |
Opp1 2n{" |
qm |
ln |
m |
|
|
Cq. |
|||
Тахонов Иван Иванович |
Параллельные машины. Приближенное решение |
|
|
FPTAS для задачи Pm||Cmax Списочные расписания
Algorithm 2 (FPTAS äëÿ P m||Cmax)
|
|
|
" |
|
|
Выбрать " ¡ 0. Положить 1 |
|
2n , |
N Plog CT. |
||
sm |
íà Bk1k2:::km, ki P t0; : : : ; Nu. |
||||
Разбить B r0; C |
|||||
Положить V01 tr0; 0; : : : ; 0su. |
|
|
|
|
|
for j 1 Ñ n do |
|
|
|
|
|
перебрать все rt1; : : : ; ti; : : : ; tms P Vj1 1;
@i добавить в S кортежи rt1; : : : ; ti pj; : : : ; tms; преобразовать S â Vj1 (удалив лишние векторы).
^ |
|
^ |
|
|
|
|
|
|
P 1 |
|
arg min max t |
. |
|||||
Найти t |
Vn |
: t |
|
|||||
|
|
|
P |
1 |
1¤i¤m |
i |
|
|
|
|
|
|
t |
Vn |
|
|
|
Восстановить решение.
Тахонов Иван Иванович |
Параллельные машины. Приближенное решение |
|
|
FPTAS для задачи Pm||Cmax Списочные расписания
Теорема 1
Алгоритм 2 строит p1 "q-приближенное решение задачи
P m||Cmax с трудоемкостью Opnp1 2n{" |
qm |
ln |
m |
|
Cq. |
Доказательство. Пусть B1 некоторый параллелепипед из разбиения. Заметим, что для любых x; y P B1 верно:
yi{ ¤ xi ¤ yi è xi{ ¤ yi ¤ xi @i P t1; : : : ; mu: (1)
Сравним работу Алгоритмов 1 и 2. Покажем, что для любого x P Vk найдется y P Vk1 :
yi ¤ xi k @i:
Действительно, при k 0 эти множества совпадают. Предположим, утверждение верно для k 1. Докажем для k.
Тахонов Иван Иванович |
Параллельные машины. Приближенное решение |
|
|