WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 |

На основе Теоремы 1 в разделе 1.4 предлагается схема приближенного решения задачи. Идея схемы состоит в построении по заданному примеру A такого примера C с такими же временами обслуживания требований, который бы, во-первых, принадлежал некоторому известному полиномиально разрешимому классу примеров, и во-вторых, отличался от примера A минимальным образом (в псевдометрике (A, C)). Применив полиномиальный алгоритм для решения примера C, мы найдем оптимальную перестановку его требований и применим ее в качестве приближенного решения примера A. Из теоремы 1 следует, что абсолютная погрешность полученного решения не будет превосходить (A, C).

В подразделе 1.4.1 представлен алгоритм, работающий по схеме приближенного решения задачи. В алгоритме пример C ищется в классе Лазарева. Пример принадлежит данному классу, если существует нумерация требований {1, 2,..., n}, для которой выполняются соотношения dC... dC; C... C, 1 n 1 n C где C = dC - rj - pC обозначает временной запас требования j. Заj j j тем доказывается Теорема 2, которая дает аналитическую формулу для абсолютной погрешности (A, C) для первого варианта схемы.

Теорема 2 Для любого примера A задачи 1 | rj | Lmax, не принадлежащего классу Лазарева, и для любого примера C, наследующего длительности обслуживания примера A и принадлежащего классу Лазарева9, справедлива оценка расстояния между A и C:

(A, C) L(A) = max min{dA - dA, A - A}. (1) j i j i i,jN Оценка (1) достигается на некотором примере C, который может быть найден за время O(n log n).

В подразделе 1.4.2 представлен другой алгоритм, работающий по схеме приближенного решения задачи. В алгоритме пример C ищется в классе Хогевена10. Пример принадлежит данному классу, если выполняется условие rj [dj - pj -, dj - ] j N, - const.

Затем доказывается Теорема 3, которая дает аналитическую формулу для абсолютной погрешности (A, C) для второго варианта схемы.

Лазарев А.А. Эффективные алгоритмы решения некоторых задач теории расписаний для одного прибора с директивными сроками обслуживания требований// Дис. канд. физ.-мат. наук.– Казань: 1989.– 108 с.

Hoogeveen J. A. Minimizing maximum promptness and maximum lateness on a single machine// Math. Oper. Res.– 1996.– V. 21.– P. 100 – 114.

Теорема 3 Для любого примера A задачи 1|rj|Lmax, не принадлежащего классу Хогевена, и для любого примера C, наследующего длительности обслуживания примера A и принадлежащего классу Хогевена, справедлива оценка расстояния между A и C:

A A (A, C) H(A) = max{dA - rj - pA - dA + ri }. (2) j j i i,jN Оценка (2) достигается на некотором примере C, который может быть найден за время O(n).

В разделе 1.5 построена процедура равномерной генерации примеров из ограниченного множества содержащего всевозможные примеры задачи 1 | rj | Lmax. С помощью данной процедуры проведено экспериментальное исследование полиномиальных алгоритмов Лазарева и Хогевена для решения соответствующих специальных случаев задачи. Исследование показало число оптимально решенных данными алгоритмами примеров стремится к 100% при увеличении размерности. Также экспериментально было оценена фактическая погрешность решения, полученного с помощью предложенных вариантов схемы приближенного решения задачи. Показано, что среднее отношение фактической погрешности к гарантированной теоретической погрешности возрастает при увеличении размерности и стремится к некоторому значению, не превышащему 1/2.

Вторая глава диссертации посвящена алгоритмам оптимального решения задачи 1 | rj | Lmax.

В разделе 2.1 рассмотрены существующие подходы к решению задачи, такие как алгоритм Карлье11 и метод программирования в ограничениях12 (ПвО). Данный метод близок к методу ветвей и границ. Отличие заключается в том, что для сокращения перебора в ПвО используется пропагация ограничения, которая удаляет несовместимые значения из множеств допустимых значений переменных. Алгоритм Карлье и программирование в ограничениях служат основой для алгоритмов решения задачи, предложенных далее во второй главе диссертации.

Carlier J. The one-machine sequencing problem// European J. of Oper. Res.– 1982.– V. 11, N 1.– P. 42 – 47.

Baptiste Ph., Le Pape C., Nuijten W. Constraint-based scheduling: applying constraint programming to scheduling problems// Kluwer Academic Publishers, 2001.– 198 p.

В разделе 2.2 предлагаются два алгоритма оптимального решения задачи 1 | rj | Lmax. Первый алгоритм построен по методу программирования в ограничениях. На каждом шаге алгоритма для исходной задачи решается задача распознавания с помощью метода ПвО, в котором используется предложенная нами правило ветвления, основанное на следующей теореме.

Теорема 4 Пусть построено расписание Шража13 (N) для данного примера задачи, и требования пронумерованы в том порядке, в котором они упорядочены в. Пусть также b N наименьший номер, для которого Lb() = Lmax(), и a N наибольший такой номер, что a b и sa() - min rj Lb() - UB, ajb где UB Lmax(), UB верхняя оценка оптимального решения. Примем S = {a,..., b}, тогда:

• если не существует такого требования c S, что dc > db, то для данного примера не существует расписания c максимальным временным смещением, меньшим, чем UB;

• иначе, если c S - последнее требования c директивным сроком dc > db, то в любом таком расписании, что Lmax( ) < UB, требование c выполняется или до, или после всех требований из множества J = {c + 1,..., p}.

Оптимальное решение задачи находится с помощью бинарного поиска (дихотомии). Второй алгоритм построен по методу ветвей и границ. В алгоритме также используется правило ветвления, основанное на теореме 4. Отличительной особенностью алгоритма является использование Schrage, L. Solving Resource-Constrained Network Problems by Implicit Enumeration: NonPreemptive Case// Oper. Res.– 1970.– V. 18.– P. 263 – 278.

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

В разделе 2.3 приводятся результаты экспериментального сравнения точных алгоритмов решения задачи 1 | rj | Lmax, предложенных в работе и подходов, существующих в литературе. Исследование показало, что на множестве тестовых примеров второй предложенный алгоритм показал наилучшие результаты.

В разделе 2.4 рассматривает вариант распознавания задачи 1 | rj | Lmax. Назовем расписание допустимым по отношению к константе L, если Lmax() L. Множество требований S допустимо по отношению к константе L, если существует допустимое расписание (S), и недопустимо, если не существует такого расписания. В рассматриваемом здесь варианте задачи требуется определить допустимо ли заданное множество требований N по отношению к заданной константе L. Если N допустимо, то необходимо найти допустимое расписание. Если же N недопустимо, то требуется найти как можно меньшее недопустимое по отношению к той же константе подмножество требований из множества N.

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

Теорема 5 Пусть дано недопустимое по отношению к константе L расписание Шража (N) и требования пронумерованы в том порядке, в котором они упорядочены в. Пусть также b N наименьший номер, для которого Lb() > L, и a N наибольший такой номер, что a b и sa() - min rj < Lb() - L, jS где S = {a,..., b}. Тогда:

1. если не существует такого требования c S, что dc > db, то множество требований S недопустимо по отношению к L ;

2. иначе, если c S - последнее требования c директивным сроком dc > db, и существует допустимое расписание (N), то в данном расписании требование c выполняется или до, или после всех требований из множества J = {c + 1,..., p}.

Отличительной чертой модифицированного алгоритма Карлиера является способ построения недопустимого подмножества требований в случае, если алгоритм не нашел допустимого расписания. На каждом узле дерева поиска, где не происходит ветвления, согласно Теореме 5, мы располагаем подмножеством S, недопустимым для задачи с текущими параметрами требований. Данное подмножество передается родительскому узлу дерева поиска. Способ построения недопустимого подмножества для узла, имеющего дочерние узлы, обоснован в Теореме 6.

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

Теорема 6 Пусть в текущей задаче в любом допустимом расписании (N) требование c N может быть обслужено только до или после всех требований из множества J N. Пусть также Sa N - недопустимое множество требований для задачи с дополнительным ограничением, согласно которому c обслуживается перед всеми требованиями из множества J, а Sb N - недопустимое подмножество для задачи, где c выполняется после всех требований из J. Тогда:

1. если c Sa, то множество Sa недопустимо для текущей задачи;

2. если c Sb, то множество Sb недопустимо для текущей задачи;

3. если c Sa и c Sb, то множество S = J Sa Sb недопустимо для текущей задачи.

Результаты, полученные в первой и второй главах, частично используются в третьей главе диссертации, в которой предлагается точный алгоритм решения задачи 1 | rj | wjUj. Алгоритм построен по “гибридному” методу14 ветвей и отсечений15, который представлен в разделе 3.1.

В этом же разделе сделан обзор работ, внесших вклад в развитие данного метода. Предложенный алгоритм ветвей и отсечений заключается в следующим. Релаксация задачи формулируется как задача целочисленного линейного программирования (ЦЛП) и решается методом ветвей и отсечений, который является производным от метода ветвей и границ (метода Лэнд и Дойг). Каждое полученное целочисленное решение формулировки проверяется на допустимость с помощью специально разработанных комбинаторных алгоритмов. В случае недопустимости решения генерируются дополнительные ограничения, добавляемые в формулировку задачи отсечения.

В разделе 3.2 приведена постановка задачи, сделан обзор литературы по существующим методам ее решения.

В разделе 3.3 задача 1 | rj | wjUj формулируется как задача ЦЛП. Пусть булева переменная xj принимает значение 1, если требование j N обслуживается вовремя и 0 - если требование j N запаздывает. Тогда в компактном виде формулировка записывается следующим образом.

min wj(1 - xj) (3) jN RD(x) (4) disjunctive(x) (5) x {0, 1}n (6) Здесь ограничениеdisjunctive(x) выполняется тогда и только тогда, когда множество требований J = {j : xj = 1} может быть обслужено на одном приборе без прерываний и с соблюдением времен поступления и директивных сроков, (4) релаксация ограниченияdisjunctive. Ограничение (5) моделируется линейными ограничениями достаточно громоздко и неэффективно, что делает невозможным решение задачи ЦЛП достаточно большой размерности за приемлемое время. Поэтому в предлагаемом алгоритме ветвей и отсечений ограничение (5) исключается из Корбут А.А., Сигал И.Х., Финкельщтейн Ю.Ю. Гибридные методы в дискретном программировании// Изв. АН СССР. Техн. кибернет.– 1988.– N 1.– C. 65 – 77.

Финкельщтейн Ю.Ю. Метод отсечения и ветвления для решения задач целочисленного линейного программирования// Изв. АН СССР. Техн. кибернет.– 1971.– N 4.– C. 34 – 38.

формулировки.

В разделе 3.4 рассматриваются различные варианты релаксации (4).

Существующие в литературе варианты не являются достаточно эффективными, поэтому в качестве ограничений (4) предлагаются следующие неравенства. Обозначим li = (ri - rl)+ и jl = (dl - dj)+.

Утверждение 1 Пусть для двух требований i, j N выполняется ri < dj. Если вектор x удовлетворяет ограничениюdisjunctive, тогда x также удовлетворяет ограничению min[dj - ri, (pl - max{li, jl})+]xl dj - ri. (7) lN Раздел 3.5 посвящен вопросу проверки на допустимость решения x за дачи ЦЛП (3), (7), (6), а также вопросу построения отсечений в случае недопустимости x. Предлагаются два семейства отсечений. Отсечение первого семейства может быть построено при помощи алгоритма, предложенного в разделе 2.4. Алгоритм выполняется для множества требо ваний J = {j : xj = 1}, и в случае его недопустимости находится недо пустимое подмножество S J, для которого строится ограничение xj | S | -1. (8) jS Следующее утверждение представляет отсечения второго вида.

Утверждение 2 Пусть заданы такие множество требований N и требование k N \, что k может быть обслужено только с мо мента времени rk, rk > rk, если все требования из выполняются вовремя. Положим также lk = (rk - rl)+. Тогда вектор x, удовлетворяющий ограничениюdisjunctive, удовлетворяет неравенству min dj - rk, (pl - max{lk, jl})+ xl+ lN\\{k} (9) (pk - jk)+xk dj - rk + (rk - rk)(| | - xo), o для каждого требования j N \, dj > rk.

В работе предлагается алгоритм сложности O(n3), который проверяет существование отсечения вида (9), которое нарушается заданным вектором x.

В разделе 3.6 рассматриваются различные варианты предложенного алгоритма ветвей и отсечений. В заключительном разделе 3.7 представляются результаты экспериментального исследования предложенного алгоритма на множестве общедоступных тестовых примеров. Показанно, что разработанный алгоритм для задачи 1 | rj | wjUj является более эффективным, чем лучший алгоритм для данной задачи, существующий в литературе16.

В заключении перечислены основные результаты диссертации.

Публикации автора по теме диссертации 1. Лазарев А.А., Садыков Р.Р. Эффективность полиномиального алгоритма O(n3 log n) для решения NP-трудной проблемы минимизации максимального временного смещения 1 | rj | Lmax// Материалы VII Международного семинара "Дискретная математика и ее приложения", 29 января – 2 февраля.– М.: Изд-во центра прикладных исследований при мех.-мат. факультете МГУ, 2001.– C. 381 – 383.

2. Лазарев А.А., Садыков Р.Р. К исследованию проблемы теории расписаний 1 | rj | Lmax// Материалы российской конференции "Дискретный анализ и исследование операций", 24 июня – 28 июня.– Новосибирск: Изд-во Ин-та математики, 2002.– C. 219.

3. Лазарев А.А., Садыков Р.Р. Схема приближенного решения проблемы 1 | rj | Lmax// Материалы российской конференции "Дискретный анализ и исследование операций", 28 июня – 2 июля.– Новосибирск: Изд-во Ин-та математики, 2004.– C. 173.

4. Лазарев А.А., Садыков Р.Р., Севастьянов С.В. Схема приближенного решения проблемы 1 | rj | Lmax// Дискретный анализ и исследование операций.– 2006.– Cер. 2.– Т. 13, N 1.– C. 57 – 76.

Peridy, L., Pinson E., Rivreau D. Using short-term memory to minimize the weighted number of late jobs on a single machine// European J. Oper. Res.– 2003.– V. 148. P. 591 – 603.

Pages:     | 1 || 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»