Введение к работе
Актуальность темы. Теория расписаний занимается упорядочением протекающих во времени процессов, порожденных человеком и подвластных человеку. Из этой формулировки становится ясно, что возможная сфера приложения этой науки чрезвычайно широка. Ее актуальность проистекает из того, что человек является главной причиной (и источником) возрастания энтропии (то бишь, хаоса) на Земле, что особенно ярко и болезненно проявило себя в последнем, ХХ-м веке в виде стремительного возрастания числа техногенных катастроф и усугубления их последствий. И эта тенденция может оказаться губительной, если не противопоставить ей тенденцию оптимального упорядочения процессов, порожденных человечеством. В этом — в перспективе — видится главное предназначение науки, называемой "теорией расписаний".
Приведенный выше абзац является философским осмыслением целей той науки, которой занимается автор диссертации. Конечно, в реальности масштаб решаемых задач не столь грандиозен. Однако это проистекает вовсе не из-за того, что более глобальные задачи являются неактуальными. Просто сложность поставленных (и еще не поставленных) в этой сфере задач настолько велика, что существующие на сегодгяш-ний день методы их решения позволяют справиться пока что лишь с простейшими, "идеальными" задачами, каких в реальной жизни практически не существует. Камнем преткновения является слишком большая многовариантность решений исследуемых задач, что не позволяет за приемлемое время выбрать "самое лучшее" решение. Выход из положения здесь видится в отказе от максималистского подхода, когда считается пригодным только "самое-самое лучшее" решение. — Действительно, наилучшее (по выбранному критерию) решение часто является далеко не самым лучшим по другим критериям. (А жизнь, как известно, многогранна.) Стоит ли в таком случае тратить огромные вычислительные ресурсы и время на отыскание решения, которое, возможно, лишь на немного
превосходит другие "достаточно хорошие" решения? Этот риторический вопрос обосновывает актуальность направления, получившего в последние 2-3 десятка лет широкое развитие в дискретной оптимизации — направление построения эффективных алгоритмов приближенного решения NP-трудных задач с гарантированными оценками точности [2]. В теории расписаний для многостадийных систем это направление нача-ло развиваться несколько позже. Еще в классической монографии Танаева, Сотскова, Струсевича по Многостадийным системам теории расписаний [8], вышедшей в 1989 году, тема построения эффективных алгоритмов приближенного решения звучала достаточно скромно, — лишь в одном параграфе и в Библиографической справке. Однако сейчас можно утверждать, что построение эффективных приближающих алгоритмов стало доминирующим направлением в современной теории расписаний (см., например, обзор Чена, Поттса и Вё-гингера [10]), что подтверждает актуальность выбранной нами темы. Действительно, термин "эффективные алгоритмы", стоящий в названии диссертации, в большинстве случаев относится к приближающим алгоритмам, поскольку его применение к алгоритмам точного решения задач является весьма ограниченным.
Цель работы состоит в развитии методов построения эффективных алгоритмов для (приближенного или точного) решения NP-трудных задач, возникающих в теории расписаний и смежных областях дискретной математики.
Научная новизна. Все результаты, представленные в диссертации, являются новыми. В диссертации содержится некоторое количество принципиально новых результатов и направлений развития теории, часть из которых уже успела получить дальнейшее развитие в работах других математиков.
Безусловно новым является развиваемый автором геометрический подход к построению эффективных алгоритмов нахождения близких к оптимальному расписаний для многостадийных систем [21, 43]. Этот подход основывается на сведе-
ний рассматриваемой задачи теории расписаний к задаче нахождения оптимального порядка суммирования векторов в т-мерном пространстве, т.е. такого порядка, при котором все частичные суммы находятся в некоторой оптимальной области или семействе областей пространства.
Новым является обнаруженное автором свойство локализации оптимумов [44], которым, как выяснилось, обладают многие задачи построения кратчайших расписаний для многостадийных систем. Пользуясь этим свойством, мы можем эффективно и довольно точно оценивать значение оптимума любого примера рассматриваемой NP-трудной задачи.
Новым является подход к построению широких эффективно разрешимых подклассов примеров NP-трудной задачи open shop, основанный на анализе вектора разностей нагрузок машин [34]. Направление, связанное с поиском минимальных нормализующих векторов в пространстве R"1, представляется автору достаточно перспективным.
Построенная совместно с Г. Вёгингером [52] полиномиальная аппроксимационная схема решения задачи open shop является второй PTAS, построенной для многостадийных систем. (Первая подобная схема была чуть раньше построена Лэсли Холл для задачи flow shop [И].) Схема дает ответ на давно стоявший вопрос о сложности приближаемое задачи open shop.
Практическая ценность. Большинство рассматриваемых в теории расписаний задач имеют происхождение от задач, возникающих на практике. И хотя теоретические модели в большой степени идеализированы и абстрагированы от многих практических ограничений, всё же они обладают некоторой "остаточной" практической ценностью. Что касается результатов, изложенных в диссертации, то большинство из них связано с построением и анализом эффективных алгоритмов, т.е. таких алгоритмов, которые имеют сравнительно небольшую временную сложность, и следовательно, способны решать задачи достаточно большой размерности (т.е. такой,
какая часто возникает в практических задачах). Это обосновывает практическую ценность полученных результатов. Однако в большинстве случаев под "практической ценностью" результатов понимается их "теоретическая" ценность: насколько ценны они для теории, позволяют ли они лучше понять природу исследуемых задач, помогают ли в получении других результатов?- В этом -смысле, -например, построенная^ работе полиномиальная аппроксимационная схема для задачи open shop представляет скорее теоретическую, чем практическую ценность, так как проясняет вычислительную сложность исследуемой задачи, но вряд ли может быть использована для конструирования реальных эффективных алгоритмов ее решения. Другие результаты (такие как построение полиномиальных алгоритмов с абсолютными оценками точности для задач типа job shop [20]) помимо обоснованной выше практической ценности обладают и теоретической ценностью: на основе этих результатов Шмойс, Стайн, Вайн построили алгоритмы с относительными оценками точности для задач flow shop и job shop [14], а придуманная недавно Янсеном, Солис-Оба и Свириденко PTAS для задачи job shop [12] принципиально базируется на результатах диссертанта.
Апробация. Результаты диссертации были представлены на двух десятках международных, всесоюзных и всероссийских конференций и заслушивались на семинарах известных профессоров в Европейских университетах. В частности, результаты докладывались на: Всесоюзных и Международных конференциях по проблемам теоретической кибернетики (Ва-дулуй Водэ, Молдавия, 1982; Тбилиси, 1990; Ульяновск, 1996), Сибирских Конгрессах по прикладной и индустриальной математике (INPRIM 1996,1998,2000), 2-м Всесоюзном семинаре по дискретной математике и ее приложениям (Москва, 1987), 14-м Международном симпозиуме по Математическому программированию (Амстердам, Нидерланды, 1991), Международной конференции по Исследованию операций (Берлин, Германия, 1994), Втором, Третьем, Четвертом рабочим семина-
рам по Моделям и Алгоритмам в Планировании и Теории Расписаний (Вернигероде, Германия, 1995; Кембридж, Англия, 1997; Ренесса, Нидерланды, 1999), Дагпттуль-семинаре по Комбинаторным Приближенным Алгоритмам (Шлее Дапнтуль, Германия, 1997), Пятом Европейском Симпозиуме по Алгоритмам — ESA'97 (Грац, Австрия, 1997), 13-м и 14-м рабочих семинарах по Дискретной оптимизации (Бург, Германия, 1998; Хольцхау, Германия, 2000), Международном рабочем семинаре по методам дискретной оптимизации в теории расписаний и компьютерном дизайне (Минск, 2000), семинаре профессора Катоны по Комбинаторике в Математическом институте Венгерской академии наук (Будапешт, Венгрия, 1989), семинарах профессора Ленстры по дискретной математике в Техническом Университете Эйнховена (Эйндховен, Нидерланды, 1995), семинаре профессоров Дойбера и Аалсведе по дискретной математике в Техническом Университете Билефельда (Билефельд, Германия, 1996), семинарах профессора Брэзел по дискретной математике в Техническом Университете Магдебурга (Магдебург, Германия, 1998, 2000), семинаре профессора Танаева по теории расписаний в Институте Технической Кибернетики (Минск, 2000).
Публикации. Основные результаты диссертации опубликованы в 42 научных работах [15]-[56], в том числе: в 16 международных журналах и изданиях, 10 центральных изданиях, 4 сборниках Института математики, 4 препринтах Европейских университетов и 8 тезисах международных и всероссийских конференций. Результаты диссертации представлены также в монографиях, обзорах и учебных пособиях по теории расписаний и функциональному анализу, написанных другими авторами. Из известных диссертанту: монография Танаева, Сотскова и Струсевича по Многостадийным системам теории расписаний [8]; обзор Чена, Поттса, Вёгингера по теории расписаний [10]; учебное пособие Сотскова, Струсевича и Танаева по Математическим моделям и методам календарного планирования [7]; учебное пособие Гимади и Глебова по Дис-
кретным экстремальным задачам принятия решений [1]; учебное пособие В.М. Кадеца и М.И. Кадеца по Перестановкам рядов в пространствах Банаха [5]; монография Мас-Колела по Теории общего экономического равновесия [13].
Главные результаты диссертации
а Разработан геометрический метод эффективного прйбли~ женного решения ряда NP-трудных задач теории расписаний (типа задачи job shop) с критерием минимум длины расписания [18]-[21],[25], [27]-[28],[31]-[32],[35]- [39],[43]-[45],[47],[53], [55], для которых ранее не было известно приемлемых методов решения. Метод основан на идее приближенного сведения рассматриваемых задач к задачам о суммировании векторов в конечномерном нормированном пространстве и последующем эффективном приближенном решении полученных геометрических задач. Построенные алгоритмы обладают свойством асимптотической оптимальности, т.е. стремления погрешности получаемых ими решений к нулю с ростом размерности задачи.
b Доказана теорема 11.5 [23], устанавливающая возможность суммирования произвольного О-семейства векторов в различных выпуклых областях пространства Шт, зависящих от произвольного вектора а Є Rm. Из теоремы вытекает следствие, согласно которому для любой нормы 5 с центрально симметричным (не обязательно относительно начала координат) единичным шаром всякое s-семейство векторов может быть просуммировано в шаре радиуса т — 1 + 1/т. Этот результат улучшает как известные ранее оценки минимального радиуса суммирования в задаче о компактном суммировании векторов (в частности, экспоненциальные от тп оценки Бергстрёма [9] и Кадеца [4]), так и результаты самого автора диссертации, полученные им ранее (оценку радиуса тп, справедливую для любых, в том числе несимметричных норм [6]; ранее было показано [3], что оценка тп неулучшаема для несимметричных
норм, и было не известно, можно ли ее улучшить для произвольного т в случае симметричных норм). Примечательно, что улучшение гарантированных оденок радиуса суммирования достигнуто без потери эффективности алгоритма. с Исследованы свойства и получены верхние и нижние оденки функций Штейница (принимающих значения минимального радиуса суммирования векторов в пространстве JR"1 с той или иной нормой s) [21].
d Для задач теории расписаний типа задачи о сборочной линии и задачи job shop установлено существование интервала локализации оптимумов [36],[20],[41],[54]. Знание этих интервалов позволяет с достаточной точностью (не зависящей от таких параметров исходной задачи как число работ) эффективно локализовать значение оптимума любого примера рассматриваемой NP-трудной задачи.
е Определено понятие нестрогого суммирования векторов в семействе областей m-мерного пространства. Для произвольной нормы s в R2 получены достаточные условия, гарантирующие возможность нестрогого суммирования любого 5-СЄМЄЙ-ства векторов в исходной выпуклой области пространства (теоремы 13.8 и 13.21 [28]). Разработаны эффективные алгоритмы нахождения такого суммирования при выполнении достаточных условий. С использованием нестрогого суммирования векторов найдены неулучшаемые интервалы локализации оптимумов для ряда задач нахождения кратчайшего расписания для трех машин.
f На основе понятия нормальности [34] найдены широкие полиномиально разрешимые классы примеров задачи open shop. Представлено три разных подхода к построению таких классов: на основе метода компактного суммирования векторов [44], с использованием усовершенствованного метода Фиалы [24] и на основе анализа разностей нагрузок машин [26],[29], [34]. Из полученных результатов следует, что нормальность является типичным явлением на множестве примеров задачи open shop.
g Для многопроцессорной задачи open shop с фиксированным числом машин совместно с Г. Вёгингером построена полиномиальная аппроксимационная схема (PTAS) линейной трудоемкости [15]. Таким образом, найден ответ на давно стоявший открытый вопрос о границе приближаемости задачи open shop. В то же время, для любого р < 5/4 доказана невозможность (при условии P^NP) построения /^приближающего^ полиномиального алгоритма решения задачи open shop в случае, когда число машин является переменной1. Тем самым, в анализе сложности этой задачи установлен "водораздел" между случаями, допускающими построение полиномиальной ап-проксимационной схемы (когда т — любое фиксированное число), и случаями, когда такой схемы не существует (т — переменная).
h Найдены тесные связи между комбинаторными задачами из различных областей дискретной математики (такими как задача объемно календарного планирования, задача нахождения подмножества векторов с заданной суммой, задача компактного суммирования векторов, задача нахождения равномерного разбиения множества предметов, задача эквидистан-ции в булевом кубе, задача балансировки, и др.). Эти связи позволяют использовать результаты анализа одних задач для отыскания интересных свойств решений других задач [21], [50]. Так например, нетривиальные нижние оценки определенных нами функций Штейница для норм lp, р > 2, могут быть получены с использованием матриц Адамара, а для произвольной нормы s — с помощью функции Дворецкого.
Структура и объем работы. Диссертация изложена на 283 страницах, содержит два введения (неформальное и формальное), три части и библиографию (136 наименований). Третья часть диссертации состоит из четырех глав. Вся работа делится на 45 разделов, содержит 23 рисунка и 2 таблицы.
Результат получен автором диссертации независимо и опубликован в совместной статье с шестью соавторами [56].