WWW.DISSERS.RU

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

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

Pages:     || 2 | 3 |

На правах рукописи

Садыков Руслан Равильевич АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ ТЕОРИИ РАСПИСАНИЙ ДЛЯ ОДНОГО ПРИБОРА C КРИТЕРИЯМИ Lmax И wjUj 01.01.09 дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва 2006

Работа выполнена на кафедре экономической кибернетики Казанского государственного университета имени В. И. Ульянова – Ленина.

Научный консультант: кандидат физико-математических наук, доцент А. А. Лазарев

Официальные оппоненты: доктор технических наук, профессор И. Х. Сигал, кандидат физико-математических наук, в.н.с. Я. М. Шафранский

Ведущая организация: Институт проблем управления РАН

Защита диссертации состоится " " 2006 г. в часов на заседании диссертационного совета Д.002.017.02 при Вычислительном Центре имени А.А. Дородницина Российской академии наук (119991, г.

Москва, ул. Вавилова, 40, конф.зал).

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

Автореферат разослан " " 2006 г.

Ученый секретарь диссертационного совета, д.ф.-м.н. В. В. Рязанов

Общая характеристика работы

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

Теория расписаний берет свое начало в 50-е годы 20-го века с работ Джексона1 и Джонсона2. В связи с бурным развитием автоматизации производства данное направление прикладной математики приобрело большое значение. В наше время задачи теории расписаний возникают во многих сферах человеческой деятельности: образовании, транспорте, управлении, информатике, производстве, сельском хозяйстве и т.д.

Классические приборные задачи теории расписаний являются схематичными теоретическими моделями многих задач, встречающихся на практике. Исследование приборных задач помогает изучить фундаментальные свойства и структуру практических задач, что способствует построению эффективных алгоритмов их решения.

Рассмотрим постановку одноприборной задачи теории расписаний.

Множество требований N = {1, 2,..., n} должно быть обслужено без прерываний на одном приборе, который может обслуживать не более одного требования в каждый момент времени. Время обслуживания требования j N обозначается как pj. Момент, когда требование j становится доступным для обслуживания, задается временем поступления rj. Требование j также может иметь директивный срок dj (время, до которого желательно завершить обслуживание требования), вес wj (значимость требования).

В любой приборной задаче теории расписаний целью является построение оптимального расписания по определенному критерию. Для представления различных критериев нам необходимы следующие определения. Времена начала и окончания обслуживания требования j в расписании обозначаются как, соответственно, sj() и cj(). Определим Lj() = cj() - dj как временное смещение требования j в расписании, а Tj() как его запаздывание. Uj() обозначает запаздывает Jackson J.R. Scheduling a production line to minimize maximum tardiness// Los Angeles, CA:

University of California, 1955.– Manag. Sci. Res. Project. Research Report N 43.

Johnson S.M. Optimal two- and three-stage production schedules with setup times included// Naval Res. Logistics Quat.– 1954.– V. 1. P. 61 – 68.

ли требование j в расписании или нет. Uj() = 1 если j запаздывает (cj() > dj), иначе Uj() = 0 (требование j обслуживается вовремя).

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

Заметим, что классические критерии являются регулярными, то есть данные функции являются неубывающими по отношений к временам обслуживания требований. При наличии регулярного критерия мы можем ограничиться рассмотрением только ранних расписаний. Каждое раннее расписание однозначно определяется перестановкой требований множества N. Eсли = (j1, j2,..., jn), тогда = (sj, sj,..., sj ), где 1 2 n sj = rj, sj = max{sj + pj, rj }, k = 2,..., n.

1 1 k k-1 k-1 k Множество всевозможных расписаний обслуживания требований множества N обозначается как (N).

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

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

Graham R.L., Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G. Optimization and approximation in deterministic sequencing and scheduling: a survey// Ann. Discrete Math.– 1979.– V. 5.– P. 287 – 326.

Многие задачи теории расписаний являются NP -трудными4. Для решения таких задач существуют три основных класса алгоритмов: эвристические, приближенные и алгоритмы сокращения перебора. Эвристические алгоритмы позволяют получить "хорошее"решение за небольшое время, однако они не могут дать оценок качества полученного решения.

Приближенные алгоритмы5 гарантируют оценку качества полученного решения (погрешность), которое будет ими найдено за полиномиальное время. Приближенные алгоритмы для задач теории расписаний разработаны, например, в работах Ковалева6, Севастьянова7. Однако, во многих случаях гарантируемая погрешность не является достаточной. Более того, для некоторых NP -трудных задач вообще нельзя постоить приближенные алгоритмы. Алгоритмы сокращения перебора используются для оптимального решения NP -трудной задачи. Однако, получение оптимального решения может занять длительное время. Поэтому, если за некоторое приемлемое время оптимальное решение не было найдено, исполнение алгоритма прекращается. В этом случае пользователю доступно некоторое приближенное решение задачи и оценка его качества. Подчеркнем, что оценка полученного решения здесь известна после решения, тогда как при использовании приближенного алгоритма оценка качества известна до начала решения. Обычно, алгоритм сокращения перебора дает лучшее решение поставленной задачи, чем приближенный алгоритм, но за более длительное время. Наиболее распространенным подклассом алгоритмов сокращения перебора являются алгоритмы, построенные по методу ветвей и границ8.

В зависимости от требований пользователя, предпочтительным может оказаться использование алгоритмов как первого, так и второго или Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи// Пер. с англ.– М.:

Мир, 1982.– 416 с.

Танаев В.С., Гордон В.С., Шафранский Я.М. Теория расписаний. Одностадийные системы// М.:

Наука. Гл. ред. физ.-мат. лит., 1989.– 384 с.

Корбут А.А., Финкельщтейн Ю.Ю. Приближенные методы дискретного программирования// Изв. АН СССР. Техн. кибернет.– 1983.– N 1.– C. 165 – 176.

Ковалев М. Я. Интервальные -приближенные алгоритмы решения дискретных экстремальных задач// Дис. канд. физ.-мат. наук.– Минск: 1986, 110 с.

Севастьянов С.В. Геометрические методы и эффективные алгоритмы в теории расписаний// Дис. док. физ.-мат. наук.– Новосибирск: 2000.– 280 с.

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование// М.: Физматлит, 2002.– 240 с.

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

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

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

Научная новизна Результаты работы являются новыми. Основными являются следующие.

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

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

3. Экспериментально показано, что процент оптимально решенных примеров задачи 1 | rj | Lmax полиномиальными алгоритмами стремится к 100% при увеличении размерности. Также экспериментально установлено, что фактическое значение абсолютной погрешности решения, полученного при помощи обоих вариантов предложенной схемы нахождения приближенного решения, в среднем не превосходит половины теоретического значения абсолютной погрешности.

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

5. Для модифицированного варианта разрешимости проблемы 1 | rj | Lmax разработан алгоритм, который определяет допустимо ли заданное множество требований и в случае недопустимости находит некоторое недопустимое подмножество. Разработанный алгоритм используется для решения задачи с критерием минимизации взвешенного числа запаздывающих требований.

6. Для задачи 1 | rj | wjUj предложен точный алгоритм ветвей и отсечений. Преимущество предложенного алгоритма над наилучшим алгоритмом для данной задачи, представленном в литературе, на множестве общедоступных тестовых примеров подтверждено численными экспериментами.

Теоретическая и практическая значимость Исследуемые в диссертации задачи являются схематичными теоретическими моделями практических задач. Однако алгоритмы для решения этих задач используются как вспомогательные для решения более сложных задач теории расписаний, более приближенных к практике.

Предложенные методы также могут быть использованы для разработки алгоритмов решения других похожих теоретических задач теории расписаний. Результаты работы могут быть полезны специалистам Вычислительного центра им. А.А. Дородницина РАН, Казанского Государственного Университета, Новосибирского Государственного Университета, Омского Государственного Университета, Минского Государственного Университета.

Апробация результатов Результаты диссертации докладывались и обсуждались на VII Международном семинаре “Дискретная математика и ее приложения” (Москва, 2001 г.), XL Международной научной студенческой конференции “Студент и научно-технический прогресс” (Москва, 2002 г.), Российской конференции “Дискретный анализ и исследование операций” (Новосибирск, 2002, 2004 гг.), X Международной конференции по оптимизации FGI2000 (Монтпелье, Франция, 2000 г.), I Международной конференции по интеграции методов исследования операций и искусственного интеллекта в программировании в ограничениях для решения комбинаторных задач CP-AI-OR’04 (Ницца, Франция, 2004 г.), VII Международном семинаре по методам и алгоритмам для задач календарного планирования и теории расписаний MAPSP’05 (Сиена, Италия, 2005 г.).

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

Структура и объем работы Диссертация состоит из введения, трех глав, заключения и списка литературы (81 наименование). Общий объем 131 страница.

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

В первой главе предлагаются полиномиальные алгоритмы приближенного решения задачи 1 | rj | Lmax. Данные алгоритмы основаны на доказанной нами теореме об абсолютной погрешности.

В разделе 1.1 рассматривается постановка задачи, а также дан краткий исторический обзор задачи, приведены основные результаты, существующие в литературе. В разделе 1.2 вводятся обозначения и определения, используемые далее в работе.

В разделе 1.3 доказывается теорема об абсолютной погрешности (Теорема 1). Для формулировки теоремы требуется следующие определение и обозначение. Пусть задан пример A на множестве требований N. Будем говорить, что пример B на том же множестве требований наследует у примера A параметр x, если xB = xA, j N. Будем обозначать через j j LI() максимальное временное смещение расписания для примера I с I параметрами требований {rj, pI, dI}.

j j Теорема 1 Пусть пример C наследует у примера A длительности обслуживания требований (pA = pC, j N) и пусть A и C оптиj j мальные расписания для этих примеров. Тогда 0 LA(C) - LA(A) (A, C), A C где (A, C) = maxjN{dA - dC} + maxjN{dC - dA} + maxjN{rj - rj } + j j j j C A maxjN{rj - rj }.

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

Pages:     || 2 | 3 |






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