автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Алгоритмы построения расписаний для цеховых задач потокового типа с цифровым буфером

005055025

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

КОНОНОВА Полина Александровна

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

Специальность 05.13.18 — математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

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

Новосибирск - 2012

1 5 И0Я 2012

005055025

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

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

Попков Владимир Константинович

доктор физико-математических наук, профессор, Институт вычислительной математики и математической геофизики СО РАН, главный научный сотрудник Пяткин Артем Валерьевич доктор физико-математических наук, доцент, Институт математики им. С.Л. Соболева СО РАН, ведущий научный сотрудник Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Омский государственный университет им. Ф.М. Достоевского»

Защита состоится 27 ноября 2012 г. в 16 час. 30 мин. на заседании диссертационного совета Д 003.061.02 на базе Федерального государственного бюджетного учреждении науки Института вычислительной математики и математической геофизики Сибирского отделения Российской академии наук (ИВМиМГ СО РАН) по адресу: 630090 г. Новосибирск, пр. Ак. Лаврентьева, 6.

С диссертацией можно ознакомиться в библиотеке ИВМиМГ СО РАН. Автореферат разослан 22 октября 2012 г.

Ученый секретарь диссертационного совета

д.ф.-м.н.

Сергей Борисович Сорокин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

В данной работе рассматривается задача теории расписаний, которая появилась при создании электронно-цифровых библиотек и музеев. Интерес к этой задаче обусловлен выполнением совместного Российско-Тайваньского гранта. Рассматриваемая задача является обобщением классической цеховой задачи потокового типа на двух машинах, т.е. задачи Джонсона [4] и относится к так называемым цеховым задачам. В отличие от цеховых задач с промежуточным буфером рассмотренных в [6], в которых работа находится в буфере только в тех промежутках времени, когда она не обслуживается ни одной машиной, в цифровом буфере работа напротив занимает буфер в течение всего интервала ее обслуживания. Последняя ситуация более характерна для приложений, связанных с обработкой цифровых данных на компьютерах.

Цеховые задачи теории расписаний интенсивно изучаются с середины 50-х годов прошлого столетия. Большинство этих задач трудны как теоретически, то есть являются NP-тpyдными, так и практически, то есть требуют слишком много времени для нахождения точного решения даже на примерах малой размерности, 15-20 работ. Все эти свойства характерны для цеховой задачи с цифровым буфером. Поэтому одним из перспективных подходов является построение нижних оценок и разработка методов локального поиска, учитывающих структуру задачи.

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

Основные результаты.

1. Проведено исследование вычислительной сложности цеховой задачи на двух машинах с цифровым буфером.

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

3. Разработаны и программно реализованы итерационные методы локального поиска для решения задачи с активным и пассивным методами загрузки буфера.

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

1. Впервые выделены полиномиально разрешимые случаи задачи. Установлена КР-трудность в сильном смысле некоторых подклассов.

2. Получены оригинальные модели целочисленного линейного программирования для активной и пассивной загрузки цифрового буфера. Ранее аналогичные модели отсутствовали.

3. Разработаны алгоритмы и программы, которые позволяют решать задачи большой размерности, с числом работ больше 50.

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

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

Практическая и теоретическая ценность. Работа носит теоретический и экспериментальный характер. Установлена вычислительная сложность цеховых задач с цифровым буфером, получены численные методы их решения. Разработанные методы реализованы в виде программ. Программа "Локальный поиск с чередующимися окрестностями для цеховой задачи потокового типа с цифровым буфером" зарегистрирована в Фонде алгоритмов и программ СО РАН, свидетельство №Р11 12009.

Апробация работы. Все разделы диссертации прошли апробацию на следующих конференциях в России и за рубежом:

— Международный симпозиум по математическому программированию (ISMP), Германия, Берлин, 2012;

— Балканская конференция по исследованию операций (BalcOR), Греция, Салоники,2011;

— Международная конференция по управлению планирования и теории расписаний (PMS), Франция, Тур, 2010;

— Международный симпозиум по исследованию операций (OR), Германия, Мюнхен, 2010;

— Российская конференция "Дискретная оптимизация и исследование операций", Новосибирск, Алтай, 2010;

— Всероссийской конференции "Проблемы оптимизации и экономические приложения", Омск, 2009 и 2012;

— Азиатская международная школа-семинар "Проблемы оптимизации сложных систем", Кыргызская Республика, г.Бишкек, 2009;

— Научные семинары Института математики им. C.JT. Соболева СО РАН.

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

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

Публикации. По теме диссертации автором опубликовано 12 работ, в том числе 3 статьи в журналах из списка ВАК, получено свидетельство о регистрации программы в Фонде алгоритмов и программ СО РАН.

Объем и структура диссертации. Диссертация состоит из введения, трех глав и списка литературы (47 наименований). Объем диссертации — 106 страниц.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе формулируется задача потокового типа с цифровым буфером и ее подзадачи. Эти задачи возникают при создании электронно-цифровых библиотек и музеев [5]. Медиа-объекты (файлы) за- _ гружаются из удаленной базы данных и затем воспроизводятся. Для каждого файла заданы время загрузки и воспроизведения. При загрузке файл поступает в буфер транслирующего устройства и покидает его сразу после завершения воспроизведения. Размер буфера ограничен. Размеры файлов известны и пропорциональны времени загрузки. Воспроизведение файла не может начаться раньше окончания его загрузки. Если файл начал загрузку или воспроизведение, то этот процесс не прерывается. Требуется, так задать порядок загрузки и воспроизведения файлов, чтобы минимизировать время окончания воспроизведения последнего файла.

Рассматриваемая задача выбора порядка презентации медиа-объектов тесно связана с цеховой задачей построения расписания в системе потокового типа на двух машинах, которую принято называть задачей Джонсона [4]. В задаче Джонсона множество работ требуется выполнить на двух машинах. Каждая работа выполняется сначала на первой машине, а затем — на второй. Требуется найти такой порядок выполнения работ на обеих машинах, который минимизирует длину расписания, то есть время завершения последней работы. Задачу выбора порядка презентации медиа-объектов можно представлять как задачу Джонсона с дополнительным буферным ограничением, если считать загрузку объекта выполнением работы на первой машине, а воспроизведение — выполнением на второй машине.

Известно несколько способов загрузки. В [2] рассмотрен случай, когда новый объект не загружается, пока свободного пространства в буфере недостаточно для помещения этого объекта. Другими словами, если

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

Активная модель загрузки предполагает более агрессивное использование свободного пространства, а именно, в каждый момент времени общий размер загруженных и частично загруженных объектов не должен превышать размера буфера. Будем ссылаться на такую модель, как на модель с активной загрузкой и обозначать ее как АР-задачу.

Сформулируем обе задачи в терминах теории расписаний. Дано множество из п работ 3 — {1,2,..., п}, две машины АиВи буфер размера П. Каждая работа имеет две операции. Первая операция каждой работы выполняется на машине А. Вторая операция каждой работы выполняется на машине В. Вторая операция каждой работы не может начаться раньше завершения первой операции той же работы. Для каждой операции задано время ее выполнения. Пусть а^ и Ь^ обозначают длительности первой и второй операций работы і соответственно. Предполагая, что в единицу времени загружается одна единица объема файла получим, что объем буфера, занимаемый работой ■} после загрузки равен а^.

Обозначим через в" (сг) и с°(а) момент начала и момент окончания первой операции работы і в расписании а соответственно. Аналогично обозначим через и с'(сг) моменты начала и окончания работы і на машине В в расписании а.

Пусть Зт — подмножество работ, которые находятся в буфере или загружаются в него в момент т. Тогда следующее ограничение должно выполняться в РР-задаче:

^ а, < П, т < Т, ¿є.и

где Т—верхняя оценка на общее время выполнения всех работ.

Для ЛР-задачи ограничение на буфер будет менее жестким. Пусть а_, (т) обозначает часть работы і, уже загруженной в буфер к моменту г, или 0, если т > Ср т < Т. Тогда следующее ограничение должно выполняться в АР-задаче:

£ а.}(т) < П, т < Т.

j€Jт

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

В разд. 1.1 вводится понятие ограниченной задачи. Если для каждой работы выполняется неравенство а^ + ^ < П, 3 6 J, то РР-задача обозначается как КРР-задача, а АР-задача — как ДЛР-задача.

Теорема 1. Задачи РР и ЯРР эквивалентны.

Аналогичное утверждение доказано для АР и КАР задач в теореме 2.

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

В разд. 1.2 для ЛР-задачи доказано важное свойство: оптимальное расписание можно искать среди перестановочных расписаний.

Теорема 3. Среди оптимальных расписаний АР-задачи существует расписание, в кот,ором работы на машинах А и В выполняются в одинаковом порядке.

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

Лемма 1. Пусть в АР-задаче обе машины выполняют, работы в соответствии с перестановкой п = (1,2,..., п), и расписание а задается следующими рекуррентными формулами:

= О, чь _ га

в? =шах{с°_1,4_1 -П + аг_1}, 2 <г<п,

я^тах^!,^}, 2 < г < п.

Пусть а' — некоторое другое расписание, но работы в нем выполняются в том же порядке тг, тогда Стах(сг) < Стах(с')-

В лемме 3 вводятся похожие рекуррентные формулы для РР-задачи.

Эти рекуррентные формулы используются для вычисления длины расписания по заданной перестановке в алгоритмах локального поиска.

В разд. 1.3 проведено исследование сложности подклассов задачи. Доказано, что в общем случае задача является ^-трудной в сильном смысле. Выделены полиномиально разрешимые случаи.

В разд. 1.3.1 доказано, что ЯАР-задача также является ИР-трудной в сильном смысле. К данной задаче полиномиально сводится задача 3-Разбиение.

В разд. 1.3.2. и 1.3.3 рассматриваются частные случаи задач для быстрых и медленных сетей. Назовем ДРР-задачу ДРР>-задачей (РРР<-задачей), если а, > bj < Ь3) для всех работ. Показано, что обе задачи являются ИР-трудными в сильном смысле, что усиливает результат

Теорема 7. Пусть в ЯАР>-задаче обе машины выполняют работы в соответствии с перестановкой тт, в которой работы г)порядочены по невозрастанию величин ЬТогда расписание а, построенное по формулам из леммы 1 для перестановки -к, является оптимальным для ЯАР> -задачи.

Из теоремы 7 следует, что Л Р>-задача также является полиномиально разрешимой.

В теоремах 8 и 9 доказано, что ЯАР<-задача является полиномиально разрешимой, а соответствующая ей ЛР<-задача является ^-трудной в сильном смысле.

Во второй главе подробно рассматривается задача с активным буфером. В разд. 2.1 она представлена в виде задачи целочисленного линейного программирования (ЦЛП).

Введем переменные хц е {0,1}, которые также как и 7г задают порядок выполнения работ: х^ = 1, если работа г выполняется j-oiл по порядку в 7г. Тогда следующие ограничения описывают ЛР-задачу:

из [2].

П

П

4 = о, > З е .1,

>зь1+рь1+р*-п, з^З.

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

Для поиска оптимального решения этой задачи использовались специализированные коммерческие пакеты. Результаты численных экспериментов с пакетом СРЬЕХ показывают, что если существует разрыв цело-численности, то примеры с 20 работами могут потребовать более суток -расчетов на персональном компьютере. Если разрыва целочисленности нет, то примеры решаются за минуту.

Разд. 2.2 посвящен различным нижним оценкам для задачи с активным буфером. В разделе 2.2.1 изучаются две оценки линейного программирования: ЬВ1Р для АР-задачи и Ы3[р для ЯАР-задачи, построенной по данным АР-задачи. Первая оценка получается заменой целочисленных переменных в ЦЛП на непрерывные. Для получения второй оценки исходный пример преобразуется в эквивалентный пример ограниченной задачи. После этого, для полученной ограниченной задачи строится аналогичная оценка линейного программирования.

Доказано, что ЬВ¡р < ЬВ[Р на любом примере. Более того, численные эксперименты показали, что на многих примерах переход к ограниченной задаче увеличивает нижнюю оценку, на некоторых примерах до 10%.

В разд. 2.2.2 описана другая нижняя оценка. Если в рассматриваемой задаче считать, что размер буфера неограничен, то задача совпадет с классической задачей Джонсона на двух машинах, которая является полиномиально разрешимой. Ее оптимальное решение дает другую нижнюю оценку для задачи с буфером. Численные эксперименты показали, что эта оценка на некоторых примерах лучше, чем оценка линейного программирования. Доказано, что существуют примеры, для которых оценка Джонсона для ограниченной задачи в (2 — е) раза точнее оценки Джонсона для исходной задачи, где е сколь угодно малая положительная константа.

Разд. 2.3 посвящен описанию разных вариантов схемы локального поиска с чередующимися окрестностями [1]. В разд. 2.4 представлены

окрестности используемые в алгоритмах локального поиска.

Кроме простых окрестностей, также рассматривается окрестность Кер-нигана-Лина. Эта окрестность позволяет найти некоторую последовательность переходов по простым окрестностям, приводящую к хорошему решению. Окрестность Кернигана-Лина позволяет продолжать поиск даже если текущее решение является локальным минимумом относительно простых окрестностей.

Численные эксперименты подробно описаны в разд. 2.5. Сначала сравним нижние оценки с верхними оценками, получаемыми алгоритмом локального поиска с чередующимися окрестностями на случайно порожденных данных. Численные эксперименты показали, что с ростом размерности число несовпадений нижней и верхней оценок падает, а при п — 50 исчезает вовсе. При п > 100 ситуация сохраняется. Получается удивительный эффект: с ростом размерности задачи она становится проще и при больших п легко решается точно. Алгоритм быстро находит решение, значение которого совпадает с нижней оценкой. Такой эффект связан со способом генерации исходных данных. При большом разнообразии длительностей работ их легко компоновать под размер буфера. Изменив способ генерации исходных данных, можно получить трудные примеры, которые даже при отсутствии разрыва целочисленно-сти будут представлять "головоломку".

Также были построены примеры из трудных примеров для задачи упаковки в контейнеры [3]. В этих примерах оптимальное решение соответствует оптимальному решению задачи упаковки в контейнеры. Нижние оценки совпадают и равны оптимуму. Однако найти оптимум методами локального поиска трудно. На небольшой размерности п = 40 разработанный метод локального поиска в 44 примерах из 50 нашел оптимальное решение, в остальных б примерах найденное решение отличалось от оптимального на единицу. Для п = 80 средняя погрешность составляет около 0,02%.

В третьей главе подробно рассматривается задача с пассивным буфером. В разд. 3.1 предложено 4 формулировки задачи в терминах целочисленного линейного программирования. Три из этих формулировок предполагают, что порядки выполнения работ на машинах А и В могут не совпадать. С помощью этих формулировок имеется возможность

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

В разд. 3.2 и 3.3 описаны три схемы локального поиска для решения задачи с пассивным буфером. Одна из них использует экспоненциальную окрестность, не используемую ранее для задачи с активным буфером. Эта окрестность задается некоторым интервалом в перестановке и соседними решениями являются только те, которые отличаются от исходного в этом интервале. Найти лучшего соседа по такой окрестности можно используя одну из ЦЛП формулировок, зафиксировав порядок для всех работ, непопадающих в этот интервал. Численные эксперименты показали, что поиск оптимального соседнего решения требует неприемлемое время. Поэтому разработана новая процедура, основанная на методе поиска с запретами, просматривающего решения в этой окрестности.

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

Теорема 12.Пусть а — оптимальная перестановка работ для задачи Джонсона. Тогда для задачи с пассивным буфером можно за полиномиальное время найти минимальный размер буфера, при котором а останется оптимальной перестановкой.

Теорема 13. Задача минимизации буфера при заданной длине расписания является ЫР-трудной в сильном смысле.

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

Основные результаты

• Для цеховой задачи потокового типа с цифровым буфером введены понятия активного и пассивного буфера. Для обоих вариантов задачи получены новые математические модели в терминах целочисленного линейного программирования. Доказана КР-трудность рассматриваемых задач и некоторых их частных случаев. Выделены полиномиально разрешимые подклассы. Для обратной задачи минимизации буфера при заданном времени выполнения всех работ установлена ^-трудность задачи, вычисление минимального размера буфера при заданной последовательности выполнения работ является полиномиально разрешимой задачей.

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

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

Список литературы

[1] Кочетов Ю., Младенович Н., Хансен П. Локальный поиск с чередующимися окрестностями // Дискретный анализ и исследование операций. Серия 2. —2003. - Том 10, № 1. -С. 11-43.

[2] Lin F.-C., Hong J.-S., Lin B.M.T. A two-machine flow shop problem with processing time-dependent buffer constraints - An application in multimedia problem // Computers and Operations Research.— 2009 — V. 36, N. 4. - P. 1158-1175.

[3] Falkenauer E. A Hybrid grouping genetic algorithm for bin packing //J. Heuristics.—1996. - V. 2, N. 1,— P. 5 - 30.

[4] Johnson S.M., Optimal two- and three-stage production scheduling with setup time included. Naval Research Logistics Quarterly 1, 61-68, (1954).

[5] Lin F.-C., Lai C.-Y., Hong J.S. Minimize presentation lag by sequencing media objects for auto-assembled presentations from digital libraries // Journal Data & Knowledge Engineering. V. 66,1. 3, 2008, P. 382-401.

[6] Papadimitriou, C. H., Kanellakis, P. C. Flowshop scheduling with limited temporary storage // Journal of the Association for Computing Machinery -1980 - V. 27, N.3. - P. 533-549.

[7] Sevastianov S., Lin B.M.T. Efficient enumeration of optimal and approximate solutions of the two-machine flow-shop problem // Preprint of 10th Workshop on Models and Algorithms for Planning and Scheduling Problems (Nymburk, Czech Republic,2011 July 19-24). — P.177-179.

Публикации автора по теме диссертации

1. Кононова П.А. Нижние и верхние оценки длины оптимального расписания презентаций медиа-объектов // Дискретный анализ и исследование операций. 2012. Т.19, № 1. С. 59-73.

2. Kononov A., Hong J.-S., Kononova P., Lin F.-C. Quantity-based buffer-constrained two machine flowshop problem: active and passive prefetch models for multimedia applications// Journal of Scheduling. 2012. V. 15, N.4, P. 487497.

3. Кононова П.А., Кочетов Ю.А. Локальный поиск с чередующимися окрестностями для задачи Джонсона с пассивным буфером // Дискретный анализ и исследование операций. 2012. Т.19, № 5. С. 63-82.

4. Kononova P. Lower bounds for the two stage multimedia problem with an active prefetch// Proceedings of 1-st International Symposium &: 10-th Balkan Conference on Operations Research, Thessaloniki, Greece, 2224 September, V. 2, P. 289-294.

5. Кононова П.А., Кочетов Ю.А. Нижние оценки для задачи выбора порядка презентаций медиа-объектов// Труды XV Байкальской международной школы-семинара "Методы оптимизации и их приложения". Т. 5, Иркутск, 23-29 июня, РИО ИДСТУ СО РАН, 2011, С. 73-78.

6. Kononov А. V., Kononova P. A., Hong J.-S. New lower bounds for two-stage multimedia scheduling problems// Abstracts of the 12th International Conference devoted to Project Management and Scheduling, Tours, France, April 26-28, 2010, P. 231-234.

7. Кононова П.А. Алгоритм ветвей и границ для решения задачи Джонсона с буфером на второй машине. Российская конференция "Дискретная оптимизация и исследование операций": Материалы конференции (Алтай, 27 июня - 3 июля 2010). - Новосибирск: Изд-во Ин-та математики, 2010. С. 143.

8. Kononova Р.А. Heuristic and exact methods for a two stage multimedia problem with passive prefetch. International conference on Operations Research, Munich, September 1-3, 2010, P. 165.

9. Кононова П. А. Алгоритм локального поиска для задачи выбора порядка презентаций медиа объектов // Труды ИВМ и МГ, Информатика, 9, Новосибирск 2009, С. 177-182.

10. Kononov А. V., Kononova P. A., Hong J.-S. Two-stage multimedia scheduling problem with an active prefetch model // Preprints of the 13th IFAC Symposium on Information Control Problems in Manufacturing, Moscow, Russia, June 3 - 5, 2009, P. 1997-2002.

11. Кононова П.А. Алгоритм решения задачи Джонсона с буфером. Тезисы IV Всероссийской конференции "Проблемы оптимизации и экономические приложения", Омск, 2009, С. 139.

12. Кононова П.А. Алгоритм решения задачи Джонсона с буфером. Тезисы V Всероссийской конференции "Проблемы оптимизации и экономические приложения", Омск, 2012, С. 155.

Подписано в печать 22.10.12. Формат 60x84 1/16. Усл. печ. л. 1,0. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ № 167.

Отпечатано в ООО "Омега Принт" пр. Ак. Лаврентьева, 6, 630090 Новосибирск

Введение

1 Вычислительная сложность потоковых задач с буфером

1.1 Сведение к ограниченной задаче.

1.2 Перестановочные расписания.

1.3 Сложность задачи.

1.3.1 Сложность КАР-задачи.

1.3.2 ЙРР-задача с быстрой/медленной скоростью передачи

1.3.3 Я АР- задача с быстрой / медленной скоростью передачи

2 Нижние и верхние оценки оптимума для цеховых задач потокового типа с активным буфером

2.1 Математическая модель.

2.2 Нижние оценки.

2.2.1 Оценка линейного программирования.

2.2.2 Оценка Джонсона

2.3 Поиск с чередующимися окрестностями.

2.4 Окрестности.

2.5 Численные эксперименты.

3 Нижние и верхние оценки оптимума для цеховых задач потокового типа с пассивным буфером

3.1 Постановка задачи и ее ЦЛП формулировки.

3.2 Окрестности.

3.3 Общая схема метода и ее варианты

3.4 Построение примеров с известным оптимумом.

3.5 Численные эксперименты.

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

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

В данной работе рассматривается задача теории расписаний, которая появилась при создании электронно-цифровых библиотек и музеев. Интерес к этой задаче был обусловлен выполнением совместного Российско-Тайваньского гранта. Рассматриваемая задача является обобщением классической цеховой задачи потокового типа на двух машинах, т.е. задачи Джонсона [30] и относится к так называемым цеховым задачам. В отличие от цеховых задач с промежуточным буфером рассмотренных в [42], в которых работа находится в буфере только в тех промежутках времени, когда она не обслуживается ни одной машиной, в цифровом буфере работа напротив занимает буфер в течение всего интервала ее обслуживания. Последняя ситуация более характерна для приложений связанных с обработкой цифровых данных на компьютерах.

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

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

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

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

1. Проведено исследование сложности цеховой задачи на двух машинах с цифровым буфером. Доказано, что в общем случае задача является ОТ-трудной в сильном смысле. Выделены полиномиально разрешимые случаи.

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

3. Найден способ корректировки исходных данных существенно улучшающий нижние оценки глобального оптимума.

4. Разработаны итерационные методы локального поиска для решения задачи с активным и пассивным методами загрузки буфера.

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

Апробация работы. Все разделы диссертации прошли апробацию на следующих конференциях в России и за рубежом:

Международный симпозиум по математическому программированию (¡БМР), Германия, Берлин, 2012;

Конференция европейского общества комбинаторной оптимизации (ЕССО), Турция, Анталия, 2012;

Балканская конференция по исследованию операций (Ва1с(Ж), Греция, Салоники, 2011;

Международная конференция по управлению планирования и теории расписаний (PMS), Франция, Тур, 2010;

Международный симпозиум по исследованию операций (OR), Германия, Мюнхен, 2010;

Российская конференция "Дискретная оптимизация и исследование операций", Новосибирск, Алтай, 2010;

Всероссийской конференции "Проблемы оптимизации и экономические приложения", Омск, 2009 и 2012;

Азиатская международная школа-семинар "Проблемы оптимизации сложных систем", Кыргызская Республика, г.Бишкек, 2009;

Научные семинары Института математики им. С,Л. Соболева СО РАН.

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

Публикации. По теме диссертации автором опубликовано 12 работ, в том числе 3 статьи в журналах из списка ВАК.

Объем и структура диссертации. Диссертация состоит из введения, трех глав и списка литературы (46 наименований). Объем диссертации — 106 страниц.

Заключение

• Для цеховой задачи потокового типа с цифровым буфером введены понятия активного и пассивного буфера. Для обоих вариантов задачи получены новые математические модели в терминах целочисленного линейного программирования. Доказана КР-трудность рассматриваемых задач и некоторых их частных случаев. Выделены полиномиально разрешимые подклассы. Для обратной задачи минимизации буфера при заданном времени выполнения всех работ установлена ЫР-трудность задачи, вычисление минимального размера буфера при заданной последовательности выполнения работ является полиномиально разрешимой задачей.

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

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

1. Гончаров Е. Н., Кочетов Ю. А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения // Дискретный анализ и исследование операций. Сер. 2. — 1999. — Т. 6, № 1.- С. 12-32.

2. Кононова П.А. Алгоритм локального поиска для задачи выбора порядка презентаций медиа объектов // Труды ИВМиМГ, Информатика, 9. Новосибирск: Изд. ИВМиМГ СО РАН. — 2009.-С. 177-182.

3. Кононова П.А. Нижние и верхние оценки длины оптимального расписания презентаций медиа-объектов // Дискретный анализ и исследование операций. — 2012. — Том 19, №1. — С. 59-73.

4. Кононова П.А., Кочетов Ю.А. Локальный поиск с чередующимися окрестностями для задачи Джонсона с пассивным буфером // Дискретный анализ и исследование операций. — 2012. — Т. 19, № 5.- С.63-82.

5. Кочетов Ю., Младенович Н., Хансен П. Локальный поиск с чередующимися окрестностями // Дискретный анализ и исследование операций. Серия 2. 2003. - Том 10, № 1. - С. 11-43.

6. Aarts E. H. L., Korst J. H. M., Laarhoven van F. J. M. Simulated annealing // Local search in combinatorial optimization. Chichester: Wiley. 1997. - P. 91-120.

7. Aarts E. H. L., Lenstra J. K. (Eds.) Local Search in Combinatorial Optimization. — Chichester: John Wiley & Sons. 1997.

8. Ahuja R.K., Ergun O., Orlin J.B., Punnen A.P. A survey of very large-scale neighborhood search techniques // Discrete Appl. Math. — 2002.- V. 123, Issue 1-3. P. 75-102.

9. Bent R., Van Hentenryck P. A two stage hybrid local search for the vehicle routing problem with time windows // Transportation science.- 2004. Vol. 38, No. 4. - P. 515-530.

10. Blum C. Roli A. Metaheuristics in combinatorial optimization: Overview and conceptual comparison // ACM Computing Surveys (CSUR). 2003. - V.35, Issue 3. - P. 268-308.

11. Brimberg J., Hansen P., Mladenovic N. Convergence of variable neighborhood search // Les Cahiers du GERAD G-2000-73. Monreal, Canada, 2000.

12. Brimberg J., Mladenovic N. A variable neighborhood algorithm for solving the continuous location-allocation problem // Stud. Locat. Anal. 1996. - V. 10. - P. 1-12.

13. Brucker P., Knust S., Complex Scheduling. Berlin: Springer, 2006.

14. Burke E. K., Causmaecker de P., Petrovic S., Berghe G. V. Variable neighbourhood search for nurse rostering problems // MIC'2001 4th Metaheuristics Intern, conf. Porto, July 16-21. - 2001. - P. 755-760.

15. Burke E.K., Kendall G. (Eds.) Search Methodologies. Introductory Tutorials // Optimization and Decision Support Techniques. — Berlin: Springer, 2005.

16. Davidovic T., Hansen P., Mladenovic N. Variable neighborhood search for multiprocessor scheduling with communication delays // MIC'2001- 4th Metaheuristics Intern, conf. Porto, July 16-21 2001. - P. 737741.

17. Dreo J., Petrowski A., Siarry P., Taillard E., Metaheuristics for Hard Optimization, — Springer, 2006.

18. Falkenauer E. A Hybrid grouping genetic algorithm for bin packing // J. Heuristics-1996. V. 2, N. 1- P. 5 - 30.

19. Festa P., Resende M. G. C., GRASP: An annotated bibliography. In: C. C. Ribeiro, P. Hansen (Eds.) Essays and surveys in metaheuristics.- Kluwer Academic Publishers. 2002. — P. 325-368.

20. Fischetti M., Lodi A. Local branching. // Math. Programming. — 2003.- V. 98, N. 2. P. 23-47.

21. Garey M. R., Johnson D. S., Computer and intractability: a guide to the theory of NP-completness. San Francisco, CA: Freeman, 1979.

22. Glover F. Future paths for integer programming and links to artificial intelligence. // Comp. Oper. Res. 1986. - V. 13. - P. 533-549.

23. Glover F., Laguna M. Tabu Search. — Dordrecht: Kluwer Acad. Publ., 1997.

24. Goldberg D. E. Genetic algorithms in search, optimization, and machine learning. Reading, MA: Addison-Wesley, 1989.

25. Gutin G. Exponential neighborhood local search for the traveling salesman problem // Comput. Oper. Res. — 1999. — V. 26. — P. 313320.

26. Gutin G., Yeo A. Small diameter neighborhood graphs for the traveling salesman problem: four moves from tour to tour // Comput. Oper. Res. 1999. - V. 26. - P. 321-327.

27. Hansen P, Mladenovic N. Variable neighborhood search for the p-median problem //Location Science — 1997. — V. 5. — P. 207-226.

28. Hansen P., Mladenovic N., Perez-Brito D. Variable neighborhood decomposition search //J. Heuristics. — 2001. — V. 7, N. 4. — P. 335-350.

29. Ierapetritou M.G., Floudas C.A. Effective continuous-time formulation for shortterm scheduling: I. multipurpose batch process // Ind. Eng. Chem. Res. 1998. - Vol. 37. - P. 4341 - 4359.

30. Johnson S.M., Optimal two- and three-stage production scheduling with setup time included. Naval Research Logistics Quarterly. — 1954.— V. 1, Issue 1- P. 61-68.

31. Kernighan, B.W., Lin, S.: An efficient heuristic procedure for partitioning graphs. Bell System technical Journal. — 1970. — V. 49.- P. 291-307.

32. Kochetov, Yu., Alekseeva, E., Levanova, T., Loresh, M.: Large neighborhood local search for the p-median problem. Yugoslav Journal of Operations Research. 2005. - V. 15, N 1. - P. 53-63.

33. Kochetov Yu., Kononova P., Paschenko M. Formulation Space Search Approach for the Teacher/Class Timetabling Problem // Yugoslav Journal of Operations Research. 2008, - V. 18, N 1. — P. 1-11.

34. Kononov A., Hong J.-S., Kononova P., Lin F.-C. Quantity-based buffer-constrained two machine flowshop problem: active and passive prefetch models for multimedia applications// Journal of Scheduling. — 2012.- V. 15, N.4. P. 487-497.

35. Kononov A., Kononova P., Hong J.-S. Two-stage multimedia scheduling problem with an active prefetch model // Preprints of the 13th IFAC Symposium on Information Control Problems in Manufacturing (Moscow, Russia, June 3 5, 2009).- P. 1997-2002.

36. Korte B., Vygen J., Combinatorial Optimization: Theory and Algorithms. Algorithms and Combinatorics 21 Springer, Berlin. 2000.

37. Lin F.-C., Hong J.-S., Lin B.M.T. A two-machine flow shop problem with processing time-dependent buffer constraints An application in multimedia problem // Computers and Operations Research.— 2009.— V. 36, N. 4. - P. 1158-1175.

38. Lin F.-C., Lai C.-Y., Hong J.S. Minimize presentation lag by sequencing media objects for auto-assembled presentations from digital libraries // Journal Data & Knowledge Engineering. V. 66, I. 3, 2008, P. 382-401.

39. Mladenovic, N., Plastria, F., Urosevic, D. Reformulation descent applied to circle packing problems. // Computers and Operations Research. 2005. - V. 32, N. 9. - P. 2419-2434.

40. Osman I. H., Laporte G. Metaheuristics: a bibliography // Ann. Oper. Res. 1996. - V. 63. - P. 513-628.

41. Papadimitriou, C. H., Kanellakis, P. C. Flowshop scheduling with limited temporary storage // Journal of the Association for Computing Machinery -1980.- V. 27, N.3. P. 533-549.

42. Salassa F. G. M. Matheuristics for Combinatorial Optimization Problems // Ph.D. Thesis.

43. Verhoeven M. G. A., Severens M. E. M., Aarts E. H. L. Local search for Steiner trees in graphs // Modem search, methods. N. Y.: John Wiley and Sons, Inc. 1996. - P. 117-129.

44. Wilbaut C., Hanafi S., Freville A., Balev S. Tabu search: global intensification using dynamic programming. // Control and Cybernetics. 2006. - V. 35, N. 3. - P. 579-588.

45. CPLEX http://www-142.ibm.com/software/products/ru/ru/ilogcple/.