Свойства оптимальных решений и эффективные алгоритмы построения расписаний в системах открытого типа тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение

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

Главные результаты диссертации

Публикации и апробация результатов исследований

Структура работы.

1 Анализ сложности задачи open shop

1.1 Предварительные сведения

1.2 Задача open shop в обобщенной постановке и 4-параметрический анализ ее сложности.

§ 1.2.1 Постановка задачи.

§1.2.2 Анализ сложности.

§ 1.2.3 Таблица результатов анализа

1.3 "Установление сложности базисных классов.

§ 1.3.1 Полиномиально разрешимые базисные классы

§ 1.3.2 NP-трудность классов l(xj) (j € {10,., 14})

§ 1.3.3 NP-трудность классов X(xg) и X(xq).

1.4 Заключительные замечания к главе 1.

2 Эффективное построение нормальных расписаний

2.1 Предварительные сведения

2.2 Базовые нормальные классы

Оглавление

§ 2.2.1 Минимальные нормализующие векторы в К2 и R

§ 2.2.2 Величина доминирования.

2.3 Эффективно нормализующие векторы в Rm

§ 2.3.1 Метод последовательной достройки нормального расписания

§ 2.3.2 ^-нормализующие и fc-доетраивающие векторы в Ет

§ 2.3.3 Построение эффективно нормализующих векторов в Шт.

2.4 Заключительные замечания к главе 2.

3 Интервал локализации оптимумов задачи open shop

3.1 Предварительные сведения

3.2 Точный интервал локализации оптимумов задачи open shop с тремя машинами.

§3.2.1 Основные формулировки

§ 3.2.2 Процедура "склеивания" работ.

§ 3.2.3 Описание доказательства леммы 3.4.

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

3.4 Заключительные замечания к главе 3.

Общая характеристика работы и обзор результатов диссертации

Рассматриваемая в диссертации с разных сторон задача относится к одной из классических многостадийных моделей теории расписаний. Задачи теории расписаний появляются там, где необходимо упорядочить некоторый процесс в рамках заданных ограничений (т.е. составить допу~ стимое расписание для выполнения этого процесса), с тем чтобы полученное расписание было оптимальным по тем или иным критериям. В настоящее время исследуется множество разнообразных моделей теории расписаний (см., например, обзор [18]), хотя подавляющее большинство этих моделей описывают весьма далекие от реальных условий "идеальные" ситуации. Тем не менее, в течение последних 20 и более лет теория расписаний бурно развивается и в ее рамках создается множество практический приложений для оптимизации реальных процессов.

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

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

Различные многостадийные модели в частности различаются ограничениями на выбор порядка выполнения операций, что, в свою очередь, ограничивает множество допустимых расписаний для данной модели. Так например, в моделях типа "рабочий цех" (job shop) на множестве операций каждой работы априорно задан полный порядок. Рассматриваемая нами модель открытого типа, или open shop, отличается отсутствием априорно заданного порядка выполнения операций. Единственное ограничение, накладываемое на допустимое расписание, состоит в том, что интервалы выполнения операций, принадлежащих одной и той же работе или выполняемых на одной и той же машине, не могут пересекаться.

Здесь требуется сделать небольшое пояснение. Дело в том, что обычно, говоря о "задаче open shop", понимают ее классическую постановку, сформулированную Гонзалезом и Сйни в [3]. Она характеризуется тем, что каждая работа на каждой машине имеет не более одной операции. В данной же диссертации под словами "задача open shop" понимается некоторая более общая модель, а говоря про классическую модель мы будем использовать слова "задача open shop в классической постановке". Более широкая постановка, допускающая наличие более чем одной операции каждой работы на каждой машине, будет у нас именоваться "задача open shop в обобщенной постановке". Еще одно пояснение касается критерия оптимальности расписания. В данной диссертации мы рассматриваем только один из множества критериев, хотя и наиболее распространенный, а именно длина расписания Стах. (В англоязычной литерауре эта величина называется трудно переводимым словом makespan). 1ри использовании этого критерия мы считаем оптимальным наиболее сороткое расписание, т.е. расписание, выполняющее все операции в те-юнии наименьшего промежутка времени. (По умолчанию полагая, что !ыполнение расписания всегда начинается в момент времени 0, часто щину расписания называют поздним временем завершения выполнения итераций.)

Итак, в данной диссертации под словами open shop понимается задача )реп shop (в классической либо обобщенной постановке) с критерием :минимум длины расписания".

Исследование задачи open shop, проделанное в данной диссертации, [ачинается с анализа сложности решения этой задачи, проведенного в лаве 1. Как известно, анализ сложности является одной из основных [роблем, волнующих исследователя той или иной задачи дискретной оптимизации. Исходно под анализом сложности какой-либо оптимиза-;ионной задачи понималось такое ее исследование, которое позволяло пределить одну из двух альтернатив: существует ли полиномиальный лгоритм точного решения задачи (такие алгоритмы мы и будем назы-ать эффективными) или же задача относится к классу NP-трудных. Еозднее, когда для подавляющего большинства известных задач такой ервоначальный анализ был проделан и когда выяснилось, что боль-шнство задач являются NP-трудными, стали исследовать сложность х приближенного решения. Возможные результаты в этом направлении то: построение эффективных р-приближающих алгоритмов (либо дока-ательство невозможности их построения — в предположении P^NP) гуш какой-либо константы р, а также построение полиномиальных ап-проксимационных схем, т. е. семейств полиномиальных по сложности (1+^-приближающих алгоритмов для всевозможных е > 0.' К этому же направлению относятся результаты по построению аппроксимационных схем, состоящих из (р + е)-приближающих алгоритмов для р ф 1, и результаты по построению /-приближающих алгоритмов, где / — уже не константа, а некоторая функция от каких-то входных параметров задачи. Точное определение классов Р и NP можно найти в [4].

В главе 1 мы ограничимся анализом сложности точного решения задачи open shop в обобщенной постановке. Будет исследоваться зависимость сложности задачи от значений нескольких ключевых параметров, а именно: от числа работ (п), максимального числа операций одной par боты (V), числа машин (т) и максимального числа операций машины (/i). Для этого в главе 1 вводится понятие многопараметрического анализа сложности задач дискретной оптимизации. (Напомним, что одно-параметрический анализ сложности классической задачи open shop был проделан Гонзалезом и Сани в [3].)

Каждый вход I задачи open shop определяет значение вектора параметров xi = (п, г/,га, д). Для всевозможных векторов х € Кт мы определяем классы входов Х(х) = {I\xj < ж}. Задача многопараметрического анализа состоит в нахождении базисного набора векторов, обладающего свойствами полноты, непротиворечивости и независимости. Кроме того, для каждого базисного вектора х должна быть определена сложность соответствующего класса Х{х). Имея такой набор базисных векторов, мы можем для любого вектора х определить сложность соответствующего лассаХ(ж).

В главе 1 проведен "почти полный" 4-параметрический анализ слож-:ости задачи open shop. Сложность класса входов с тремя машинами и е более чем двумя операциями каждой работы определить не удалось, •аметим, что вопрос о сложности этого класса был поставлен еще в [3] является открытой проблемой с 1976 года. В теореме 1,4 доказано, что зависимости от сложности такого класса базисный набор состоит либо з 10, любо из 14 векторов, описанных в таблице 1 (§ 1.2.3).

В главе 2 описываются широкие полиномиально разрешимые подклас-ы задачи open shop в классической постановке, описанные в терминах еравномерности нагрузки машин. Неравномерность нагрузки описыва-гся так называемым вектором разностей (VOD), компоненты которого ц равны разности между максимальной нагрузкой машин для данного хода и нагрузкой г-й машины М%. Для универсальности определения ектора разностей величйны Д; измеряются в единицах ртах, где ртах - максимальная длительность операции. По умолчанию считается, что ашины занумерованы в естественной нумерации, т.е. упорядочены по евозрастанию нагрузки. В терминах вектора разностей каждый вектор к = (0,д2,.,дт) € Шт, такой что д2 < д3 < ••• < дт? опреде-яет класс входов задачи с т машинами с VOD — Д. Полиномиально азрещимые подклассы именно такого вида описываются в главе 2.

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

В разделе 2.2 описаны минимальные нормализующие и эффективно нормализующие векторы в I2 и I3. Показано, что единственным таким (как нормализующим, так и эффективно нормализующим) вектором в К2 является вектор (0,1), а в R3 — вектор (0,0,2) (результат из совместной статьи с Кононовым и Севастьяновым [27]).

В разделе 2.3 описан алгоритм последовательной достройки расписания, основанный на жадных принципах. При выполнении определенных условий на вектор разностей этот алгоритм дополняет нормальное расписание на первых к машинах до нормального расписания на первых I машинах (к < I < т). С помощью этого алгоритма можно получить широкий класс эффективно нормализующих векторов в пространствах высшей размерности (см. утверждение 2.29, теорему 2.30, следствие 2.31). И хотя в пространстве R4 нам пока не известно ни одного минимального нормализующего (минимального эффективно нормализующего) вектора, мы можем утверждать, что в R4 имеется по меньшей мере два различных минимальных нормализующих вектора и два различных минимальный эффективно нормализующих вектора (теорема 2.32).

В главе 3 исследуется минимальный интервал локализации оптимумов задачи open shop в обобщенной постановке в терминах тривиальной нижней оценки оптимума С = max{Lmax, c?max}, где Lmax — максимальная нагрузка машины, a dmax — максимальная длина работы. Этот интервал содержит длины оптимальных расписаний для всех входов задачи open shop с т машинами и имеет вид [С, р(т)С\. В теореме 3.1 найдено точное значение функции р(т) при т = 3. Оказывается, что оптимум любого входа задачи open shop с тремя машинами принадлежит интервалу [С, |С], и границы этого интервала точны. Доказательство теоремы является "человеко-машинным" (computer-aided), т.е. при доказательстве используется компьютерная программа. Оно опирается на две леммы. Лемма 3.3 представляет собой "человечную" часть доказательства. В ней показывается, что доказательство теоремы 3.1 для произвольного числа работ может быть сведено к проверке утверждения теоремы для случая не более чем пяти работ. В лемме 3.4 — "машинной" части доказательства — утверждение теоремы 3.1 проверяется (с помощью компьютера) для ограниченного случая с тремя машинами и не более чем пятью работами.

Практическим приложением данного результата является теорема 3.2, предлагающая |-приближающий алгоритм линейной трудоемкости для решения задачи open shop с тремя машинами. Более того, этот алгоритм находит расписание, длина которого принадлежит интервалу [С, |С] точной локализации оптимумов для этой задачи.

Эта схема человеко-машинного доказательства некоторых свойств оптимального расписания представляется нам вполне продуктивной и демонстрируется в разделе 3.3 применительно к еще одной задаче теории расписаний — задаче о сборочной линии для трех машин. Для этой задачи вводится тривиальная нижняя оценка оптимума С, подобная С. В теореме 3.5 доказано, что для любого входа задачи о сборочной линии с тремя машинами длина оптимального расписания принадлежит интер

Л р Л валу [С, |6j, и границы этого интервала точны. Главные результаты диссертации Введено понятие многопараметрического анализа задач дискретной оптимизации и проведен "почти полный" четырех параметрический анализ для задачи open shop [30]. Показано, что для семейства нетривиальных подклассов задачи open shop существует; базисная система классов, включающая либо 10, либо 14 базисных классов. Окончательный ответ на этот вопрос зависит от сложности класса задач с тремя машинами, в котором каждая работа, имеет не более двух операций. Сложность этого класса является открытой проблемой с 1976 года [3]. Описаны широкие эффективно нормальные подклассы входов задачи open shop, определяемые в терминах вектора разностей. Показано, что вектор (0,3,3,3) е I4 является эффективно нормальным (теорема 2.9). Описан алгоритм жадной достройки расписания, на основании свойств которого найден широкий класс эффективно нормализующих векторов [27]. в Найден точный интервал локализации оптимумов задачи open shop с тремя машинами в терминах тривиальной нижней оценки С — max{Z/max, dmax}. Показано, что для любого входа задачи open shop с тремя машинами длина оптимального расписания для этого входа принадлежит интервалу [С, |С], и границы этого интервала точны. Для доказательства этого утверждения разработана и применена схема человеко-машинного доказательства свойств оптимального расписания, основанная на идее "склеивания работ".

• Построен алгоритм приближенного решения задачи open shop с тремя машинами, находящий расписание с длиной из интервала [С, |С] (тем самым, алгоритм является |-приближающим), В классе приближенных алгоритмов, не использующих для обоснования точности других оценок оптимума, кроме С, этот алгоритм является наилучшим как по точности, так и по трудоемкости, которая составляет 0(п).

Публикации и апробация результатов исследований

Диссертант является автором 11 научных работ. По теме диссертации опубликовано 9 работ, в том числе: 2 — в международных журналах,

2 — в журнале "Дискретный анализ и исследование операций", 5 — в тезисах конференций.

Результаты диссертанта по теме диссертации опубликованы в работах [30], [21], [27] и [26].

Результаты, представленные в диссертации, докладывались автором:

• Второй Сибирский Конгресс по Прикладной и Индустриальной Математике - ИНПРИМ-96 (Новосибирск, 1996);

• Третий Сибирский Конгресс по Прикладной и Индустриальной Математике - ИНПРИМ-98 (Новосибирск, 1998);

• Шестой Европейский Симпозиум по Алгоритмам — ESA'98 (Венеция, Италия, 1998);

• Международная конференция по дискретному анализу и исследованию операций - DAOR'2000 (Новосибирск, 2000);

• Четвертая молодежная школа по дискретной математике и ее приложениям (Москва, 2000).

Структура работы

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

1. Johnson, S.M. Optima two- and three-stage production schedules with setup times included // Naval Res. Logist. Quart. 1, 1954, P. 61-68.

2. Гимади Э. X., Глебов H. И., Перепелица В. А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики. М.: Наука, 1975. Вып. 31. С. 35-42.

3. Gonzalez, Т. and Sahni, S. Open shop scheduling to minimize finish time// J. Assoc. Сотр. Mach. 23,1976, P. 665-679.

4. Гэри, MV) Джонсон, Д. Вычислительные машины и труднореша-емые задачи // М.: Мир, 1982.

5. BArAny, I., Fiala, Т. Nearly optimum solution of multimachine scheduling problems // Szigma- Mat.-Kozgaz-das&gi Foly6irat, 15,1982 P. 177-191.

6. FlALA, T. An algorithm for the open shop problem // Math. Oper. Res. 8, 1983, P. 100-109.

7. Танаев В. c., cotckob Ю. H., СтРУСЕВИЧ В. А. Теория расписаний. Многостадийные системы // М.: Наука, 1989.

8. СЕВАСТЬЯНОВ, С.В. Полиномиально разрешимый случай задачи open shop с произвольным числом машин // Кибернетика и системный анализ. №6, 1992, С. 135-154.

9. Chen, В., Strusevitch, V.A. Approximation algorithms for three-machine open shop scheduling // ORSA Journal of Computing 5, 1993, P, 321-326.

10. Potts, C.N., Sevast'janov, S.V., Strusevich, V.A., Van Wassenhove, L.N.,Zvaneveld, C.M. The two-stage assembly scheduling problem: complexity and approximation. // Oper. Res. 43, 1995, P. 346-355.

11. Shafransky, Y.M. On a revision of some notions of the theory of computational complexity // Препринт N 1. Минск: Институт технической кибернетики, Академия наук Беларуси, 1997.ЛитератураЩ.

12. Williamson, D.P., Hall, L.A., Hoogeveen, J.A., Hurkens, G.A.J., Lenstra, J.K., Sevastianov, S,V., Shmoys, D.B. Short shop schedules // Oper.Res. 1997. V, 45, N. 2. P. 288-294.

13. Sevastianov, S.V., Woeginger, G.J., Makespan minimization in open shops: A polynomial time approximation scheme // Math. Programming, 1998, V.82, P. 191-198.

14. Chen, В., Potts, C.N., Woeginger, G.J. A review of machine scheduling: complexity, algorithms and approximability // Handbook of Combinatorial Optimization // Boston, MA: Kluwer Acad. Publ., 1998. V. 3. P. 21-169.

15. Кононов, А.В., Севастьянов, C.B. О сложности нахождения связной предписанной раскраски вершин графа // Дискретный анализ и исследование операций, Сер. 1. 2000. Т. 7, N 2. С. 21-46.Публикации автора

16. Севастьянов, С.В., Черных, И.Д. Достаточное условие эффективной разрешимости задачи open shop // Дискретный анализ и ис-след. операций, Т.З № 1, 1995, С. 57-74.

17. Kononov, A., Sevastianov, S., Tchernykh, I. When difference in machine loads leads to efficient scheduling in open shops // Annals of Oper. Res. 92, 1999, P. 211-239.

18. Каширских, К.Н., Севастьянов, С.В., Черных, И.Д. Четы-рехпараметрический анализ сложности задачи open shop // Дискретный анализ и исслед. операций, серия 1 Т.7 № 4, 2000, С. 59-77.Литература114

19. Каширских, К., Кононов, А., Севастьянов, С., Черных, И. // Полиномиально разрешимый подкласс двухстадийной задачи open shop с тремя машинами, Дискр. анал. исслед. опер., в печати.