авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 | 2 ||

«УДК 519.854.2 Рецензенты: д.т.н., профессор В.Н. Бурков; д.т.н., профессор Д.И. Коган Под редакцией академика РАН С.Н. Васильева Данное ...»

-- [ Страница 3 ] --

Определение 2. Определим множество следующим образом:

= {t|t = rj + x1 · p + x2 · st1 + x3 · st2, j {1, 2,..., n}, x1, x2, x3 {0, 1, 2,..., n}, x2 + x3 x1 }.

Заметим, что множество содержит не более O(n4 ) элементов.

Лемма 3.3. Во всех “сдвинутых влево” расписаниях моменты начала обслуживания требований принадлежат множеству.

Доказательство. Пусть в допустимом “сдвинутом влево” расписании требование jk, 1 k n, является первым требованием, для кото рого Sjk, т.е для предшествующего ему требования jk1 выполнено / Sjk1. Самый ранний из возможных моментов S начала обслужива ния требования jk определяется следующим образом:

S = max{rj, Sj + p}, () k k S = max{rjk, Sjk1 + p + st1 }, () jk1 + p + st2 }. ( ) S = max{r, S jk (*) выполняется, если требования jk и jk1 принадлежат одному и тому же множеству N1 или N2, (**) выполняется, когда jk N2 и jk1 N1, а (***) справедливо для случая, когда jk N1 и jk1 N2. Очевидно, что S. Поскольку Sjk, получаем S Sjk, а значит, расписание не / является “сдвинутым влево”.

3.2.2 Алгоритмы для задач с упорядоченными подмножества ми N1 и N Далее представлены алгоритмы решения следующих задач:

- 1|setup times, N1, N2, pj = p, rj |Cmax ;

- 1|setup times, N1, N2, pj = p, rj | Cj ;

- 1|setup times, N1, N2, pj = p| w j Cj ;

- 1|setup times, N1, N2, pj = p| Tj.

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

Введем обозначения: N1 = {j1, j2,..., jn1 } и N2 = {i1, i2,..., in2 }.

Лемма 3.4. Для всех указанных выше задач существует оптимальное расписание, при котором требования выполняются в одной из следующих последовательностей.

- для задач 1|setup times, N1, N2, pj = p, rj |Cmax и 1|setup times, N1, N2, pj = p, rj | Cj требования из каждого подмножества N1 и N2 обслуживаются в порядке по неубыванию моментов поступ ления, т.е. rj1 rj2 · · · rjn1 и ri1 ri2 · · · rin2 ;

- для задач 1|setup times, N1, N2, pj = p| wj Cj требования из каждого подмножества N1 и N2 обслуживаются в порядке по невоз растанию весов, т.е. wj1 wj2 · · · wjn1 и wi1 wi2 · · · win2 ;

- для задач 1|setuptimes, N1, N2, pj = p| Tj требования из каждо го подмножества N1 и N2 обслуживаются в порядке по неубыванию директивных сроков, т.е. dj1 dj2 · · · djn1 и di1 di2 · · · din2.

Доказательство. Лемма может быть легко доказана следующим обра зом. Если в оптимальном расписании два требования, принадлежащие одному и тому же подмножеству N1 или N2, обслуживаются с наруше нием указанного порядка, то в расписании их можно поменять местами без увеличения значения целевой функции.

Далее представлен алгоритм решения задачи 1|setup times, N1, N2, pj = p, rj |Cmax, и дается объяснение, как он может быть использован для решения других рассматриваемых задач.

Предположим, что требования в N1 и N2 упорядочены в соответствии с леммой 3.4. В алгоритме одно за другим рассматриваются требования i1, i2,..., in2. Для каждого требования ik, k = 1, 2,..., n2, необходимо рассмотреть все позиции l, l = 0, 1, 2,..., n1, где позиция l означает, что требование jl предшествует требованию ik в конструируемом расписании, и ik предшествует требованию jl+1. Если для требования ik выбрана по зиция l, то для требования ik+1 могут быть рассмотрены только позиции l, l + 1,..., n1 (см. лемму 3.4).

Здесь (F, opt ) := Sequence(1, 0, p), где opt оптимальная последо вательность обслуживания требований, F = Cmax минимальное время окончания обслуживания всех требований.

Оценим трудоемкость алгоритма. Множество требований для которых еще не составлено расписание, являющиеся аргументами рекурсивной процедуры, имеют вид {jl+1, jl+2,..., jn1, ik, ik+1,..., in2 }, Algorithm 2 Function Sequence(k, l, Sik1 ) 1: if k = n2 + 1 then Назначить обслуживание требований jl+1, jl+2,..., jn1 с момента времени 2:

Sik1 + p + st1 согласно алгоритму (3.2);

3: := (jl+1, jl+2,..., jn1 ) Вернуть пару (Cjn1, );

4:

5: end if 6: if l = n1 then Назначить обслуживание требований ik, ik+1,..., in2 с момента времени Sik1 + 7:

p соласно алгоритму (3.2);

8: := (ik, ik+1,..., in2 ) Вернуть пару (Cin2, );

9:

10: end if 11: S := Sik1 ;

12: fmin := ;

13: min := ();

14: for pos := l to n1 do 15: if pos = l then 16: Sik := max{rik, S + p};

S := S + p + st1 ;

17:

18: (f, ) := Sequence(k + 1, l, Sik );

19: else 20: Sjpos := max{rjpos, S};

21: Sik := max{rik, Sjpos + p + st2 };

22: (f, ) := Sequence(k + 1, pos, Sik );

23: S := Sjpos + p;

24: end if 25: if fmin f then fmin := f ;

26:

27: min := (jl+1,..., jpos, ik, ) 28: end if 29: end for 30: Вернуть пару (fmin, min );

т.е. множества точно определяются парой индексов (k, l). Аргу менты Sik1 принадлежат множеству. Следовательно, процедура Sequence(k, l, Sik1 ) будет вызвана не более O(n6 ) раз. Трудоемкость про цедуры составляет O(n) операций. Таким образом, трудоемкость алорит ма 2 составляет O(n7 ) операций.

В соответствии с леммой 3.4 алгоритм 2 строит оптимальную после довательность обслуживания требований за время O(n7 ).

Процедура может быть легко модифицирована для решения задачи ST RSP 2|rj |Cmax. Для этого необходимо изменить строки 4 и 9 процеду ры Sequence:

4. Вернуть пару (Cjn1 + T AILlef t, );

...

9. Вернуть пару (Cin2 + T AILright, );

Для решения задачи 1|setup times, N1, N2, pj = p, rj | Cj в процедуру необходимо внести следующие изменения:

n 4. Вернуть пару ( x:=l+1 Cjx, ), где Cjx время окончания обслужи вания требования jx при частичном расписании, полученном из по следовательности, где требования обслуживаются с момента вре мени Sik1 + p + st1 ;

...

n 9. Вернуть пару ( Cix, ), где Cix время окончания обслужива x:=k ния требования ix при частичном расписании, полученном из после довательности, где требования обслуживаются, начиная с Sik1 +p;

...

25. If fmin f + fcurrent Then,// где fcurrent общее вре мя окончания обслуживания требований из последовательности (jl+1,..., jpos, ik ), обслуживание которых начинается с момента вре мени Sik1 + p;

26. fmin := f + fcurrent ;

Напомним, что для задачи 1|setup times, N1, N2, pj = p, rj | Cj требо вания множеств N1 и N2 должны быть упорядочены согласно лемме 3.4.

Аналогично процедура может быть модифицирована для решения задач 1|setup times, N1, N2, pj = p| wj Cj и 1|setup times, N1, Tj. Заметим, что для этих двух задач || = O(n3 ), т.к. все N2, pj = p| моменты появления работ равны 0, т.е. сложность модифицированных алгоритмов будет равна O(n6 ) операций. Таким образом, имеем следую щую лемму.

Лемма 3.5. С помощью алгоритма 2 и его модификаций следующие задачи могут быть решены за время O(n7 ) или O(n6 ):

- 1|setup times, N1, N2, pj = p, rj |Cmax и ST RSP 2|rj |Cmax ;

- 1|setup times, N1, N2, pj = p, rj Cj и ST RSP 2|rj | Cj ;

- 1|setup times, N1, N2, pj = p| wj Cj и ST RSP 2|| w j Cj ;

- 1|setup times, N1, N2, pj = p| Tj и ST RSP 2|| Tj.

3.2.3 Задачи с частично упорядоченными подмножествами Лемма 3.6. Для задачи 1|setup times, N1, N2, pj = p| wj Uj суще ствует оптимальное “сдвинутое влево” расписание, в котором все неза паздывающие требования из одного и того же множества N1 или N2 упо рядочены по неубыванию директивных сроков, т.е. dj1 dj2 · · · djn и di1 di2 · · · din2.

Лемма 3.7. Предположим, что требования упорядочены в соответствии с леммой 3.6. Для задачи 1|setuptimes, N1, N2, pj = p| Uj существует оптимальное “сдвинутое влево” расписание и такие индексы x, 1 x n1 и y, 1 y n2, что только требования jx, jx+1,..., jn1, iy, iy+1,..., in не запаздывают и обслуживаются в порядке согласно лемме 3.6.

Обе леммы могут быть доказаны по аналогии с леммой 3.4.

Таким образом, для задачи 1|setup times, N1, N2, pj = p| Uj необ ходимо найти индексы x и y такие, что x + y min и требования jx, jx+1,..., jn1, iy, iy+1,..., in2 могут быть выполнены вовремя (без за паздывания) в начале расписания. Следовательно, нужно рассмотреть не более (n1 + 1) log(n2 + 1) пар (x, y). Для каждой из пар решается задача 1|setup times, N1, N2, pj = p| Tj с множеством требований {jx, jx+1,..., jn1, iy, iy+1,..., in2 } с помощью модификации алгоритма 2.

Если Tj = 0, то пара (x, y) допустима.

Лемма 3.8. Задача 1|setup times, N1, N2, pj = p| Uj разрешима за время O(n7 log n).

Для задачи 1|setup times, N1, N2, pj = p| wj Uj предлагается поли номиальный алгоритм динамического программирования. Алгоритм ос нован на следующих предположениях. Обозначим требования из N = {H1, H2,..., Hn }, где wH1 wH2 · · · wHn. Если wHk = wHk+1, то dHk dHk+1. Требования из N1 и N2 обозначены и упорядочены в со ответствии с леммой 3.6. Пусть Hn N2 и Hn = ik. Для Hn позиция в расписании определяется парой (t, l), где t время начала обслужи вания требования, а индекс l = 0, 1,..., n1 означает, что обслуживание незапаздывающих требований из множества {j1, j2,..., jl } предшествует обслуживанию требования Hn при расписании, а незапаздывающие тре бования из множества {jl+1, jl+2,..., jn1 } обслуживаются после обслужи вания требования Hn. Позиция (, n1 + 1) означает, что требование Hn запаздывает и обслуживается в конце расписания с некоторого момента времени T.

Таким образом, для каждой позиции (t, l) среди O(n4 ) возможный по зиций, мы можем разделить исходную задачу на две независимые под задачи:

- с множеством требований Nlef t = {j1, j2,..., jl, i1, i2,..., ik1 }, кото рые должны быть обслужены в интервале [0, t);

{jl+1, jl+2,..., jn1, -с множеством требований Nright = ik+1, ik+2,..., in2 }, которые должны быть обслужены в интервале [t + p, T ).

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

Algorithm 3 Function SequenceW U (h, t1, t2, I1, I2, k1, k2, l1, l2 ) 1: fmax := ;

// взвешенное число незапаздывающих требований;

2: max := {};

3: if Hh N1 then 4: I = 1;

5: if I1 = 1 then tmin := t1 ;

6: if I1 = 2 then tmin := t1 + st2 ;

7: if I1 = 0 then tmin := 0;

8: if I2 = 1 then tmax := t2 p;

9: if I2 = 2 then tmax := t2 p st1 ;

10: if I2 = 0 then tmax := Tmax ;

11: pos1 := k1 ;

pos2 := k2 ;

12: else 13: I = 2;

14: if I1 = 1 then tmin := t1 + st1 ;

15: if I1 = 2 thentmin := t1 ;

16: if I1 = 0 then tmin := 0;

17: if I2 = 1 then tmax := t2 p st2 ;

18: if I2 = 2 then tmax := t2 p;

19: if I2 = 0 then tmax := Tmax ;

20: pos1 := l1 ;

pos2 := l2 ;

21: end if 22: for pos := pos1 to pos2 do 23: for each t, tmin t tmax, t + p dHh do 24: if Hh N1 then 25: Пусть jl = Hh ;

26: (1, f1 ) := SequenceW U (h 1, t1, t + p, I1, I2, k1, pos, l1, l2 1);

27: (2, f2 ) := SequenceW U (h 1, t + p, t2, I1, I2, pos + 1, k2, l1 + 1, l2 );

28: else 29: Пусть ik = Hh ;

30: (1, f1 ) := SequenceW U (h 1, t1, t + p, I1, I2, k1, k 1, l1, pos);

31: (2, f2 ) := SequenceW U (h 1, t + p, t2, I1, I2, k1 + 1, k2, pos + 1, l2 );

32: end if 33: if f1 + f2 + wHh fmax then 34: fmax := f1 + f2 + wHh ;

35: max := 1 2 {(h, t)};

36: end if 37: end for 38: end for 39: // Дополнительно рассматриваем случай, когда требование Hh запаздывает.

40: (1, f1 ) := SequenceW U (h 1, t1, t2, I1, I2, k1, k2, l1, l2 );

41: if f1 fmax then 42: fmax := f1 ;

43: max := 1 {(h, Tmax )};

44: end if 45: Вернуть пару (fmax, max );

Здесь Tmax = max{t|t }, (F, SCHEDU LEopt ) := SequenceW U (n, 0, Tmax, 0, 0, 0, n2, 0, n1 ), где SCHEDU LEopt недопустимое расписание, которое может быть трансформи ровано в оптимальное путем изменения расписания для тре бований, обслуживание которых назначено с момента време wj (1 Uj ) ни Tmax, F = максимальное взвешенное чис ло незапаздывающих требований. Отметим, что для задачи wj Uj мощность множества || = O(n3 ), 1|setuptimes, N1, N2, pj = p| поскольку все моменты поступления требований равны 0.

Несложно оценить трудоемкость данного алгоритма. Множества неупорядоченных требований, выступающие в качестве аргументов ре курсивной процедуры, имеют вид N = {jl1, jl1 +1,..., jl2, ik1, ik1 +1,..., ik2 }, {Hh+1, Hh+2,..., Hn } =, N т.е. они точно задаются пятью индексами h, k1, k2, l1, l2. Аргумен ты t1, t2 принадлежат множеству. Таким образом, процедура SequenceW U (h, t1, t2, I1, I2, k1, k2, l1, l2 ) выполняется не более O(n5+3+3 ) раз. Трудоемкость рекурсивной процедуры составляет O(n4 ) операций.

Следовательно, время работы алгоритма 3 составляет O(n15 ) операций.

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

Железнодорожная Соответствующая задача для Сложность задача одного прибора алгоритма O(n7 ) ST RSP 2|rj |Cmax 1|setup times, N1, N2, pj = p, rj |Cmax O(n7 ) ST RSP 2|rj | Cj 1|setup times, N1, N2, pj = p, rj Cj O(n6 ) ST RSP 2|| wj Cj 1|setuptimes, N1, N2, pj = p| wj Cj O(n6 ) 1|setup times, N1, N2, pj = p| Tj ST RSP 2|| Tj O(n7 log n) 1|setup times, N1, N2, pj = p| Uj ST RSP 2|| Uj O(n15 ) ST RSP 2|| wj Uj 1|setuptimes, N1, N2, pj = p| wj Uj Таблица 3.3. Сложность предложенных алгоритмов для разных типов задач 3.3 Задача минимизации максимального взвешенно го временного смещения выполнения заказа для двух станций Имеется две станции, соединенные двухпутной железной дорогой.

Необходимо выполнить множества заказов N 1 = {J1,..., Jn } и N 2 = 1 2 {J1,..., Jn } на поставку грузов между станциями. Заказы множества N 1 необходимо доставить с первой станции на вторую, а заказы множе ства N 2 со второй на первую.

Каждый заказ состоит из одного вагона. Все вагоны однотипные. Так как железная дорога двухпутная, то расписания для множеств N 1 и N составляются отдельно. Рассматриваемое множество для простоты обо значим N = {J1,..., Jn }. Пусть rj время поступления заказа Jj на станцию. Без потери общности предположим, что заказы пронумерованы в порядке их поступления. Каждый заказ имеет свою ценность wj 0.

Доставка вагонов с одной станции на другую осуществляется соста вами, каждый из которых состоит из k вагонов. Пусть p время дви жения состава между станциями, а время, которое должно разде лять моменты отправки двух поездов. Движение пассажирских поездов и плановые ремонтные работы путей учитываются в модели как допу стимые интервалы отправки [1, 1 ], [2, 2 ],..., [z, z ]. Поезда могут быть отправлены только в момент времени, принадлежащий одному из этих интервалов.

Каждый заказ имеет директивный срок dj = rj + момент време ни, до которого заказ может быть доставлен на станцию назначения без опоздания, где запас времени на доставку.

n Все заказы должны быть обслужены q поездами, где q = k. Пусть время доставки заказа Jj N. Целевая функция задачи записыва Cj ется как Lmax = max(wj (Cj dj )).

j=1,n Расписание, удовлетворяющее минимуму данной целевой функции, будем называть оптимальным и обозначать (N ).

Рис. 3.3. Оптимальное расписание примера Пример 3.3.0.1. Рассмотрим следующий пример задачи. Пусть n = 6, k = 2, p = 4, = 4, = 2, r1 = r2 = 0, r3 = r4 = 1, r5 = r6 = 3, w1 = 3, w2 = w3 = w4 = 10, w5 = 30, w6 = 5. Оптимальное расписание для данного примера проиллюстрировано на рис. 3.3.

Здесь начало прямоугольника время отправки поезда, конец вре мя прибытия. Цифры внутри прямоугольника обозначают номера зака зов, перевозимых поездом. Значение целевой функции равно 15 и дости гается на заказе J1.

3.3.1 Задача минимизации общего времени выполнения зака зов при ограничении на максимальное взвешенное вре менное смещение Решим вспомогательную задачу. Пусть задано множество заказов N и положительное число y. Задача заключается в составлении расписания (N, y) удовлетворяющего условию min max(Cj )| max(wj (Cj dj )) y.

j=1,n j=1,n Введем дополнительные обозначения. Для данного значения y для каждого заказа j может быть определён момент времени tj, до которого данный заказ должен быть отправлен. Из ограничения на максимальное временное смещение имеем:

y y wj (Cj dj ) = wj (Cj rj ) Cj + rj +.

wj Так как с момента отправки заказа до прибытия его на станцию на значения требуется время p, то получаем условие на момент отправки заказа j:

y y tj = C j p + rj + p t j + rj + p.

wj wj Следовательно, задача может быть сформулирована следующим об разом. Имеется множество n = kq заказов, для каждого из которых опре делены момент поступления rj и момент обязательной отправки tj, после которого будет нарушено ограничение сверху на максимальное взвешен ное временное смещение. Необходимо максимально быстро перевезти за казы на q поездах, каждый из которых вмещает ровно k заказов и тратит на дорогу время, равное p, так чтобы каждый заказ был доставлен по ездом, отправляющемся в промежутке [rj, tj ).

Алгоритм решения задачи Введем семейство множеств S1 S2 · · · Sq заказы, которые должны уехать первым поездом (S1 ), первым или вторым поездом (S2 ), первым или вторым или третьим (S3 ) и т.д. Заметим, что до начала ра боты алгоритма построения (N, y) не пусто только множество Sq, ко торое состоит из всех n = kq заказов. Введем функцию r(X) = max(ri ), Ji X где X некоторое множество заказов. Обозначим также за Xi подмно жество множества X, состоящее из первых (в порядке поступления) i заказов множества X.

Для поезда с номером m, имеющего текущее значение момента от правки tm, обозначим за tm наименьший момент времени, принадле жащий допустимому интервалу отправки, для которого выполняется tm tm +.

Задача построения расписания (N, y) может быть решена с помо щью алгоритма динамического программирования. Алгоритм основан на следующих достаточно очевидных, но важных свойствах задачи.

Свойство 1. В расписании (N, y) момент времени tm отправки поезда с номером m должен удовлетворять следующим условиям:

(i) если в момент отправки доступно больше чем k вагонов, то отправ ляются вагоны с меньшим значением t ;

(ii) поезд с номером m не может отправиться раньше момента tm max(rk·m, r(Sm ), tm1 );

(iii) все заказы Jl, для которых выполняется tm tl должны уехать одним из поездов с номерами от 1 до m т.е. Jl Sm ;

(iv) после отправки m-ого поезда все заказы из множества Sm должны быть отправлены.

Условие (i) следует из того, что, если есть 2 заказа a и b такие, что ta tb, то заказ a может быть отправлен в одном поезде с заказом b либо более поздними поездами.

Условие (ii) справедливо, поскольку поезд m не может быть отправлен до того момента, как:

поступит k · m заказов;

поступят все заказы из Sm ;

(m 1)-ый поезд освободит пути.

Условие (iii) следует из того, что поезд, отправляющийся в момент вре мени tm, делает невозможным отправку следующего поезда до момента tm, а значит, все заказы l, для которых выполняется неравенство tm tl, не смогут отправиться поездами, номер которых больше m. Условие ( iv) следует из определения множества Sm.

Обозначим за Tm текущее множество заказов, перевозимых m-м по ездом.

Алгоритм построения расписания (N, y) заключается в следующем.

На каждом шаге алгоритма производится попытка отправить некоторый поезд m. Для этого выбирается первый момент tm такой, что для него выполняется условие (ii). После этого выбираются k доступных заказов по условию (i). Затем проверяется верность свойства (iii). В случае, если существует заказ Jl такой, что rl tm и tm tl, то согласно условию (iii) мы включаем заказ Jl во множества Sm, Sm+1..., Sq и возвраща емся к проверке условия (ii). Если же такого заказа не существует, то условие (iii) может быть не выполнено только в том случае, если к мо менту времени tm доступно x k неотправленных заказов из множества Sm. Множество этих заказов назовем X 0. Следовательно, x k заказов должны будут отправиться первыми m 1 поездами. Чтобы отправить данные x k заказов первыми m 1 поездами, будем по порядку во мно жествах заказов Tm1, Tm2... искать такие заказы j, что tj tm, до тех пор, пока их количество не достигнет значения x k. Пусть послед ний такой заказ был найден на поезде с номером s. Введем обозначение Tsm1 = Ts · · · Tm1.

множество, состоящее из x k заказов j, j Tsm1, для Пусть X которых верно tj tm, имеющих минимальные моменты t из всех таких j Tsm1.

Далее будем отправлять заказы из множества X = (Tsm1 \X ) X поездами s,..., m. Условие отправки (ii) изменится с учетом того, что отправлять мы можем только заказы из X, тем самым вместо rk·i по явится r(X(is+1)k ). При этом противоречие условию (i) невозможно, так как любые из доступных в этот момент заказов, не принадлежащих X имеют t tm. В случае противоречия условию (iii) происходит измене ние соответствующего множества Si, осуществляется переход к поезду i, и начинается новый шаг.

Если противоречий не встретилось, то отправляем по этим правилам поезда с номерами s,..., m и переходим к следующему шагу отправке поезда m + 1. Алгоритм прерывает свою работу, если на каком-то шаге мощность какого-либо множества Si стала больше k · i.

Данный алгоритм строит расписание (N, y), так как на каждом шаге производится попытка отправить поезд в первый момент време ни, который возможен при текущих условиях, что дает минимальность Cmax, и при этом прерывает свою работу только в случае несоответствия условий, откуда напрямую следует отсутствие допустимого расписания (N, y).

Сложность алгоритма Оценим сложность работы алгоритма. На каждом шаге происходит проверка условий, пополнение множества Sm, изменение моментов ti (не более, чем для q поездов), подсчет заказов, удовлетворяющих определен ным условиям во множествах Ts,..., Tm, формирование множеств X 0, X и X, а также формирование поездов с Ts по Tm. Эти операции имеют трудоемкость O(n2 ). На каждом шаге алгоритма в одно из множеств S1, S2,... Sq1 добавляется не менее 1 заказа. При этом во множестве Sm может находиться не более mk заказов, а значит, количество шагов не больше чем k + 2k + · · · + (q 1)k = k (q1)(q2), т.е. будем иметь O(q 2 k) = O( n ) операций. Тем самым трудоемкость алгоритма, строя k щего расписание (N, y), составляет O( n ) операций.

k 3.3.2 Решение задачи минимизации максимального взвешен ного временного смещения Для построение оптимального расписания (N ) будем действовать следующим образом. Построим расписание, в котором заказы отправ ляются по возрастанию моментов поступления. Тем самым мы получим расписание, удовлетворяющее условию минимума Ci для каждого поез да i. Рассмотрим заказ j1, на котором достигается максимум целевой функции (wj1 Lj1 ).

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

Тогда для того, чтобы улучшить целевую функцию, необходимо отпра вить заказ Jj1 одним из поездов, отправившимся до поезда с номером m1, т.е. необходимо включить заказ Jj1 во множество Sm1 1. Это значит, что если мы построим расписание (N, wj1 Lj1 ), то в нем заказ Jj1 бу дет отправлен одним из поездов, номер которого меньше m1, а целевая функция будет меньше, чем wj1 Lj1 и достигается на заказе Jj2, который идёт поездом m2.

Следующим шагом алгоритма построим расписание (N, wj2 Lj2 ), в котором заказ Jj2 должен быть отправлен поездом с номером меньше, чем m2, а значит, заказ Jj2 попадет во множество Sm2 1. Будем повто рять эту процедуру до тех пор, пока не наступит такой шаг s, что рас писания (N, wjs Ljs ) не существует. Это означает, что не существует расписания со значением целевой функции меньшим, чем wjs Ljs, и при этом существует расписание, полученное на s-м шаге со значением целе вой функции wjs Ljs, следовательно, оно и будет оптимальным. Обозна чим за AddS (j, m) процедуру, которая добавляет заказ Jj во множества Sm, Sm+1,..., Sq, а в случае, когда |Sm | k · m, прерывает работу алго ритма.

Алгоритм (N ) 0. Построить расписание, в котором заказы отправляются по возраста нию моментов поступления.

1. Положить y := max(wj Lj ). Найти j : wj Lj = y, m : Jj Tm и запу jN стить AddS (j, m 1).

2. Запустить Алгоритм (N, y) и перейти на шаг 1.

Заметим, что на каждом шаге происходит перенос заказа, на котором достигнута целевая функция, в одно из множеств S1, S2,..., Sq1, при этом выход заказа из каждого из этих множеств невозможен.

Пусть на некотором шаге достигнуто значение целевой функции на заказе i, отправленном поездом с номером m в расписании (N, ), после чего данный заказ перенесен во множество Sm1. На следующих шагах будут получены расписания вида (N, y), где y, при этом любой поезд с номером m при расписании (N, ) отправлен не позже, чем поезд с номером m при расписании (N, y).

Это следует из того, что все сдвиги, которые производятся при по строении расписания (N, ), будут необходимы и в расписании (N, y).

Поэтому, чтобы целевая функция не стала больше либо равной той, что достигалась в расписании (N, ) на заказе i, должно выполняться усло вие отправки заказа i одним из поездов c номером меньше m, а значит, заказ i останется во множестве Sm1.

Суммарное количество мест во множествах S1, S2,..., Sq1 равняет ся k + 2k + · · · + (q 1)k = O(kq 2 ), а значит, количество шагов равно O(kq 2 ) = O(n2 /k). На каждом шаге мы получаем расписание, для по строения которого необходимо O(n3 /k) операций. Следовательно, общая трудоёмкость составляет O(n6 /k 2 ) операций.

Продемонстрируем работу алгоритма на примере расписания, постро енного в примере 3.3.0.1.

Шаг 1. Строим для данного множества заказов расписание, удовле творяющее условию min(Cmax ), находим значение целевой функции max(wi Li ) и принимаем его за y = 30 (см. рис. 3.4).

i=1,n Шаг 2. Строим расписание (N, y) для множества N = {J1,..., J6 } и y = 30. Определяем моменты ti, i = 1,..., 6: t1 = 10, t2 = 3, t3 = t4 = t5 = 4, t6 = 9. Теперь пытаемся отправить поезда 1, 2,..., q, так, чтобы это не противоречило условиям (i)–(iv).

Заметим, что при отправке поезда 2 возникает противоречие свойству (iii) (см. рис. 3.5).

Рис. 3.4. Расписание min(Cmax ) для множества заказов N В соответствии с условием (ii) получаем t2 = 2, однако есть три заказа, Рис. 3.5. Противоречие свойству (iii) при отправке второго по езда для которых t2 + t3, t4, t5, а значит, мы включаем заказы J3, J4, J во множество S2 и строим множества X 0 = {J3, J4, J5 }, X = {J1 } и X = {J2, J3, J4, J5 } и пытаемся отправить их первыми двумя поездами.

Получаем расписание (N, y), при котором целевая функция max(wL) = 15 достигается на заказе J1 (см. рис. 3.6).

Шаг 3. Строим расписание (N, y) для значения y = 15. Имеем Рис. 3.6. Расписание (N, 30) t1 = 5, t2 = 1.5, t3 = t4 = 2.5, t5 = 3, 5t6 = 6. При отправке первого поезда имеем: t1 = 0, t1 + t2 J2 S1 S2.

При попытке отправить второй поезд сталкиваемся с противоречием условию (iii), т.к. t2 = 2, t2 + t3, t4, t5, следовательно, J3, J4, J5 S2.

Так же как на шаге 2, строим множества X 0 = {J3, J4, J5 }, X = {J1 } и X = {J2, J3, J4, J5 } и пытаемся отправить заказы из множества X первыми двумя поездами.

Так как r3 = r4 = 1, то t1 = 1, а значит, t2 3. Из того, что t2 + t5, получаем противоречие условию (iii) при попытке отправить второй поезд. Отсюда следует, что J1 S2. Но тогда S2 = {J1, J2, J3, J4, J5 } |S2 | 4, а значит расписания (N, 15) не существует.

Следовательно, расписание, полученное на шаге 2, будет оптималь ным, а значение целевой функции будет равно 15.

Рис. 3.7. Противоречие свойству (iii) при построении расписа ния (N, 15) Упражнения С помощью рассмотренного алгоритма построить расписания для задач со следующими параметрами:

Упр. 3.3.2.1. n = 9, k = 3, = 1, p = 3, = 4, [1, 1 ] = [0, 2], [2, 2 ] = [4, +), r = (0, 0, 0, 0, 1, 1, 2, 3, 3), w = (2, 2, 2, 1, 2, 2, 5, 2, 2).

Упр. 3.3.2.2. n = 8, k = 2, = 1, p = 2, = 2, [1, 1 ] = [0, 2], [2, 2 ] = [4, 4.5], [3, 3 ] = [5.5, +], r = (0, 0, 1, 2, 3, 3, 4, 4), w = (1, 1, 5, 5, 1, 1, 2, 2).

Упр. 3.3.2.3. n = 8, k = 2, = 1, p = 2, = 3, [1, 1 ] = [0, +], r = (0, 0, 0, 1, 1, 1, 2, 4), w = (2, 3, 2, 4, 3, 3, 4, 4).

3.4 Полиномиальные алгоритмы задач о станциях на основе сведения к задачам теории расписания для одного прибора В работе [14] описан полиномиальный алгоритм решения класса задач теории расписаний для одного прибора со следующими параметрами:

• требования j поступают на обслуживание в моменты времени rj 0;

• продолжительность обслуживания всех требований равна некото рой константе p;

• требования обслуживаются в группах. Группой считается набор тре бований, обслуживаемых “одновременно” с той точки зрения, что моменты начала и завершения обслуживания всех требований в од ной группе совпадают между собой.

В задаче рассматривается два механизма объединения обслуживания требований в группах.

• Последовательные группы, когда продолжительность обслужива ния (разность между моментами начала и завершения обслужива ния) требований в группе с k требованиями равна kp, т.е. требова ния в одной группе обслуживаются последовательно одно за другим.

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

• Параллельные группы, когда продолжительность обслуживания требований равна p, т.е. требования в одной группе обслуживаются одновременно. Задано максимальное количество b n требований, которые могут быть объединены в одну группу, где n общее ко личество требований.

Для каждого конкретного примера задач указывается, какой из механиз мов (последовательный или параллельный) используется для объедине ния требований в группы.

В качестве целевого функционала рассматривается целый класс функций F, называемых упорядоченными целевыми функциями, со сле дующими свойствами:

• F является прямой суммой некоторых функций от моментов завер шения обслуживания, то есть F = i fi (Ci );

• F является регулярной функцией, то есть i fi является неубываю щей функцией;

• для каждой функции fi существует такой момент времени i, что t i выполняется f (t) = f (i );

• для любых i j, i j и t, функция-разность (fi fj )(t) является неубывающей на отрезке [0, i ].

Без ограничения общности, предположим, что требования пронумерова ны так, что 1 2 · · · n.

Согласно нотации Грэхема и др. [35], такие рассматриваемые задачи обозначаются следующим образом: 1|s batch, rj, pj = p|F (задача для последовательных групп) и 1|p batch, b n, rj, pj = p|F (задача для параллельных групп).

Условиям упорядоченных целевых функций удовлетворяют следую щие критерии: суммарное взвешенное количество запаздывающих тре бований ( wj Uj ), суммарный взвешенный момент завершения обслу живания ( wj Cj ), суммарное запаздывание ( Tj ).

Для указаных задач в последовательном и параллельном случаях в работе [14] предложены алгоритмы динамического типа нахождения точного решения за полиномиальное время. В случае последовательных групп трудоемкость алгоритма составляет O(n14 ) операций, в случае па раллельных групп – O(n8 ) операций.

Идея алгоритма основана на следующих свойствах оптимальных рас писаний.

Лемма 3.9. Для случая последовательных групп в оптимальном распи сании обслуживание требований начинается и заканчивается в моменты времени из множества S = {r + µp + s, {1,..., n}, µ {0,..., n}, {0,..., n}}.

Для случая параллельных групп – из множества P = {r + µp, {1,..., n}, µ {0,..., n}}.

Количество элементов в множествах S и P равно, соответственно, O(n3 ) и O(n2 ).

Введем понятие частичных групп. Частичной группой назвается группа из требований, в которой в действительности упорядочено µ требований, µ. То есть, в частичных группах возможно появление пустых мест, в которых нет никакого требования. Можно сказать, что в этих пустых местах прибор простаивает, но время таких простоев вклю чается в общее время обслуживания требований данной группы.

Пусть Uk (tl, tr ), k n и tl tr, обозначает множество требований j, для которых j k и rj (tl, tr ].

В случае последовательных групп переменными динамического про граммирования являются k, tl, tr, l, r, µr. Каждая их комбинация опре деляет подзадачу для требований из множества Uk (tl, tr ), в которой • частичная группа, содержащая 0 требований из Uk (tl, tr ), начинает ся в tl и завершается в tl + pl ;

• частичная группа, содержащая µr требований из Uk (tl, tr ), начина ется в tr и завершается в tr + pr.

Пусть Sk (tl, tr, l, r, µr ) является минимальным значением целевой функции для указанной подзадачи с последовательными группами. Ес ли расписания, удовлетворяющего условиям подзадачи не существует, то данная величина принимает значение +.

Аналогично, в случае параллельных групп переменными динамиче ского программирования являются k, tl, tr, µr. Их комбинация определя ет подзадачу для требований из множества Uk (tl, tr ), в которой частичная группа, содержащая µr требований из Uk (tl, tr ), начинает обслуживание в момент времени tr.

Пусть Pk (tl, tr, µr ) является минимальным значением целевой функ ции для указанной подзадачи с параллельными группами. Если распи сания, удовлетворяющего условиям подзадачи, не существует, то данная величина принимает значение +.

Работа метода динамического программирования для рассматрива емых задач основана на следующих условиях (реализациях принципа Беллмана).

Лемма 3.10. Для последовательных групп выполяется Sk (tl, tr, l, r, µr ) = min{L, I, R}, где L = Sk1 (tl, tr, l, r, µr ) + fk (k ), I = min,t {Sk1 (tl, t, l,, 1) + fk (t + p) + Sk1 (t, tr,, r, µr )}, R = fk (tr + pr ) + Sk1 (tl, tr, l, r, µr 1) если µr 0, иначе +.

При этом, S0 (tl, tr, l, r, µr ) принимается равным нулю, если tl + pl + s tr и + в противном случае.

Лемма 3.11. Для параллельных групп выполняется Pk (tl, tr, µr ) = min{L, I, R}, где L = Pk1 (tl, tr, µr ) + fk (k ), I = mint {Pk1 (tl, t, b 1) + fk (t + p) + Pk1 (t, tr, µr )}, R = fk (tr + p) + Pk1 (tl, tr, µr 1) если µr 0, иначе +.

При этом, P0 (tl, tr, µr ) принимается равным нулю, если tl + p tr и + в противном случае.

Таким образом, данные условия определяют следующие алгоритмы динамического построение величин Sk и Pk (Алгоритмы 4 и 5).

Algorithm 4 Вычисление величин Sk (tl, tr, l, r, µr ) 1: for k = 1 n do 2: for r = 0 n do 3: for l = 0 n do 4: for µr = 0 r do 5: for tr S do 6: for tl S(tl tr ) do 7: Вычислить значения L, I, R;

8: Sk (tl, tr, l, r, µr ) min{L, I, R};

9: end for 10: end for 11: end for 12: end for 13: end for 14: end for Algorithm 5 Вычисление величин Pk (tl, tr, µr ) 1: for k = 1 n do 2: for µr = 0 b do 3: for tr P do 4: for tl P(tl tr ) do 5: Вычислить значения L, I, R;

6: Pk (tl, tr, µr ) min{L, I, R};

7: end for 8: end for 9: end for 10: end for Трудомкость применения указанных алгоритмов требует O(n14 ) опе раций в случае последовательных групп, и O(n8 ) в случае параллельных групп.

Сформулированные в разделах 2.1.2–2.1.5 задачи о станциях могут быть представлены в виде рассматриваемых задач теории расписаний для случая параллельных групп. В данном представлении в качестве требований выступают вагоны, которые необходимо доставить с одной станции на другую. Обслуживание требований в группе означает вклю чение вагонов в состав, продолжительность обслуживания каждого тре бования равна времени движения состава от одной станции к другой.

В случае с задачей о двух станциях предложенный в [14] алгоритм получения точного решения для параллельных групп применяется непо средственным образом. Таким образом, задача с двумя станциями раз решима за O(n8 ) операций.

Для вариантов из m станций (расположенных последовательно, за мкнутых между собой и для варианта расположения звездой) алгоритм получения точного решения представляет собой расширение основного подхода из [14] на случай динамического перебора решений для частных подзадач из двух станций. Трудоемкость такого подхода оценивается в O(n8m ) операций и является полиномиальной величиной при фиксиро ванном значении m.

Отметим, что качественным выводом из полученных результатов яв ляется теоретическая полиномиальная разрешимость задач о станциях из разделов 2.1.2–2.1.5. Применение полученных алгоритмов для реше ния задач большой размерности представляется невозможно в силу, хотя и полиномиальной, но большой трудоемкости решения.

3.5 Приближённые методы решения задач железно дорожного планирования Некоторые из сформулированных выше задач являются NP-труд ными, в связи с чем возникает проблема поиска приближенных решений в таких задачах. С другой стороны, как было показано в предыдущих па раграфах, рассмотренные задачи железнодорожного планирования мо гут быть сведены к классическим задачам теории расписаний.

Для нахождения решений с гарантированной точностью в похожих за дачах теории расписаний хорошо зарекомендовал себя метод изменения параметров [6], которому посвящён следующий параграф.

3.5.1 Метод изменения параметров Рассмотрим задачу теории расписаний, характеризующуюся набором параметров = {1, 2,..., m }, к примеру, для задачи минимизации суммарного запаздывания в роли параметров выступают времена по ступления заказов rj, продолжительности обслуживания pj и директив ные сроки dj, j = 1,..., n, всего m = 3n параметров.

Индивидуальный пример A задачи полностью характеризуется значе ниями m параметров m и потому может быть рассмотрен как точка в m-мерном пространстве. Значения параметров, относящихся к приме ру A будем обозначать A. Значения целевой функции примера A при некотором расписании будем обозначать через F A ().

Лемма 3.12. Пусть функция (A, B), определенная в пространстве па раметров, при любом расписании удовлетворяет неравенству |F A () F B ()| (A, B), (3.3) тогда F A ( B ) F A ( A ) 2(A, B), (3.4) где A и B оптимальные расписания примеров A и B соответственно.

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

F A ( B ) F A ( A ) |F A ( B ) F B ( B )| + (F B ( B ) F B ( A ))+ +|F B ( A ) F A ( A )| 2(A, B) + (F B ( B ) F B ( A )) 2(A, B).

В ряде случаев функция (A, B) удовлетворяет аксиомам метрики и может быть рассмотрена как расстояние между примерами A и B.

Пусть введена метрика, задающая расстояние между двумя при мерами с различными исходными параметрами и A полиномиально неразрешимый пример. Схема нахождения приближенного решения за ключается в выполнении следующих двух шагов. На первом шаге пара метры примера A изменяются таким образом, чтобы полученный при мер B принадлежал полиномиально (псевдополиномиально) разрешимо му классу примеров. На втором шаге для решения примера B использу ется известный для данного класса примеров полиномиальный (псевдо полиномиальный) алгоритм, затем полученное расписание применяется к примеру A.

Согласно Лемме 3.12 абсолютная погрешность найденного решения не будет превышать удвоенного расстояния (A, B) между примерами A и B. Ясно, что минимальная оценка погрешности будет получена в случае, когда на первом шаге схемы будет найден пример B минимизирующий значение функции (A, B). Таким образом, решение задачи сводится к отысканию для заданного примера A наиболее близкого примера из за данного полиномиально разрешимого класса.

Далее будет рассмотрен вариант схемы для задачи суммарного запаз дывания 1|rj | Tj.

Выберем в качестве целевой функции F () выражение:

max{0, Cj () dj }, (3.5) min Tj () = min jN jN где Cj () момент окончания обслуживания требования j при расписа нии. Для сокращения записи будем опускать (), если понятно о каком расписании идет речь.

Расписание = (j1,..., jn ) называется ранним, если при этом распи сании каждое требование jk, k N начинает обслуживаться в наиболее ранний допустимый момент времени: либо в момент его поступления rjk, либо в момент окончания обслуживания предыдущего требования Cjk1.

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

Лемма 3.13. Пусть у примеров A и B совпадают времена поступления и продолжительности обслуживания требований:

A B rj = rj = rj, pA = pB = pj, j N.

j j тогда для любого расписания справедливо неравенство TjA TjB | |dA dB |.

| (3.6) j j jN jN jN Доказательство.

TjA TjB | | max{0, Cj dA } max{0, Cj dB }| | j j jN jN jN max{0, |dB dA |} |dB dA |, j j j j jN jN где было использовано известное неравенство:


| max{a, b} max{c, d}| max{|a c|, |b d|} для любых действительных чисел a, b и c, d.

Лемма 3.14. Пусть у примеров A и B совпадают времена поступления и директивные сроки требований:

A B rj = rj = rj, dA = dB = dj, j N.

j j тогда для любого расписания справедливо неравенство TjA TjB | n |pA pB |.

| (3.7) j j jN jN jN Доказательство.

TjA TjB | A B | | max{0, Cj d} max{0, Cj dj }| jN jN jN (3.8) A B A B max{0|, Cj Cj |} |Cj Cj |.

jN jN Для раннего расписания имеем |Cj1 Cj1 | = |rj1 + pA rj1 pB | = |pA pB | A B |pA pB |.

j1 j1 j1 j1 j j jN Предположим, что для некоторого jk выполняется k A B |pA pB |, |Cjk Cjk | ji ji i= в этом случае |Cjk+1 Cjk+1 | | max{rjk+1 + pA, Cjk + pA } A B A jk+1 jk+ max{rjk+1 + pB, Cjk + pB }| B jk+1 jk+ max{|pA pB |, |Cjk + pA Cjk pB |} A B jk+1 jk+1 jk+1 jk+ k+ |pA pB | |pA pB |, ji ji j j i=1 jN тогда из (3.8) получаем TjA TjB | A B |pA pB | = n |pA pB |.

| |Cj Cj | j j j j jN jN jN kN jN jN Лемма 3.15. Пусть у примеров A и B совпадают продолжительности обслуживания и директивные сроки требований:

pA = pB = pj, j j dA = dB = dj, j N.

j j тогда для любого расписания справедливо неравенство TjA TjB | n max |rj rj |.

A B | (3.9) jN jN jN Доказательство.

TjA TjB | A B | | max{0, Cj d} max{0, Cj dj }| jN jN jN (3.10) A B A B max{0|, Cj Cj |} |Cj Cj |.

jN jN Для раннего расписания имеем A B A B A B A B |Cj1 Cj1 | = |rj1 + pj1 rj1 pj1 | = |rj1 rj1 | max |rj rj |.

jN Предположим, что для некоторого jk выполняется A B A B |Cjk Cjk | max |rj rj |, jN в этом случае A B A A |Cjk+1 Cjk+1 | | max{rjk+1 + pjk+1, Cjk + pjk+1 } B B max{rjk+1 + pjk+1, Cjk + pjk+1 }| max{|rjk+1 rjk+1 |, |Cjk Cjk |} max |pA pB |, A B A B j j jN тогда из (3.10) получаем TjA TjB | A B A B A B | |Cj Cj | max |rj rj | = n max |rj rj |.

jN jN jN jN jN kN Лемма 3.16. Функция n n A B |pA pB | |dA dB | (A, B) = n · max |rj rj | +n· (3.11) + j j j j jN j=1 j= удовлетворяет свойствам метрики.

Доказательство. Функция (3.11) очевидно является симметричной, неотрицательной и равняется нулю тогда и только тогда, когда A = B.

В силу известных свойств модуля, неравенство треугольника выполня ется для каждого из слагаемых функции (3.11), а значит и для самой функции.

Лемма 3.17. Функция (3.11) при любом расписании удовлетворяет неравенству TjA TjB | (A, B).

| (3.12) jN jN Доказательство. Пусть пример C имеет директивные сроки как у при мера B и одинаковые с примером A времена поступления и продолжи тельности обслуживания требований. Пусть далее, пример D имеет оди наковые с примером B директивные сроки и времена поступления тре бований и одинаковые с примером A продолжительности обслуживания.

Используя леммы 3.13–3.15, получим TjA TjB | | TjA TjC | + | TjC TjD |+ | jN jN jN jN jN jN n TjD TjB | |dA dB | + n · max |rj rj |+ A B +| j j jN j= jN jN n |pA pB | (A, B).

+n · j j j= Согласно леммам 3.12 и 3.17 для функции (3.11) выполняется T A ( B ) ( A ) 2(A, B), (3.13) jN jN где A и B оптимальные расписания примеров A и B соответственно.

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

3.5.2 Метрики для общего случая целевой функции Рассмотрим общий случай аддитивной целевой функции:

(3.14) F () = j (, r1,..., rn, p1,..., pn, dj ).

jN В этом случае метрика может быть построена в виде:

(Rji |rj rj | + Pji |pA pB |) + A B Dj |dA dB |, (3.15) (A, B) = j j j j jN iN jN Здесь где Rji, Pji, Dj – константы Липшица для функций i по перемен ным rj, pj и dj, j, i N.

Аналогичная формула имеет место для случая минимаксной целевой функции:

(3.16) F () = max j (, r1,..., rn, p1,..., pn, dj ).

jN (Rj |rj rj | + Pj |pA pB |) + D max |dA dB |, A B (3.17) (A, B) = j j j j jN jN Обратим внимание, что полученные метрики также являются сепара бельными.

3.5.3 Сведение к задаче линейного программирования Рассмотрим случай, когда некоторый полиномиально разрешимый класс примеров определяется системой линейных неравенств вида A · RB + B · P B + C · DB H, где RB = (r1,..., rn )T, P B = (pB,..., pB )T, DB = (dB,..., dB )T, pB B B 1 n 1 n j 0, rj 0, j N, верхний индексT обозначает транспонирование, A, B, C B – матрицы размера m n, и H – m-мерный вектор.

Тогда для отыскания в полиномиально разрешимом классе примера B, ближайшего к примеру A, достаточно решить следующую задачу ли нейного программирования.

n n p xp ) r r (yj xd ), d min f = n · (y x ) + n · (3.18) (yj + j j j=1 j= при условиях xr rj rj y r, A B x p p A p B yj, p j j j xd dA dB y d, j j j rj 0, pB 0, j N, B j A · RB + B · P B + C · DB H.

В полученной задаче линейного программирования присутствуют 7n + переменных:rj, pB, dB, xp, yj, xd, yj, xr, y r, j = 1,..., n. Для её решения p B d j j j j существуют полиномиальные алгоритмы, поэтому вся схема нахождения приближенного решения в рассматриваемом случае является полиноми альной.

3.5.4 Численные эксперименты Для определения эффективности предложенной схемы была проведе на серия численных экспериментов. Поиск полиномиально разрешимых примеров проводился в следующих классах:

n |pA p|+n·max |rj r|, A • {PR : pj = p, rj = r, j N }, (A, B) = n· j jN j= |pA p| + |dA d|, • {PD : pj = p, dj = d, j N }, (A, B) = n · j j jN jN A |dA d|, • {RD : rj = r, dj = d, j N }, (A, B) = n · max |rj r| + j jN jN |pA p|, • {P : pj = p, j N }, (A, B) = n · j jN A • {R0 : rj = 0, j N }, (A, B) = n · max |rj r|.

jN Рис. 3.8. Плотность распределения модуля разности суммар ных запаздываний примеров, в процентах от значения метри ки.

Здесь, для каждого класса указана функция метрики (A, B), A – произ вольный пример, B – пример принадлежащий соответствующему классу.

В первых трех классах решением является расписание, упорядоченное по неубыванию свободного параметра. Алгоритмы решения задач послед них двух классов представлены в [14] и [7] и имеют сложности O(n7 ) и O(n4 pj ), соответственно.

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

A f (r) = n · max |rj r|.

(3.19) jN Рис. 3.9. Плотность распределения процентных долей частей метрики, зависящих от отдельных параметров.

n |pA p|.

g(p) = n · (3.20) j j= |dA d|.

(3.21) h(d) = j jN • Минимум функции (3.19) достигается в точке r = Лемма 3.18.

A A rmax +rmin A A A A, где rmax = max rj, rmin = min rj.

2 jN jN • Минимум функции (3.20) достигается в точке p {pA,..., pA }.

1 n • Минимум функции (3.21) достигается в точке d {dA,..., dA }).

1 n Рис. 3.10. Плотность распределения реальной погрешности приближенного решения, в процентах от теоретической.

Доказательство. Функция f (r) представима в виде A A A A rmax rmin rmax + rmin A A A n · max |rj r| max{r rmin, rmax r} + |r | = = 2 jN rmax +rmin и очевидно имеет минимум в точке.

Пусть функция g(p) имеет минимум в точке p0, тогда либо f (p0 ) = 0, либо p0 {pA,..., pA }). Поскольку g(p) кусочно-линейная функция, 1 n обращение её производной в нуль означает, что функция является кон стантой на некотором интервале [pA, pA ], k = 1,..., n 1 а значит гра k k+ ничные точки pA и pA также являются точками минимума.

k k+ Последнее утверждение леммы о минимуме функции h(d) доказыва ется аналогично.

Были проведены несколько серий экспериментов. Во всех сериях ис пользовались примеры с параметрами, распределенными равномерно на интервалах [1, 100] для pA, [pj, pj ] для dA и [0, dj pj ] для rj.

A j j jN В первой серии экспериментов проверялись результаты леммы 3.17, влияющей на величину погрешности. Для каждого n = 10, 20,..., генерировалось 10000 пар примеров. Для каждой пары вычислялась ве TjA TjB | | jN jN личина. Также для определения параметров, имеющих наи (A,B большее влияние на функцию метрики вычислялись процентные величи ны вкладов частей метрики, зависящих от продолжительностей обслу живания, директивных сроков и моментов поступления.


Результаты представлены в таблице 3.4. Среднее значение TjA TjB | | jN jN меняется от 5% до 10% при росте n, а части функции мет (A,B рики, зависящие от продолжительностей обслуживания, директивных сроков и моментов поступления дают вклады 35%, 20% и 25% в общую величину функции, соответственно.

Графики полученных плотностей распределения для n = 60 показаны на рис. 3.8 и рис. 3.9.

Вторая серия экспериментов служила проверке метода изменения па раметров непосредственно. Эксперименты проводились по следующей схеме. Рассматривались значения n = 4, 5,..., 10, для каждого n гене рировались по 10000 примеров. К каждому примеру применялась выше описанная схема для нахождения приближенного решения со значени ем целевой функции Fe, затем при помощи алгоритма ветвей-и-границ искалось точное решение с оптимальным значением целевой функции F. Далее вычислялось отношение реальной погрешности схемы = Fe F к её верхней оценке, определяемой неравенством (3.13):

Fe F (3.22) =.

2(A, B) По итогам экспериментов строились зависимости плотности распре деления ошибки для различных n. Типичный вид полученной зависи мости показан на рис. 3.10.

A B | Tj Tj | p r d n 10 11,7% 35,6% 42,3% 20,6% 20 10,4% 39,7% 39,4% 19,4% 40 8,9% 42,4% 37,4% 18,6% 60 7,8% 43,6% 36,6% 18,3% 80 7,3% 44,4% 34,4% 18% 100 6,7% 44,9% 35,7% 17,9% Таблица 3.4. Средняя разница между целевыми функциями и доли составных частей метрики PR PD RD P R n 4 2,5% 4,6% 20,8% 1,8% 2,9% 5 2,6% 4,8% 23,1% 1,9% 2,8% 6 2,6% 4,6% 24,6% 1,9% 2,7% 7 2,6% 4,7% 26% 1,9% 2,5% 8 2,5% 4,6% 27% 2% 2,3% 9 2,4% 4,7% 27,9% 2% 2,2% 10 2,4% 4,6% 28,6% 1,9% 2,1% Таблица 3.5. Средняя экспериментальная погрешность в про центах от теоретической Было обнаружено, что если поиск полиномиально разрешимого при мера ведется в классе RD, то средняя погрешность решения растет от 20% до 30% от верхней оценки (3.13) при увеличении n, это показыва ет, что расписание по возрастанию продолжительностей обслуживание плохо применимо для примеров с выбранным распределением парамет ров. Для остальных классов средняя погрешность решения не зависит от n, и составляет несколько процентов от максимальной теоретической.

Столь малая погрешность обусловлена тем, что примерно в 20% случаев метод изменения параметров давал точное решение задачи. Зависимость средней ошибки от n представлена в таблице 3.5.

Список общих обозначений nij количество вагонов, которые необходимо доставить со станции i на станцию j;

Jijk k-й заказ (вагон) для отправки со станции i на станцию j;

mijk масса вагона;

lijk длина вагона;

hij длина пути между i и j станциями;

dijk директивный срок доставки k-го заказа со станции i на станцию назначения j;

rijk время поступления k-го заказана на станцию i для отправки на станцию j;

pij время передвижения состава между станциями i и j;

Cij момент доставки i-го заказа на станцию j;

L множество локомотивов;

B множество локомотивных бригад;

wi коэффициент значимости;

zi штраф за задержку вагона.

Qin множество поездов, прибывающих на станцию i;

i Qout множество поездов, отбывающих со станции i;

i tin время прибытия на станцию i поеза q;

qi tout время отбытия со станции i поеза q;

qi out вершина отбытия со станции i поезда q в момент tout ;

vit qi in вершина прибытия на станцию i поезда q в момент tin ;

vit qi srt vit вершина сортировки на станцию i поезда q;

amov out in ребро движения поезда (vit, vjt ), соответствующее движению qij поезда q Q со станции i на следующую на его маршруте станцию j;

atr in out ребро стоянки поезда (vit, vit ), соответствующее стоянке поезда qi q Q на промежуточной на его маршруте станции i;

adwn in srt ребро отцепки вагонов (vit, vi,t+ ), соответствующее отцепке ва qi гонов от поезда q Q на находящейся на его маршруте станции i;

aup srt out ребро прицепки вагонов (vi,t, vit ), соответствующее прицепке qi вагонов к поезду q Q на находящейся на его маршруте станции i;

asrtt srt srt ребро сортировки (vit, vit ) между соседними вершинами сорти it ровки станции i;

a fij количество вагонов, “перемещенных” по ребру a из i в j.

+ v, v множества входящих и исходящих рёбер для вершины v.

Литература [1] Бодюл В.И. Математическая модель распределения вагонного парка по железным дорогам в условиях неравномерности грузовых пере возок // Вестник ВНИИЖТ. 2006. №3.

[2] Данциг Дж. Линейное программирование. Его применение и обоб щение M.: Изд-во “Прогресс”, 1966.

[3] Козлов П.А., Владимирская И.П. Пути повышения обоснованности технологических решений // Вестник ВНИИЖТ. 2009. № 3. C.

8–12.

[4] Козлов П.А., Владимирская И.П. Построение систем автоматизи рованного управления потоками вагонов разных собственников // Вестник ВНИИЖТ. 2009. № 6. C. 8– [5] Козлов П.А., Владимирская И.П., Тушин Н.А. Оптимальное управ ление работой вагонов разных собственников // Вестник ВНИИ ЖТ. 2010. № 4.

[6] Лазарев А.А. Теория расписаний. Оценки абсолютной погрешности и схема приближенного решения задач теории расписания. М.:

МФТИ, 2008.

[7] Лазарев А.А., Гафаров Е.Р. Теория расписаний. Минимизация сум марного запаздывания для одного прибора М.: Вычислительный центр им. А.А. Дородницына РАН, 2006.

[8] Левин Д.Ю. Теория оперативного управления перевозочным про цессом. М.: “Транспортная книга”, 2008.

[9] Литвак Б.Л. Алгоритм решения динамической транспортной за дачи. // В кн.: Системы многосвязного управления. М.: Наука, 1977. С.59–69.

[10] Макаров В.Л. Динамическая транспортная задача. // Труды Ле нингр. инж.-экон. ин-та. 1965. вып. 58.

[11] Сурин С.С. Динамическая транспортная задача и некоторые её обоб щения. // В сб.: Методы вычислений. Вып. 3. Л.: Изд-во ЛГУ, 1966.

[12] Acbarya, D., Martland C.D., J. M. Sussman Using Expert Systems and Optimization Techniques for Rail Relay Scbeduling. // Proceedings of the ASCE First International Conference on Advanced Technologies in Transportation Engineering, San Diego CA, Feb., 1989. P. 378-383.

[13] Allahverdi A., Ng C.T., Cheng T.C.E., Kovalyov M.Y. A survey of scheduling problems with setup times or costs. // European Journal of Operational Research. 2008. No. 187. P. 985–1032.

[14] Baptiste Ph. Batching identical jobs. // Math Meth Oper Res. 2000.

No. 52. P. 355–367.

[15] Baptiste Ph., Brucker P., Knust S. and Timkovsky V.G. Ten notes on equal-processing-time scheduling. // 4OR: Quarterly Journal of the Belgian, French and Italian Operations Research Societies. 2004.

V. 2. P. 111–127.

[16] Beaujon G.J., Turnquist M.A. A Model for Fleet Sizing and Vehicle Allocation. // Transportation Science. 1991. No. 25.1. P. 19–45.

[17] Bellman R. Mathematical aspects of scheduling theory // Journal of the Society of Industrial and Applaid Mathematics. 1956. Vol. 4.

P. 168–205.

[18] Billionet A. Using integer programming to solve the train-platforming problem. // Transportation Science. 2003. No. 37(2). P. 213–222.

[19] Borndorfer R., Grotschel M., Lukac S., Mitusch M., Schlechte T., Schultz S., Tanner A. An auctioneng approach to railway slot allocation.

Technical Report 05-45. Konrad-Zuse-Zentrum fur Informationstechnik Berlin, 2005.

[20] Borndorfer R., Schlechte T. Solving railway track allocation problems.

Technical Report 07-20. Konrad-Zuse-Zentrum fur Informationtechnik Berlin, 2007b.

[21] Brannlund U., Lindberg P.O., Nou A., Nilsson J.-E. Railway Timetabling using Lagrangian Relaxation. // Transportation Science.

1998. No. 32.4. P. 358–369.

[22] Brucker P. Scheduling Algorithms. Springer-Verlag. 2001. P. 365.

[23] Cacchiani V., Caprara A., Toth P. A column generation approach to train timetabling on a corridor. // 4OR. 2008. No. 6. P. 125–142.

[24] Cai X., Goh C. J. A fast heuristic for the train scheduling problem. // Computers and Operations Research. 1994. No. 21(5). P. 499–510.

[25] Cai X., Goh C. J., Mees A. I. Greedy heuristics for rapid scheduling of trains on a single track. // IIE Transactions. 1998. No. 30. P.

481–493.

[26] Caprara A., Fischetti M., Toth P. Modelling and solving the train timetabling problem. // Operation Research. 2002. No. 50. P. 851– 861.

[27] Caprara A., Galli L., Toth P. 04. solution of the train platforming problem.// ATMOS 2007 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization and Systems, Dagstuhl, Germany, 2007.

[28] De Luca Cardillo D., Mione N. k l-list colouring of graphs. // European Journal of Operational Research. 1998. No 106. P. 160– 164.

[29] Carey M., Lockwood D. A model, algorithms and strategy for train pathing. // The Journal of Operational Research Society. 1995.

No 46(8) P. 988–1005.

[30] Cornelsen S., Di Stefano G. Track assignment. // Journal of Discrete Algorithms. 2007. No. 5(2). P. 250–261.

[31] Delorme X. Modelisation et resolution de problemes lies a l’exploitation d’infrastructures ferroveiaires. PhD thesis, Universite de Valenciennes et du Hainaut Cambresis, 2003.

[32] Ferreira L., Murray M.H. Modelling Rail Track Deterioration and Maintenance: Current Practices and Future Needs. // Transport Reviews. 1997. No. 17.3. P. 207–221.

[33] Gandibleux X., Jorge J., Angibaud S., Delorme X., Rodriguez J. An ant colony optimization inspired algorithm for the set packing problem with application to railway infrastructure. // In Proceedings of the Sixth Metaheuristics International Conference (MIC2005). 2005. P. 390–396.

[34] Gorman M.F. Operating Plan Model Improves Service Design at Santa Fe Railway. // Interfaces. 1998. No 28.4 P. 1–12.

[35] Graham R.L., Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G.

Optimization and approximation in deterministic machine scheduling:

a survey. // Ann. Discrete Math. 1979. No. 5. P. 287–326.

[36] Higgins A., Ferreira L., Kozan E. Modeling Single-Line Train Operations. // Transportation Research Record. 1995. No. P. 9–16.

[37] Higgins A., Kozan E., Ferreira L. Optimal scheduling of trains on a single line track. // Transportation Research Part B. 1996. No.

30B(2). P. 147–161.

[38] Higgins A., Ferreira L., Kozan E. Modeling Single-Line Train Operations. // Transportation Research Record. 1995. No. 1489.

P. 9–16.

[39] Jha K.C., Ahuja R.K. Sahin G. New Approaches for Solving the Block to-Train Assignment Problem. // Networks. 2008. No. 51(1). P.

48–62.

[40] Jungnickel D. Graphs, Networks and Algorithms. Springer, 2007.

[41] Jovanovic D., Barker P.T. Tactical Scheduling of Rail Operations: The SCAN-I System. // Transportation Science. 1991. No. 25.1. P. 46– 64.

[42] Kantorovich L. On the translocation of masses // C. R. (Doklady) Acad.

Sci. URSS (N. S.). 1942. No. 37. P. 199–201.

[43] Kraay D., Barker P.T., Chen B.T. Optimal Pacing of Trains in Freight Railroads: Model Formulation and Solution. // Operations Research.

1991. No. 39.1. P. 82–99.

[44] Kravchenko S., Werner F. Parallel Machine Problems with Equal Processing Times: A Survey. // Journal of Scheduling. 2011. V.

14. No. 5. P. 435–444.

[45] Kwon O.K., Martland C.D., Sussman J.M. Routing and Scheduling Temporal and Heterogeneous Freight Car Trac on Rail Networks. // Transportation Research. 1998. No. 34E.2. P. 101–115.

[46] LeBlanc L.J. Global Solutions for a Nonconvex Nonconcave Rail Network Model. // Management Science. 1976. No. 23.2. P. 131– 139.

[47] Liebchen C., Mohring R. The modelling power of the periodic event scheduling problem: Railway timetables - and beyond. // Technical Report 2004/20, Technische Universitat Berlin, Institut fur Mathematik. 2004.

[48] Liu S.-Q., Kozan E. Scheduling trains as a blocking parallel-machine job shop scheduling problem. // Computers and Operations Research.

36(10) P. 2840–2852.

[49] Marin A., Salmeron J. Tactical Design of Rail Freight Networks - Part I: Exact and Heuristic Methods. // European Journal of Operational Research. 1996. No. 90, P. 26–44.

[50] Morlok E.K., Peterson R.B. Final Report on a Development of a Geographic Transportation Network Generation and Evaluation Model. // Journal of the Transportation Research Forum. 1970.

No. 11. P. 71–105.

[51] Monge G. Mmoire sur la thorie des dblais et de remblais. Histoire e e e de l’Acadmie Royale des Sciences de Paris, avec les Mmoires de e e Mathmatique et de Physique pour la mme anne.

e e e 1781. P. 666– 704.

[52] Newton H. N., Barnhart C., Vance P. H. Constructing Railroad Blocking Plans to Minimize Handling Costs. // Transportation Science. 1998. No. 32.4. P. 330–345.

[53] Nozick L.K., Morlok E.K. A Model for Medium-Term Operations Planning in an Intermodal Rail-Truck Service. // Transportation Research. 1997. No. 3lA.2. P. 91–107.

[54] Oliveira O., Smith B. M. A job shop scheduling model for the single track-railway timetabling problem. // Technical Report 2000.21, University of Leeds. 2000.

[55] de Oliveira E.S. Solving Single Track Railway Scheduling Problem Using Constraint Programming. //The University of Leeds, School of Computing, PhD Thesis. 2001. P. 129.

[56] Peeters L. Cyclic Railway Timetable Optimization. // PhD thesis, Erasmus Research Institute of Management. 2003.

[57] Powell W.B., Carvalho T.A. Dynamic Control of Logistics Queuing Networks for Large-Scale Fleet Management. // Transportation Science. 1998a. No. 32.2. P. 90–109.

[58] Rodriguez J. A constraint programming for real-time trains scheduling at junctions. // Transportation Research Part B. 2007. No. 41(2) P. 231-245.

[59] Sahin I. Railway trac control and train scheduling based on inter-train conict management. // Transportation Research Part B. 1999. No.

33 P. 511–534.

[60] Sauder R.L., Westerman W.M. Computer Aided Train Dispatching:

Decision Support Through Optimization. // Interfaces. 1983. No.

13.6 P. 24–37.

[61] Serani P., Ukovich W. A mathematical model for periodic scheduling problems. // Society for Industrial and Applied Mathematics Journal on Discrete Mathematics. 1989. No. 2(4). P. 550–581.

[62] Sherali H.D., Suharko A.B. A Tactical Decision Support System for Empty Railcar Management. // Transportation Science. 1998. No.

32.2. P. 306–329.

[63] Sherali H.D., Tuncbilek C.H. Static and Dynamic Time-Space Strategic Models and Algorithms for Multilevel Rail-Car Fleet Management. // Management Science. 1997. No. 43.2. P. 235–250.

[64] Szpigel B. Optimal train scheduling on a single line railway. // Operations Research. 1973. No. 72. P. 344–351.

[65] Turnquist M.A., Markowicz B.P. An Interactive Microcomputer-Based Model for Railroad Car Distribution. // Working Paper, Cornell University, Ithaca, NY. 1989.

[66] Wolsey L.A., Nemhauser G.L. Integer and Combinatorial Optimization. N.Y.: John Wiley & Sons Inc., 1988.

[67] Ziarati K., Soumis F., Desrosiers J., Gelnis S., Saintonge A.

Locomotive Assignment with Heterogeneous Consists at CN North America. // European Journal of Operations Research. 1997. No.

97.2. P. 281–292.

[68] Zwaneveld P. J., Kroon L. G., Romeijn H. E., Salomon M., Dauzere Peres S., van Hoesel S. P. M., Ambergen H. W. Routing trains through railway stations: Model formulation and algorithms. // Transportaion Science. 1996. No. 30(3). P. 181–194.

[69] Zwaneveld P. J., Kroon L. G., van Hoesel S. P. M. Routing trains through a railway station based on a node packing model. // European Journal of Operational Research. 2001. No. 128 P. 14–33.

ЛАЗАРЕВ АЛЕКСАНДР АЛЕКСЕЕВИЧ МУСАТОВА ЕЛЕНА ГЕННАДЬЕВНА КВАРАЦХЕЛИЯ АЛЕКСАНДР ГОНЕРОВИЧ ГАФАРОВ ЕВГЕНИЙ РАШИДОВИЧ ТЕОРИЯ РАСПИСАНИЙ.

ЗАДАЧИ УПРАВЛЕНИЯ ТРАНСПОРТНЫМИ СИСТЕМАМИ Подписано в печать 30.06. Объем 10 п.л. Тираж 25 экз.

Заказ № Оформление обложки: М.А. Лазарев, М.О. Пороснова.

Физический факультет МГУ имени М.В. Ломоносова 119991, Москва, ГСП-1, Ленинские горы, д.1, стр.2.

Отпечатано в отделе оперативной печати физического факультета МГУ

Pages:     | 1 | 2 ||
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.