Построение расписаний в системах обслуживания с блокировками Олег Ефимов магистрант 2008 руководитель Сарванов В.И. доцент каф. ДМиА. - презентация

1 Построение расписаний в системах обслуживания с блокировками Олег Ефимов магистрант 2008 руководитель Сарванов В.И. доцент каф. ДМиА

2 Для огромного множества задач построения расписаний в системах обслуживания часто предполагается, что при перемещении требований от прибора к прибору, если следующий прибор занят, существует т.н. буфер неограниченной вместимости между приборами, где требование может находиться, пока следующий прибор занят. В действительности же, существуют и системы обслуживания, не позволяющие иметь в наличии буферы между приборами. Они получили название систем обслуживания с блокировками. Задача построения расписания в такой системе недавно возникла на Белорусской железной дороге. Актуальность проблемы

3 Определение сложностных статусов задач, возникающих в рассматриваемых системах. Поставленные цели Разработка полиномиальных алгоритмов для задач, принадлежащих классу P. Разработка приближённых полиномиальных алгоритмов с гарантированной оценкой точности для задач, принадлежащих классу NP. Попытаться построить полностью приближённую полиномиальную схему для задач, которые не являются NP-трудными в сильном смысле.

4 Объектом исследования является система обслуживания типа flowshop с блокировкой. Объект и предмет исследования Предмет исследования – оптимальное расписание в системе обслуживания типа flowshop с блокировкой. Оптимизационный критерий – минимизация периода обслуживания.

5 Грузовой фронт состоит из N складов с различными типами продукции, расположенных вдоль железнодорожного пути. На фронт подаются вагоны, каждый из которых должен быть обслужен ровно на одном складе определённого типа. Задано время обслуживания каждого вагона. Каждый склад может одновременно заниматься обслуживанием только одного вагона. Прерывания в обслуживании не допускаются. Необходимо расположить вагоны в таком порядке, чтобы последний вагон покинул фронт как можно ранее.

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

7

8 Складам ставим в соответствие приборы, а вагонам – требования. 0 2 a2a2 a1a1 b3b3 b2b2 b1b1 b4b4 t 1

9 Научные гипотезы В случае системы с двумя приборами с односторонним ограничением на доступ задача является NP-трудной в сильном смысле (результат).результат В случае системы с блокировками с конечным количеством приборов задача принадлежит классу P (результат).результат

10 Теорема. Задача «Построение оптимального расписания в системе обслуживания с односторонним ограничением на доступ» для случая двух приборов является NP-трудной в сильном смысле. Идея доказательства – полиномиальное сведение задачи «3- РАЗБИЕНИЕ» к данной задаче.

11 Идея. Отсортировать требования на 2-ой прибор в порядке неубывания, а требования на 1-ый прибор в порядке невозрастания. Последовательно выбирая из отсортированного списка требования на 1-ый прибор, пытаться ставить их одновременно с выполнением минимального по времени требования на 2-ой прибор так, чтобы сумма времён требований на 1-ом приборе не превосходила времени требования на 2-ом приборе при одновременном обслуживании. Если это оказалось невозможным, то ставить данное требование туда, где сумма требований на 1-ый прибор будет минимально превышать время требования на 2-ой прибор. Алгоритм затрачивает O(n*m) операций.

12 0 2 1 t

13

14 Вспомогательное неравенство. Пусть, причём,, тогда Теорема. Пусть, причём,, – подстановка множества – множество индексов элементов – подстановка множества – множество индексов элементов Тогда минимум функционала достигается при, т.е.

15 Вспомогательное неравенство. Пусть, причём,. Рассмотрим множество подстановок Теорема. Пусть, причём,, Рассмотрим множество подстановок – произвольная подстановка множества – множество индексов элементов Тогда минимум функционала достигается при, т.е., где – произвольная подстановка множества. Тогда, где.

16 На основании вышеприведённых теорем для варианта задачи без тупика существует точный полиномиальный алгоритм. Трудоёмкость алгоритма O(N*n*log n) N – количество складов, n – максимум из количества вагонов, требущих обслуживания на любом складе.

17 Можно показать, что при таких ограничениях задача остаётся NP- трудной (в обычном смысле). Воспользуемся методом масштабирования и следующим динамическим подходом. Рассмотрим индикаторную функцию Можно заметить, что в силу определения функции d она обладает следующим свойством: d(x)=d(B-x) Пусть Применяя этот подход для отмасштабированной задачи, получаем оценку

18 Несмотря на внешнее сходство, задачи «с тупиком» и «без тупика» имеют принципиально различную природу и, как следствие, различный сложностной статус. Результаты могут найти применение при разработке системы оптимального планирования работ на грузовых фронтах Белорусской Железной Дороги.

19 Спасибо за внимание!