Геометрические методы и эффективные алгоритмы в теории расписаний тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РОССИЙСКАЯ АКАДЕМИЯ НАУК Сибирское отделение Институт математики им. С.Л. Соболева

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

СЕВАСТЬЯНОВ Сергей Васильевич

у, о и«;

1 УДК 519.854

ГЕОМЕТРИЧЕСКИЕ МЕТОДЫ И ЭФФЕКТИВНЫЕ АЛГОРИТМЫ В ТЕОРИИ РАСПИСАНИЙ

Специальность 01.01.09 — математическая кибернетика

Автореферат

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

Новосибирск — 2000

Работа выполнена в Институте математики им. С. JI. Соболева СО РАН

£)фициальные_оппоненты: доктор физико-математических nayi

профессор B.C. Танаев, доктор физико-математических нау! профессор A.A. Колоколов, доктор технических наук, профессор В.Н. Павлов

Ведущая организация: ВЦ РАН

Защита состоится ноября 2000 г. в 16 часов на за-

седании диссертационного совета Д 002.23.03 в Институте математики им. С. Л. Соболева СО РАН по адресу: пр. Коптюга, 4, 630090, г. Новосибирск.

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

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

Ученый секретарь диссертационного совета, доктор физико-математических наук \У '""С. Г. Фосс

/3 {13, $ Энекретиое О^

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

Актуальность темы. Теория расписаний занимается упорядочением протекающих во времени процессов, порожденных человеком и подвластных человеку. Из этой формулировки становится ясно, что возможная сфера приложения этой науки чрезвычайно широка. Ее актуальность проистекает из того, что человек является главной причиной (и источником) возрастания энтропии (то бишь, хаоса) на Земле, что особенно ярко и болезненно проявило себя в последнем, ХХ-м веке в виде стремительного возрастания числа техногенных катастроф и усугубления их последствий. И эта тенденция может оказаться губительной, если не противопоставить ей тенденцию оптимального упорядочения процессов, порожденных человечеством. В этом — в перспективе — видится главное предназначение науки, называемой "теорией расписаний".

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

превосходит другие "достаточно хорошие" решения? Этот риторический вопрос обосновывает актуальность направления, получившего в последние 2-3 десятка лет широкое развитие в дискретной оптимизации — направление построения эффективных алгоритмов приближенного решения ЫР-трудных задач с гарантированными оценками точности [2]. В теории расписаний для многостадийных систем это направление начало развиваться несколько позже. Еще в классической монографии Танаева, Сотскова, Струсевича по Многостадийным системам теории расписаний [8], вышедшей в 1989 году, тема построения эффективных алгоритмов приближенного решения звучала достаточно скромно, — лишь в одном параграфе и в Библиографической справке. Однако сейчас можно утверждать, что построение эффективных приближающих алгоритмов стало доминирующим направлением в современной теории расписаний (см., например, обзор Чена, Поттса и Вё-гингера [10]), что подтверждает актуальность выбранной нами темы. Действительно, термин "эффективные алгоритмы", стоящий в названии диссертации, в большинстве случаев относится к приближающим алгоритмам, поскольку его применение к алгоритмам точного решения задач является весьма ограниченным.

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

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

Безусловно новым является развиваемый автором геометрический подход к построению эффективных алгоритмов нахождения близких к оптимальному расписаний для многостадийных систем [21, 43]. Этот подход основывается на сведе-

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

Новым является обнаруженное автором свойство локализации оптимумов [44], которым, как выяснилось, обладают многие задачи построения кратчайших расписаний для многостадийных систем. Пользуясь этим свойством, мы можем эффективно и довольно точно оценивать значение оптимума любого примера рассматриваемой NP-трудной задачи.

Новым является подход к построению широких эффективно разрешимых подклассов примеров NP-трудной задачи open shop, основанный на анализе вектора разностей нагрузок машин [34]. Направление, связанное с поиском минимальных нормализующих векторов в пространстве R"1, представляется автору достаточно перспективным.

Построенная совместно с Г. Вёгингером [52] полиномиальная аппроксимационная схема решения задачи open shop является второй PTAS, построенной для многостадийных систем. (Первая подобная схема была чуть раньше построена Лэсли Холл для задачи flow shop [11].) Схема дает ответ на давно стоявший вопрос о сложности приближаемости задачи 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), Пятом Европейском Симпозиуме по Алгоритмам — Е8А'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], устанавливающая возможность суммирования произвольнохчз О-семейства векторов в различных выпуклых областях пространства Мт, зависящих от произвольного вектора а 6 Rm. Из теоремы вытекает следствие, согласно которому для любой нормы s с центрально симметричным (не обязательно относительно начала координат) единичным шаром всякое ¿-семейство векторов может быть просуммировано в шаре радиуса т — 1 + 1/т. Этот результат улучшает как известные ранее оценки минимального радиуса суммирования в задаче о компактном суммировании векторов (в частности, экспоненциальные от m оценки Бергстрёма [9] и Кадеца [4]), так и результаты самого автора диссертации, полученные им ранее (оценку радиуса тп, справедливую для любых, в том числе несимметричных норм [6]; ранее было показано [3], что оценка m неулучшаема для несимметричных

норм, и было не известно, можно ли ее улучшить для произвольного т в случае симметричных норм). Примечательно, что улучшение гарантированных оценок радиуса суммирования достигнуто без потери эффективности алгоритма, с Исследованы свойства и получены верхние и нижние оценки функций Шгпейница (принимающих значения минимального радиуса суммирования векторов в пространстве JRm с той или иной нормой s) [21].

d Для задач теории расписаний типа задачи о сборочной линии и задачи job shop установлено существование интервала локализации оптимумов [36],[20],[41],[54]. Знание этих интервалов позволяет с достаточной точностью (не зависящей от таких параметров исходной задачи как число работ) эффективно локализовать значение оптимума любого примера рассматриваемой NP-трудной задачи.

е Определено понятие нестрогого суммирования векторов в семействе областей ш-мерного пространства. Для произвольной нормы s в R2 получены достаточные условия, гарантирующие возможность нестрогого суммирования любого ,s-семейств а векторов в исходной выпуклой области пространства (теоремы 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].

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

Первая группа задач рассматривается в разделе 10. Вначале приводится доказательство леммы 10.2, лежащей в основе доказательства теоремы 11.5 о компактном суммировании векторов, а также используемой в конце раздела 10 при решении задачи о подмножестве векторов с заданной суммой. Затем мы переходим к рассмотрению подмножеств ребер графа и определяем понятие независгшого подмножества ребер. Это понятие оказывается тесно связанным с понятием независимого множества векторов. Доказывается лемма 10.6 об алгоритме нахождения базы семейства ребер, являющаяся аналогом леммы 10.2 об алгоритме нахождения базы семейства векторов.

Далее рассматривается оптимизационная задача ПВЗСт)Я(Х, х) о нахождении такого подсемейства векторов заданного семейства X, чтобы его сумма была наиболее близка к заданному значению х (где близость оценивается в заданной — вообще говоря, произвольной — норме в). Выделяется два случая этой задачи, допускающие эффективное приближенное решение с гарантированной точностью: когда точка

х принадлежит параллелепипеду, построенному на векторах из X (в этом случае задача интерпретируется как задача о ближайшей вершине (БВ): требуется найти вершину параллелепипеда, наиболее близкую к его заданной точке), и когда норма в допускает линеаризацию (т.е. ее единичный шар представим в виде пересечения конечного числа замкнутых -полупространств)------

Для задачи БВ с нормой 1Ж доказывается теорема, предоставляющая эффективное приближенное решение задачи БВт>гоо с априорной оценкой точности, на порядок лучшей по сравнению с оценкой т/2, гарантируемой в случае произвольной НОрМЫ 6'.

Теорема 10.13 Существует алгоритм приближенного решения задачи БВщ^ с временной сложностью 0(пт2), который для любого заданного семейства векторов X = {x¿ | i 6 Nn} С Bs¡m и любой точки х = хг е

(Ai е [0,1], i е N„) находит такое подсемейство векторов {cc¿ | г" € iV'}, N' С Nnj что

х - YlXi

iEN'

^ Г k(n,m)\/mln2те, для всех т;

~ \ 0.735 • к(п, m)Vrrihi2m, длят > 1500;

1 ( ^ Í 1 + m> nPU П ^ П1> к{п,т) = < 2

при п > тп.

В конце раздела 10 рассматривается задача ПО (А, д) о нахождении такого подмножества операций, которое содержало бы заданное количество д операций каждой работы, и при этом давало бы нагрузку на каждую машину, пропорциональную числу (¡/к. В лемме 10.14 доказывается возможность решения этой задачи с большой точностью и малой трудоемкостью.

В разделе 11 рассматривается задача о компактном суммировании векторов (КСВ), в которой для заданного ¿-семейства векторов X — {х1,... , хп} в пространстве с нормой в

'jTi, . . . ,7ГП), минимизиру-Tfc X

требуется найти перестановку 7Г = ющую функцию Дх(7г) = тахАбКя

(Конечное семейство векторов X = .. ,хп} С Rm называется s-семейством, если сумма векторов равна нулю, а s-норма каждого вектора не превосходит 1.) Формулируется одномерный аналог этой задачи — задача о компактном суммировании чисел (КСЧ). Через КСЧ(^) обозначается задача на распознавание, в которой для семейства чисел е [—1,1] | (yi = 0} требуется определить, существует ли перестановка 7г, задающая порядок суммирования чисел, при котором все частичные суммы по абсолютной величине не превосходят ¡1.) В теореме 11.4 доказывается, что при любом фиксированном ¡л Е 1) задача КСЧ(р) NP-uолна в сильном смысле, в то время как при /х > 1 ответ в задаче КСЧ(/х) всегда положителен, а при ¡л < | — всегда отрицателен. Как следствие, задача КСВ уже в одномерном случае оказывается NP-трудной в сильном смысле, что оправдывает последующие результаты об алгоритмах ее приближенного решения.

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

Теорема 11.5 Для любого 0-семейства векторов {х\,... ,ïJ = IC Rm и вектора а € Ет с трудоемкостью 0(п2т2) находится перестановка ж = (7Гх,... , 7г„) такая, что

к

£ ^ 6 (т - 1)В(Х) + Ва, к е Nn,

i=l

где В{Х) = convia:!,... ,хп}, Ва = conv{0,o - ^В(Х)}.

В качестве прямого следствия для произвольной симметричной нормы s получаем возможность эффективного суммирования любого s-семейства векторов внутри шара радиуса m—1 + j^. Полученная оценка радиуса суммирования является рекордной. Результат остается в силе и в случае несимметричной нормы, если ее единичный шар центральносимметричен (не обязательно относительно начал а координат). Из доказы- . ваемой далее теоремы 11.10 следует, что "коэффициент растяжения" выпуклого множества Ф, содержащего векторы исходного 0-семейства X, можно понизить до тп — 1, если Ф есть выпуклое неограниченное множество, имеющее объемный рецессивный конус.

В разделе 12 выводятся оценки и исследуются свойства функций Штейница ips(m). (Функция ipa(m) принимает значения, равные минимальному радиусу шара нормы s в пространстве К"1, внутри которого при подходящем порядке суммирования может быть просуммировано любое s-семейство векторов.) В дополнение к верхней оценке <ps{m) < тп — 1 + вытекающей из теоремы 11.5, получены условные и безусловные нижние оценки функций ipa{m) для норм lp, р > 1.

Теорема 12.2 Для норм lp {р > 1) в пространстве К2 выполняются следующие оценки функций Штейница:

,„ т , / 1(1+2")^, при р е [1,2];

При этом min(pij)(2) по всемр > 1 равен л/о/4 и достигается на евклидовой норме, а max<¿>íp(2) по всемр > 1 равен 3/2 и достигается на нормах li и

Теорема 12.4 infs (ps{2) > л/Щ.

Теорема 12.6 Пусть т > 3, р > 2. Если при некотором п < гп существует матрица АП) то

Если тп = — 1 и существует матрица Лт+1, то

щр{т) > + 2 + #сли матрица Ап существует для некоторого п < т+1, то

^ооИ >

^л/ 71 + 4

Следствие 12.7 Если верна гипотеза Адамара и матрицы Ап существуют для всех п, кратных 4, то для всех т > 3, р > 2, выполняются оценки

\/т + 3, при т — Ак,

у/т 4- 2, при т = 4& + 1,

х/ттТ+Т, при тп — 4к + 2,

1

- 2 ' '

утп + 2+^, при тп = 4fc+ 3.

WcoM >

-Vm + 2

(12.1)

Показано, что для справедливости наилучшей (в данном методе) оценки (12.1), достижимой при выполнении гипотезы Адамара, достаточно, чтобы гипотеза Адамара выполнялась в ослабленной форме: для всех п, равных квадрату четного числа.

С использованием известного результата о плотности порядков матриц Адамара на целочисленной решетке, для норм lp, р > 1, в случае произвольного тп получаем:

Теорема 12.13 Для любого е > 0 существует такое целое т0, что для всякого т>т0 выполнена оценка

4>1р{т) > Q - e^j л/т, V р > 1.

Теорема 12.11 infp>, iph{m) ^ ос.

Вопрос о бесконечном росте минимума значений функций Штейница по всем нормам s остается открытым. Как показывается в разделе .19, этот вопрос сводится к "более простому" (однако остающемуся до сих пор открытым) вопросу о нижней границе функции Дворецкого.

В разделе 13 вводится понятие нестрогого суммирования векторов в заданной области или семействе областей. (Перестановка 7г — (тт\ ,... , 7ГП) задает нестрогое суммирование векторов семейства X = {zi,... ,хп} С К™ в области G С К"1, если при любом /с 6 N„ из xip1 ^ G следует х^ G G, где

Ж7Г = 12j=1 XKj •)

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

Доказывается NP-трудность в сильном смысле задачи о нестрогом суммировании чисел (теорема 13.18). Для двумерного пространства и произвольной нормы s находятся достаточные условия (теоремы 13.8 и 13.21), которым должно удовлетворять выпуклое множество G С К2, чтобы всякое s-семейство векторов из R2 могло быть нестрого просуммировано в G.

Теорема 13.8 Пусть в пространстве R2 с нормой s задано выпуклое замкнутое неограниченное множество G, содержащее точку 0 и такое, что все его О-хорды имеют s-норму, не меньшую единицы. Тогда для всякого s-семейства векторов X = {а;а,... ,£„} С R2 существует перестановка 7г = (tti, ... , 7Гп), задающая нестрогое суммирование векторов X в G. Если при этом известен рецессивный конус множества G, то искомая перестановка п находится за O(nlogn) операций.

Теорема 13.21 Пусть на плоскости заданы норма я с единичным шаром Н и выпуклое множество С, такое что

если Х\ С, х-2 ^ <3 и [ж1, Х2] ПЯ^0, то ||ж2 — || > 1.

Тогда для любого в-семейства векторов X = {х],... , хп} С Е2 существует (и находится с трудоемкостью 0(п1о£п)) перестановка тг = (7Гх,... , 7Г„), задающая нестрогое суммирование векторов из X в С.

В разделе 14 мы переходим от задач нестрогого суммирования в единичных областях к задачам о нестрогом суммировании в семействах областей. Как будет видно из третьей части диссертации, при анализе задач о нахождении кратчайших расписаний в качестве таких семейств выступают семейства замкнутых полупространств т-мерного пространства. Поэтому далее исследуется именно этот случай. Формулируется С оптимизационных задач о нахождении нестрогого суммирования векторов из исходного О-семейства в оптимальном (согласно какому-то критерию) семействе полупространств. Задачи различаются критериями и ограничениями на выбор полупространств. В лемме 14.4 показывается, что одна из этих задач без потери точности сводится к другой с понижением размерности пространства на единицу. Далее переходим к решению сформулированных задач в двумерном пространстве. С использованием результатов из предыдущего раздела получаем эффективные алгоритмы приближенного решения этих задач с гарантированными оценками точности, причем показано, что две из полученных оценок являются неулучшаемыми.

В разделе 15 доказывается теорема о суммировании семейства векторов в прямоугольной области т-мерного пространства, ограниченной единицей по одной координате и константами — по другим координатам2. Тем самым, получен от-

2Принадлежащий диссертанту результат из совместной статьи с В. Ба-нащиком [51].

вет на вопрос Вараня-Гринберга о существовании границы Штейница с единичной компонентой в пространстве произвольной размерности. (Ранее положительный ответ на этот вопрос был известен лишь для двумерного пространства.)

Для задачи суммирования векторов внутри минимального угла в пространстве Кш совместно с C.B. Августиновичем [33] получены-теоремыД5.3-иЛ5.8, ^^которых_до^ывается^воз-можность суммирования любого О-семейства векторов из М2 внутри угла 7г/3 (угол является минимально возможным) и векторов из К3 — внутри прямоугольного октанта.

В разделе 16 ставятся открытые вопросы, возникающие в задачах о подмножествах и перестановках векторов, рассмотренных в первой части диссертации.

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

В разделе 17 вводится понятие ранга гт(х) целого числа а; е {0,1,... , m}. (С небольшой поправкой, — за исключением числа m, — ранг гт(х) равен номеру младшего бита, содержащего единицу в двоичной записи числа х.) Вводится отношение порядка на множестве чисел {0,1,... , m} (сравнение чисел по рангу) и с помощью рекуррентных соотношений определяются функции ôm(x), ф^(х), Ф~п{х) и число фт>. Главным результатом раздела является лемма 17.10, в которой находится точное значение числа фт'. (Результаты этого раздела используются при построении эффективного алгоритма решения задачи open shop в разделе 26.)

В разделе 18 рассматривается задача РРП о равномерном разбиении множества из п предметов на I подмножеств. При этом каждый предмет характеризуется m параметрами, и равномерность разбиения требуется по каждому из m параметров. Экономической интерпретацией этой задачи является

известная Задача объемно-календарного планирования (ОКП). В задаче ОКП требуется годовой план предприятия, представленный п наименованиями, разбить по кварталам (или по месяцам) как можно равномернее по каждому из m параметров. В теореме 18.1 доказывается возможность эффективного приближенного решения задачи РРП с гарантированной оценкой точности при условии существования подобного алгоритма для задачи КСВ. С учетом алгоритма решения задачи КСВ из раздела 11 получаем следствие 18.2, согласно которому задача PPnm>s (X, I) с п предметами и произвольной нормой s решается с трудоемкостью 0(п2т2) и гарантированной оценкой

Сх(Н)<2(т-1 + ~У

Однако последующий анализ, проведенный в теореме 18.3 и следствии 18.4, показывает, что более перспективным методом решения задачи РРП оказывается ее сведение к задаче БВ, рассматривавшейся нами в разделе 10.

Теорема 18.3 Пусть существует алгоритм Л трудоемкости 0(Та{п, тп))> который для заданного т, нормы s в пространстве Ет, любого s-семейства векторов X = {а^,... , хп} С Rm и любой точки х € Р{Х) находит решение задачи BBm¡s(X,x) с априорной оценкой ^ Ф»{т)- Тогда су-

ществует алгоритм трудоемкости 0(7¿(n,m)r) для отыскания решения H задачи РРПтя(Х,г) с оценкой

Сх(Н)<и(г)ф,(т),

где v(i) определяется из рекуррентных соотношений:

v{l) = 0; v{i) = min max{v(i')+l/i',v(i-i')-\-l/(i-i')}, i > 1. i'eNi-i

Применяя лемму 10.8, получаем

Следствие 18.4 Для задачи РРПП1;$(Х,г) с п предметами и произвольной нормой в с трудоемкостью 0(пгт2) может быть найдено решение Н с гарантированной оценкой

Сх(Я) < 1.00023 т. (18.2)

При г < 250 оценка улучшается до (х(Ю — Тп-

Коэффициент перед т в (18.2) является точной (с точностью до последней значащей цифры) верхней границей значений функции ь>{1)/2 из теоремы 18.3. При этом максимум функции и{1) достигается при V = 909.

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

В разделе 20 рассматривается несколько комбинаторных задач различной природы, таких как задача эквидистанции (о нахождении вершины единичного куба, наиболее одинаково удаленной от вершин из заданного семейства), задача о балансировке (где для заданного семейства подмножеств конечного множества требуется найти подмножество С наиболее равномерно делящее каждое из подмножеств), задача Бека-Фиалы об округлении и задача Дворецкого (о нахождении коэффициентов е^ = ±1, минимизирующих взвешенную сумму Х^Ег^г векторов заданного семейства {хь... , Показывается, что имеются тесные взаимосвязи между этими

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

<Ps{m) > ^D3(m),

где Ds(m) = sup min — функция Дворецкого (sup

берется по всем конечным семействам векторов {.хг} С Мт, ||ж,-||в < 1, а min -- по всем наборам из р чисел {е* = ±1})-

В разделе 21 ставятся открытые вопросы, возникающие в задачах из второй части диссертации.

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

В первой главе рассматриваются системы с нефиксированными маршрутами. В разделе 23 вводится понятие нормального примера, т.е. примера, длина оптимального расписания которого совпадает с максимальной машинной нагрузкой (¿max)- Для каждого примера с га машинами определяется га-мерный вектор разностей нагрузок машин (VOD): принимая Ртах (максимальную длительность операции) за единицу и нумеруя машины в порядке невозрастания их нагрузок, полагаем VOD=(ö(l),... ,6(т)) = (Lm^-LuLmsx-L2,... ,Lmax-Lm). Вводится понятие нормализующего вектора, т.е. такого вектора Д е Кта, что любой m-машинный пример с VOD = А яв-

ляется нормальным. Вектор А называется эффективно нормализующим, если он нормализующий, и класс примеров с VOD = А является эффективно разрешимым. Естественным образом определяются минимальный нормализующий и минимальный эффективно нормализующий векторы в JRm.

Показывается, что вектор (0,1) является единственным минимальным нормализующим и единственным минимальным эффективно нормализующим ~вектором~ъ ~R2 —В -разделе 24 доказывается теорема 24.1, из которой следует, что вектор (0,0,2) является единственным минимальным нормализующим и единственным минимальным эффективно нормализующим вектором в R3 (результат из совместной статьи с Кононовым и Черных [34]).

В следующих двух разделах (25 и 26) эффективно нормальные классы примеров строятся на основе сравнения максимальной машинной нагрузки (Lmax) с длительностью максимальной операции (ртах). При этом в разделе 25 оптимальное расписание строится с использованием алгоритма компактного суммирования векторов, а в разделе 26 — с помощью модифицированного алгоритма Фиалы. В обоих случаях показывается, что если выполняется соотношение вида Lmax > i](m)pmaDi для определенной функции Т}(т) от числа машин, то длина оптимального расписания равна Lmax, и это расписание строится эффективно. Ясно, что чем меньше функция т?(т), тем более широкий эффективно разрешимый класс она определяет. В первом случае функция Т}(т) имеет порядок 0(т2), во втором — 0{т logтп), но при малых т проигрывает первой функции из-за большой константы. По сравнению с аналогичным алгоритмом Фиалы модифицированный алгоритм из раздела 26 сужает примерно в 6 раз интервал неблагоприятных значений £maxj а Б благоприятном случае имеет на два порядка меньшую трудоемкость. Для 3-маишнной задачи open shop в теореме 25.2 на основе результатов о нестрогом суммировании векторов из разделов 13, 14 строится алгоритм трудоемкости O(nlogn), который отыскивает оптимальное решение для лю-

бого примера, удовлетворяющего соотношению Z-max > 1pmsx.

В связи с приведенными выше результатами естественно задать вопрос, при какой минимальной функции т] (тп) соотношение Lmax > Tj(m)pmax гарантирует свойство нормальности примера. Результаты предыдущих разделов дают верхние оценки этой функции. Нижняя оценка сформулирована в теореме 27.1: г)(тп) > 2т — 2. В частности, при т = 3 отсюда получаем 4 < rj(3) < 7.

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

Теорема 30.2 Класс примеров задачи open shop с т машинами и п работами, задаваемый соотношениями

5(2) >т~ 1, Lm3X > 5.45 т - 7,

является эффективно нормальным. Оптимальное расписание для каждого из этих примеров находится жадным алгоритмом трудоемкости 0(п2тп2).

Известен простой результат Анны Рачмань, согласно которому для любого примера задачи open shop за время 0(nrri2) может быть построено расписание с оценкой

Cmax(S') < Lmax + (т — 1)Ршах-

В теореме 30.3 строится алгоритм такой же трудоемкости, погрешность которого зависит от соотношения между Хтах и Ртах- Одним из следствий этой теоремы является оценка

ТП — 1

Cmax('S') ¿max "I ^ Pmaxj

которую гарантирует наш алгоритм при выполнении соотношения Lmax > (7m - 6)pmax.

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

Утверждение 34.4 Следующие векторы являются эф-

-фективпо_нормализующими в К4: (0,3,3,3), (0,0,5,5),

(0,0,2,6), (0,0,0,7).

Хотя в пространстве К4 нам пока не известно ни одного минимального нормализующего (минимального эффективно нормализующего) вектора, с учетом утверждения 34.4 получаем следующее

Утверждение 34.7 В пространстве К4 существует по крайней мере два различных минимальных нормализующих вектора и два различных минимальных эффективно нормализующих вектора.

Теорема 34.5 Следующие векторы Д являются эффективно нормализующими в Шт при т > 5: (0, яг,... ,т); (0,т-2,... ,т - 2,5.45т - 12.45) ; (0,0,т + 1,... ,гп + 1); (0,0,т,... ,т,2т-2); (0,0,0, т + 2,... ,т + 2); (0,3,3,3,т + 3,... ,т + 3); (0,0,5,5,т + 3,... ,т + 3); (0,0,0,6,т +3,... ,т + 3); (0,... , 0, к ■+ га — 1,... , к + т — 1),

V к < фп или V тп> к2 - к + где Д(г) = 0, г е (0,... , 0, т2 — 2т +

(0,... , 0, - 1) ^2(т - 1) + |т - 14|);

(0, к,... , к, к + гп — 1,... , к -Ь т — 1), V к = 5,... , т — 1,

где А(г) = к, г = 2,... , к; Д(г) = к + т — 1, г — к + 1,... , т;

(0, к - 1,... , к - 1, к + т — 2,... , к + га - 2, тах{5.45/г - 7,

2т - 2}), V к < т - 2, где Д(г) = к - 1, г = 2,... ,к;

Д(г) = к + т — 2, г = к + 1,... , т — 1;

(0,0,0,6,8,10,... ,2т — 2).

Следствие 34.6 Следующие 7 векторов являются наименьшими из известных эффективно нормализующих векторов в R5: (0, 5, 5, 5,5); (0,3,3,3,8); (О, О, б, 6,6); (0,0,5,5,8); (О, 0,0,7,7); (О, О, О, б, 8); (О, О, О, О, Щ).

В разделе 35 для многопроцессорной задачи open shop (в которой имеется г цехов с идентичными параллельными машинами в каждом цехе, а каждая работа имеет г операций) строится полиномиальная аппроксимационная схема (PTAS) при условии, что общее по всем цехам число машин (т) ограничено константой. Схема имеет линейную от числа работ (п) трудоемкость, причем коэффициент перед п полиномиален от т и не зависит от задаваемой точности е. (Экспоненциальная зависимость оттие "спрятана" в аддитивной константе.)3 В противоположность этому результату в теореме 36.2 доказывается, что при нефиксированном числе машин для обычной задачи open shop и любой константы р < 5/4 не существует полиномиального р-приближающего алгоритма (при условии P^NP), а следовательно, не существует и PTAS4.

В разделе 37 рассматривается общая система открытого типа. От классической задачи open shop она отличается тем, что количество операций (г/) каждой работы j является параметром, не зависящим от числа машин т, и тем, что множество допустимых исполнителей каждой операции может быть произвольным подмножеством множества {Mi,... , М,п}. Доказывается теорема 37.1, согласно которой для открытой системы общего вида с т машинами и R операциями существует алгоритм трудоемкости 0(И?т2), строящий приближенное расписание S с оценкой точности Cmax(S) — Cmax(S0{)t) < ?"maxPmax, где rrnax = maxj Tj. При этом если все операции имеют одинаковую длину, то задача решается точно (теорема 37.2).

Вторая глава третьей части посвящена задаче flow shop. В теореме 39.1 показывается ее сведение к задаче о нестро-

3Результаг из совместной статьи с Г.Вёгингером, см. [52], [15].

^Результат из совместной статьи с шестью соавторами, см. [56].

гом суммировании векторов в семействе полупространств. С использованием известных алгоритмов нестрогого суммирования из Части I получаем теорему 39.3, согласно которой 4-машинная задача flow shop может быть решена с трудоемкостью О (п log п) и гарантированной оценкой Спиис(5'я-) < Lmax+6ртах, причем отыскиваемое алгоритмом расписание S^ является перестановочным. Для задачи трех машин нестрогое

суммирование дает алгоритм трудоемкости О(п) с гарантированной неулучшаемой оценкой Cmsx(S„) < I/max+3pmax (теорема 39.4). В случае произвольного числа машин с использованием алгоритма компактного суммирования векторов получаем:

Теорема 39.6 Существует алгоритм трудоемкости 0(п'2т2), который для любого примера задачи flow shop с т машинами и п работами находит перестановочное расписание с оценкой длины

Cmax(S„) < Lmzx + (т - 1) (т - 2 + Р™ах

Далее в разделе 40 выводятся оценки функции ДFs(jn), определяющей минимальный интервал локализации оптиму-мов по всем примерам m-машинной задачи flow shop.

В последнем разделе главы 2 рассматривается многопроцессорная r-стадийная задача flow shop. В теореме 41.1 доказывается возможность ее эффективного решения с оценкой

Cmax(S') < Lmax -f |'T2 ~ 3r + 3 4- — ^ Pmaxi

не зависящей ни от числа работ, ни от числа машин.

В третьей главе рассматривается задача о сборочной линии (CJI). Система "сборочная линия" характеризуется тем, что в ней не действует запрет на одновременное выполнение операций, принадлежащих одной работе. По этой причине

данная система не вписывается ни в одну из трех других рассматриваемых нами систем. Однако для задачи построения кратчайшего расписания в этой системе удается также показать ее сводимость к некоторой задаче о нестрогом суммировании векторов (теорема 41.2). Далее возможно применение одного из разработанных нами алгоритмов. В частности, в случае трех машин это сведение позволяет строить алгоритм трудоемкости 0(п logn), который для всякого примера задачи СЛ с тремя машинами и п работами находит перестановочное расписание Sn с неулучшаемой оценкой длины:

Стаx(»$V) 5; ^тах 1-25^тах.

В последней главе рассматриваются наиболее общие (и наиболее сложные для анализа) многомаршрутные задачи типа job shop. Долгое время для них не было известно никаких приближенных алгоритмов с гарантированными оценками качества. Нашим главным результатом здесь является

Теорема 44.2 Для любого примера задачи job shop с тп машинами, п работами и не более чем г операциями каждой работы его оптимум лежит в интервале Ijs = [Ьтах, ¿max + Ф Ртах]> где ф = г(г-1)(тг + 1). Существует алгоритм трудоемкости 0(n2m2r2), который для любого примера строит расписание S со значением длины из интервала Ijs-

В теореме 44.3 этот результат обобщается на случай произвольного множества альтернативных исполнителей каждой операции и произвольного частичного порядка на множестве операций каждой работы. В качестве интервала локализации оптимумов в этом случае берется интервал [£°пРах> ^тах + (Ф + 1 )ргаах], где — эффективно находимое значение оптимума в задаче о максимальном потоке, равномерном по стокам (из раздела 19).

Найденный нами в общем случае интервал локализации оптимумов задачи job shop может быть значительно уменьшен в

некоторых частных случаях. Так например, согласно теореме 42.2, для ациклической задачи job shop (известной также по фамилиям ее авторов — Шэлдона Акерса и Джойс Фридман) в случае трех машин оптимумы всех примеров содержатся в интервале [Lmax, Lmax+5.5pm&x], а приближенное решение из этого же интервала находится с трудоемкостью 0(n\ogn). В разделе 43 рассматриваются двухмаршрутные задачи для трех машин. Как нетрудно убедиться, всего возможно три несводим мых друг к другу конфигурации из двух маршрутов (каждый из которых является некоторой перестановкой машин). В диссертации соответствующие им задачи обозначены через R231, R213 и R321. Ясно, что двухмаршрутные задачи занимают промежуточное положение между (одномаршрутной) задачей flow shop и задачей Акерса-Фридман (в которой при ш — 3 возможно одновременное присутствие до 6 различных маршрутов), поэтому естественно ожидать, что их интервалы будут промежуточными по длине. Это ожидание подтвердилось, причем длины всех трех найденных интервалов оказались разными: 5, 4 и 3, соответственно (в единицах величины ртах)-Наилучшего результата удалось достичь для задачи встречных маршрутов (R321): ее интервал ([L max) ¿'max "t" Зртах ]) совпадает с неулучшаемым интервалом одномаршрутной задачи, а следовательно, является неулучшаемым и для задачи R3215.ripH отыскании интервалов для задач R231 и R213, а также трехмашинной задачи Акерса-Фридман использовались алгоритмы решения задач о нестрогом суммировании векторов из раздела 14.

В качестве вспомогательной при построении расписания в задаче R321 использовалась задача ДЗВМ (двухстадийная задача встречных маршрутов). В ней все работы первого маршрута имеют операции с ненулевыми длительностями лишь на машинах 1 и 2, а все работы второго маршрута — на машинах 3 и 2 (выполняемые в указанном порядке). В теореме 43.1 доказана NP-трудность задачи ДЗВМ в сильном смысле. Нетруд-

5Результат опубликован в совместной работе с Ю. Неумытовым [17].

но видеть, что при перенумерации машин (при выборе второй машины в качестве третьей) задача становится эквивалентной двухстадийной задаче flow shop для трех машин, причем такой, в которой только две из трех групп работ с различными маршрутами являются непустыми. Это усиливает результат, приведенный в монографии [8, стр. 42].

Литература

[1] Гимади Э. X., Глебов Н. И. Дискретные экстремальные задачи принятия решений. Учебное пособие // Новосибирск: НГУ, 1991.

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

[3] Гринберг В. С., Севастьянов С. В. О величине константы Штейница // Функциональный анализ и его приложения. 1980. Т. 14. С. 56-57.

[4] Кадец М. И. Об одном свойстве векторных ломаных в п-мерном пространстве // Успехи мат. наук. 1953. Т. 8. С. 139-143.

[5] Кадец В. М., Кадец М. И. Перестановки рядов в пространствах Банаха // Тарту: Тартуский Государственный Университет, 1988.

[6] Севастьянов С. В. Приближенные алгоритмы в задачах Джонсона и суммирования векторов // Управляемые системы. Новосибирск: Изд-во Ин-та математики, 1980. С. 64-73. (Тр./ АН СССР. Сиб. отд-ние. Ин-т математики. Вып. 20.)

[7] Сотсков Ю. Н., Струсевич В. А., Танаев В. С. Математические модели и методы календарного планирования. Учебное пособие // Минск: Ушверсггэцкае, 1994.

[8] Танаев В. С., Сотсков Ю. Н., Струсевич В. А. Теория расписаний. Многостадийные системы // М.: Наука, 1989.

[9] Bergström V. Ein neuer Beweis eines Satzes von E.Steinitz // Abhendlungen aus dem Mathematischen Seminar der Hamburgischen Universität. 1931. V. 8. P. 148-152.

[10] Chen B., Potts C. N., and Woeginger G. J. A review of machine scheduling: complexity, algorithms and approximability // in: Handbook of Combinatorial Optimization. D.-Z. Du and P. M. Pardalos (Eds.). Kluwer Academic Publishers, 1998. P. 21-169.

[11] Hall L. A. Approximability of flow shop scheduling // in: Proceedings of the 36th IEEE Symposium on Foundations of Computer Science. 1995. P. 82-91.

[12] Jansen K., Solis-Oba R., and Sviridenko M. Makespan minimization in job shops: a polynomial time approximation scheme // in: Proceedings of the 31st Annual ACM Symp. on Theory of Computing. 1999. P. 394-399.

[13] Mas-Colell A. The theory of general economic equilibrium. A differentiable approach // Cambridge: University-press, 1985.

[14] Shmoys D. B., Stein C., and Wein J. Improved Approximation Algorithms for Shop Scheduling Problems // SIAM J. on Computing. 1994. V. 23. P. 617 632.

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

[15] Воегингер Г. Д., Севастьянов С. В. Линейная аппроксима-ционная схема для многопроцессороной задачи open shop // Дискретный анализ и исследование операций. Сер. 1. 1999. Т. 6, N 2. С. 3-22._

[16] Кононов А. В., Севастьянов С. В., Черных И. Д. Полиномиальная разрешимость задачи open shop при условиях доминирования // Второй Сибирский Конгресс по Прикладной и Индустриальной Математике (ИНПРИМ-96). Новосибирск, 25-30 июня 1996. Материалы конференции. Новосибирск: Изд-во Ин-та математики, 1996. С. 137-138.

[17] Неумытов Ю. Д., Севастьянов С. В. Приближенный алгоритм с точной оценкой для трехмашинной задачи встречных маршрутов // Управляемые системы. Новосибирск: Изд-во Ин-та математики, 1993. С. 53-65. (Тр./ АН СССР. Сиб. отд-ние. Ин-т математики. Вып. 31.)

[18] Севастьянов С. В. Алгоритмы с оценками для задач Джонсона и Акерса-Фридмана в случае трех станков // Управляемые системы. Новосибирск: Изд-во Ин-та математики, 1982. С. 51-57. (Тр./ АН СССР. Сиб. отд-ние. Ин-т математики. Вып. 22.)

[19] Севастьянов С. В. Эффективное построение расписаний, близких к оптимальным, для случаев произвольных и альтернативных маршрутов деталей // Докл. АН СССР. 1984. Т. 276, N 1. С. 46-48.

[20] Севастьянов С. В. Алгоритм с оценкой для задачи с маршрутами деталей произвольного вида и альтернативными исполнителями // Кибернетика. 1986, N 6. С. 74-79.

[21] Севастьянов С. В. Геометрия в теории расписаний // Модели и методы оптимизации. Новосибирск: Наука, Сиб.

Отдел., 1988. С. 226-261. (Тр./ АН СССР. Сиб. отд-ние. Ин-т математики. Т. 10.)

[22] Севастьянов С. В. Теорема о компактном суммировании векторов в двумерном пространстве // Методы дискретного анализа. Новосибирск: Изд-во Ин-та математики, 1988. С. 61-65. (Тр./ АН СССР. Сиб. отд-ние. Ин-т математики. Вып. 47.)

[23] Севастьянов С. В. О компактном суммировании векторов // Дискретная математика. 1991. Т. 3, N 3. С. 66-72.

[24] Севастьянов С. В. Полиномиально разрешимый случай задачи open-shop с произвольным числом машин // Кибернетика и системный анализ. 1992. N 6. С. 135-154.

[25] Севастьянов С. В. Построение приближенного расписания для системы поточного типа // Управляемые системы. Новосибирск: Изд-во Ин-та математики, 1993. С. 6671. (Тр./ АН СССР. Сиб. отд-ние. Ин-г математики. Вып. 31.)

[26] Севастьянов С. В. Эффективное построение расписаний в системах открытого типа // Сибирский журнал исследования операций. 1994. Т. 1, N 1. С. 20-42.

[27] Севастьянов С. В. Нестрогое суммирование векторов в задачах теории расписаний // Сибирский журнал исследования операций. 1994. Т. 1, N 2. С. 67-99.

[28] Севастьянов С. В. Нестрогое суммирование векторов на плоскости и его применение в задачах теории расписаний // Дискретный анализ и исследование операций. 1995. Т. 2, N 2. С. 69-100.

[29] Севастьянов С. В., Черных И. Д. Достаточное условие эффективной разрешимости задачи open shop // Дискрет-

ный анализ и исследование операций. 1996. Т. 3, N 1. С. 57-74.

[30] Севастьянов С. В. Нестрогое суммирование векторов в многооперационных задачах теории расписаний // Второй сибирский конгресс по прикладной и индустриаль-

------ной математике (ИНПРИМ-96),Новосибирск, 25-30 июня 1996. Материалы конференции. Новосибирск: Изд-во Ин-та математики, 1996. С. 142.

[31] Севастьянов С. В. Применение геометрических методов в многостадийных задачах теории расписаний // Тез.докл. на 11 Международной конф. по проблемам теоретической кибернетики. Ульяновск, 10-14 июня 1996. Ульяновск: Изд-во СВНЦ, 1996. С. 180-181.

[32] Севастьянов С. В. Геометрические методы в теории расписаний // Международная Сибирская конференция по исследованию операций (SCOR-98). Новосибирск, 22-27 июня 1998. Материалы конференции. Новосибирск: Изд-во Ин-та математики, 1998. С. 35-38.

[33] Avgustinovich S. V. and Sevast'janov S. V. Vector Summation within Minimal Angle // Computational Geometry: Theory and Appl. 1993. V. 2. P. 235-239.

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

[35] Potts C. N., Sevast'janov S. V., Strusevich V. A., Van Wassenhove L. N., and Zvaneveld С. M. The two-stage assembly scheduling problem: complexity and approximation // Report 9256/A. Rotterdam, The Netherlands: Erasmus University Rotterdam, 1992.

[36] Potts C. N., Sevast'janov S. V., Strusevich V. A., Van Wassenhove L. N., and Zvaneveld С. M. The two-stage

assembly scheduling problem: complexity and approximation // Operations Research. 1995. V. 43, N. 2. P. 346-355.

[37] Sevastianov S. V. Efficient construction of schedules close to optimal for the class of arbitrary and alternative routes of parts // Soviet Math. Dokl. 1984. V. 29. P. 447-450. (translated from Russian)

[38] Sevast'janov S. V. An algorithm with an estimate for a problem with routings of parts of arbitrary shape and alternative executors // Cybernetics. 1986. V. 22. P. 773781. (translated from Russian)

[39] Sevast'janov S. V. On a geometric method in scheduling theory // in: 14th Int. symp. on math, programming (abstracts). Amsterdam, The Netherlands, August 5-9,1991.

[40] Sevast'janov S. V. Polynomially solvable case of the open-shop problem with arbitrary number of machines // Cybernet. Systems Anal. 1992. V. 28, N. 6. P. 918-933 (1993). (translated from Russian)

[41] Sevast'janov S. V. New polynomially solvable cases of the open shop problem // in: Operations Research 1994. Intern. Conf. on Oper. Res., Aug. 30 - Sept. 2, 1994. Program and Abstracts. Berlin: TU Berlin, 1994. P. 111.

[42] Sevast'janov S. V. Nonstrict vector summation in job shop scheduling //in: Operations Research 1994. Intern. Conf. on Oper. Res., Aug. 30 - Sept. 2, 1994. Program and Abstracts. Berlin: TU Berlin, 1994. P. 112.

[43] Sevast'janov S. V. On some geometric methods in scheduling theory: a survey // Discrete Appl. Math. 1994. V. 55. P. 59 82.

[44] Sevast'janov S. V. Vector summation in Banach space and polynomial algorithms for flow shops and open shops // Math.Oper.Res. 1995. V. 20, N. 1. 90-103.

[45] Sevastianov S. V. Nonstrict vector summation in multioperation scheduling // Memorandum COSOR 95-37.

-Eindhoven -Uni versi ty- ofTechnology ,-1995.-

[46] Sevast'yanov S. V. Efficient scheduling in open shops // in: A. D. Korshunov (ed.), Discrete analysis and oper. res. Dordrecht: Kluwer, 1996. P. 235-255.

[47] Sevast'yanov S. V. Nonstrict vector summation in scheduling problems // in: A. D. Korshunov (ed.), Discrete analysis and oper. res. Dordrecht: Kluwer, 1996. P. 257-287.

[48] Sevast'yanov S. V. and Woeginger G. J. Makespan minimization in open shops: a polynomial time approximation // SFB-Report 68, Mai 1996. TU Graz, Austria.

[49] Sevast'yanov S. V. Nonstrict vector summation in the plane and its application to scheduling problems // in: A. D. Korshunov (ed.), Operations research and discrete analysis. Dordrecht: Kluwer, 1997. P. 241-272.

[50] Sevastianov S. V. Seven problems: so different yet close // in: R. Burkard and G. Woeginger (Eds.). Algorithms — ESA'97, 5th Annual European Symposium, Graz, Austria, September 1997. Proceedings. Springer-Verlag, 1997. P. 443458. (Lecture Notes in Comp.Sci. V. 1284.)

[51] Sevast'janov S. V. and Banaszczyk W. To the Steinitz lemma in coordinate form // Discrete Math. 1997. V. 169. P. 145152.

[52] Sevastianov Sergey V. and Woeginger Gerhard J. Makespan minimization in open shops: A polynomial

time approximation scheme // Math. Programming. 1998. V. 82. P. 191-198.

[53] Sevastianov Sergey V. Compact vector summation: how it works in different fields of discrete mathematics // in: Y. Rabani, D. Shmoys, G. Woeginger (Eds.). Combinatorial Approximation Algorithms, Dagstuhl-Seminar-Report. V. 187. 1998; 18.08.-22.08.97 (9734). P. 14-15.

[54] Sevastianov Sergey. Nonstrict vector summation in multioperation scheduling // Annals of Oper.Res. 1998. V. 83. P. 179-211.

[55] Sevastianov S. V. Geometrical heuristics for multiprocessor flowshop scheduling with uniform machines at each stage // in: Symposium on operations research 1999, Magdeburg, September 1-3, 1999. Book of Abstracts. P. 101-102.

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

Неформальное введение

1 "Откуда есть пошла ." Исторический экскурс.

2 О названии.

3 Область исследования.

4 Объект и цели исследования.

5 Методы исследования.

Вполне формальное введение

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

7 Обзор результатов диссертации

8 Основные понятия и определения.

I Задачи суммирования векторов

9 Определения и обозначения

10 Алгоритмы нахождения подсемейств векторов, ребер и операций.

11 Компактное суммирование векторов

12 Оценки и свойства функций Штейница.

13 Нестрогое суммирование векторов на плоскости.

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

15 Суммирование векторов в специальных областях пространства.

А. Общее направление исследований

Диссертация посвящена разработке эффективных методов решения NP-трудных дискретных оптимизационных задач. Главной "мишенью" при этом являются многостадийные системы теории расписаний. При анализе возникающих здесь задач обнаруживается их тесная связь с другими дискретными задачами, не относящимися к области теории расписаний. Установление таких связей позволяет, во-первых, лучше понять природу исследуемых задач, и во-вторых, способствует разработке новых эффективных методов их решения. Так например, в диссертации установлена связь задач на построение кратчайших расписаний в многостадийных системах — с семейством геометрических задач о суммировании векторов. Разработка эффективных алгоритмов нахождения оптимальных (или близких к ним) порядков суммирования векторов, укладывающих траекторию суммирования векторов в некоторую экстремальную область или семейство областей m-мерного пространства, позволяет строить эффективные алгоритмы приближенного решения задач теории расписаний с гарантированными оценками точности. В свою очередь, анализ геометрических задач о суммировании векторов обнаруживает их тесную взаимосвязь с задачами, лежащими в других областях дискретной математики.

Другим направлением исследования в диссертации является отыскание широких полиномиально разрешимых классов примеров NP-трудных задач. Наиболее "удобной" в этом отношении объектом оказалась задача open shop, исследованию которой посвящена самая большая глава из третьей части диссертации. Здесь автором введено понятие нормального примера, т.е. примера, длина оптимального расписания которого совпадает с максимальной машинной нагрузкой. Главным результатом этих исследований является вывод о том, что "нормальность" — это чрезвычайно распространенное явление среди примеров задачи open shop. Кроме того, выделяются широкие эффективно нормальные классы примеров, т.е. классы нормальных примеров, допускающие их эффективное точное решение. Представлено три разных подхода к построению таких классов: на основе метода компактного суммирования векторов, с использованием

6 Общая характеристика работы 27 модифицированного метода Фиалы, и на основе анализа разностей нагрузок машин. Показано, что три указанных метода покрывают значительную часть множества всех примеров задачи open shop. (Более того, при фиксированном числе машин и произвольном числе работ множество "ненормальных" примеров есть множество меры нуль.)

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

• Разработан геометрический метод эффективного приближенного решения ряда NP-трудных задач теории расписаний (типа задачи job shop) с критерием минимум длины расписания [42]-[45],[50], [52]-[53],[56]-[57],[103]- [109],[113]-[115],[117],

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

• Доказана теорема 11.5 [48], устанавливающая возможность суммирования произвольного О-семейства векторов в различных выпуклых областях пространства Rm, зависящих от произвольного вектора а € Rm. Из теоремы вытекает следствие, согласно которому для любой нормы s с центрально симметричным (не обязательно относительно начала координат) единичным шаром всякое s-семейство векторов может быть просуммировано в шаре радиуса m—1 + l/m. Этот результат улучшает как известные ранее оценки минимального радиуса суммирования в задаче о компактном суммировании векторов (в частности, экспоненциальные от т оценки Бергстрёма [77] и Кадеца [20]), так и результаты самого автора диссертации, полученные им ранее. (Оценка радиуса т, справедливая для любых, в том числе несимметричных норм [35]. Ранее было показано [16], что оценка т неулучшае-ма для несимметричных норм, и было не известно, можно ли ее улучшить для произвольного ш в случае симметричных норм.) Примечательно, что улучшение гарантированных оценок радиуса суммирования достигнуто без потери эффективности алгоритма.

• Исследованы свойства и получены верхние и нижние оценки функций Штейница (принимающих значения минимального радиуса суммирования векторов в пространстве Rm с той или иной нормой s) [45].

• Для задач теории расписаний типа задачи о сборочной линии и задачи job shop установлено существование интервала локализации оптимумов [104],[44],[111],

127]. Знание этих интервалов позволяет с достаточной точностью (не зависящей от таких параметров исходной задачи как число работ) эффективно локализовать значение оптимума любого примера рассматриваемой NP-трудной задачи.

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

• Определено понятие нестрогого суммирования векторов в семействе областей m-мерного пространства. Для произвольной нормы s в Е2 получены достаточные условия, гарантирующие возможность нестрогого суммирования любого s-ce-мейства векторов в исходной выпуклой области пространства (теоремы 13.8 и 13.21 [53]). Разработаны эффективные алгоритмы нахождения такого суммирования при выполнении достаточных условий. С использованием нестрогого суммирования векторов найдены неулучшаемые интервалы локализации оптимумов для ряда задач нахождения кратчайшего расписания на трех машинах.

• На основе понятия нормальности [95] найдены широкие полиномиально разрешимые классы примеров задачи open shop. Представлено три разных подхода к построению таких классов: на основе метода компактного суммирования векторов [114], с использованием усовершенствованного метода Фиалы [49] и на основе анализа разностей нагрузок машин [51],[54], [95]. Из полученных результатов следует, что нормальность является типичным явлением на множестве примеров задачи open shop.

• Для многопроцессорной задачи open shop с фиксированным числом машин совместно с Г. Вёгингером построена полиномиальная аппроксимационная схема (PTAS) линейной трудоемкости [9]. Таким образом, найден ответ на давно стоявший открытый вопрос о границе приближаемости задачи open shop. В то же время, для любого р < 5/4 доказана невозможность (при условии P^NP) построения р-приближающего полиномиального алгоритма решения задачи open shop в случае, когда число машин является переменной45. Тем самым, в анализе сложности этой задачи установлен "водораздел" между случаями, допускающими построение полиномиальной аппроксимационной схемы (когда т — любое фиксированное число), и случаями, когда такой схемы не существует (га — переменная).

• Найдена тесная связь между комбинаторными задачами из различных областей дискретной математики, позволяющая использовать результаты анализа одних задач для отыскания интересных свойств решений других задач [45], [121]. Так например, нетривиальные нижние оценки определенных нами функций Штейни-ца для норм 1Р, р > 2, могут быть получены с использованием матриц Адама-ра, а для произвольной нормы s — с помощью функции Дворецкого. Установлена взаимосвязь между задачами: эквидистанции на булевом кубе, балансировки, равномерного разбиения, нахождения подмножества векторов с заданной суммой, компактного суммирования векторов, объемно календарного планирования, и др.

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

Диссертант является автором 83 научных работ. По теме диссертации опубликовано 73 работы, в том числе:

45 Результат получен автором диссертации независимо и опубликован в совместной статье с шестью соавторами [136].

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

29

21 — в международных журналах, 14 — в центральных изданиях, 12 — в сборниках трудов Института математики, 6 — в препринтах европейских университетов, 19 — в тезисах конференций.

Результаты диссертанта по теме диссертации опубликованы в работах: [9], [13]—[16], [22]—[28], [30]—[59], [66]-[69], [89], [94]-[95], [103]-[104], [107]-[129], [133], [136].

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

• монография Танаева, Сотскова и Струсевича по Многостадийным системам теории расписаний [61];

• обзор Чена, Поттса, Вёгингера по теории расписаний [81];

• учебное пособие Сотскова, Струсевича и Танаева по Математическим моделям и методам календарного планирования [60];

• учебное пособие Гимади и Глебова по Дискретным экстремальным задачам принятия решений [10];

• учебное пособие В.М. Кадеца и М.И. Кадеца по Перестановкам рядов в пространствах Банаха [21];

• монография Мас-Колела по Теории общего экономического равновесия [99];

• спецкурс Бенгта Нилссона по теории расписаний в университете г. Лунда (Швеция) [100].

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

• Конференция по теоретической кибернетике, Кишинев (1982);

• 2-й Всесоюзный семинар по дискретной математике и ее приложениям, Москва (1987);

• Семинар профессора Катоны по Комбинаторике в Математическом институте Венгерской академии наук (Будапешт, Венгрия, 1989);

• Конференция по теоретической кибернетике (Тбилиси, 1990);

• 14-й Международный симпозиум по Математическому программированию (Амстердам, Нидерланды, 1991);

46 Приводятся выступления диссертанта, начиная с 1982 года, — после защиты им кандидатской диссертации.

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

• Международная конференция по Исследованию операций (Берлин, Германия, 1994)

• Второй рабочий семинар по Моделям и Алгоритмам в Планировании и Теории Расписаний (Вернигероде, Германия, 1995);

• Семинар профессора Ленстры по дискретной математике в Техническом Университете Эй^совена (Эйндховен, Нидерланды, 1995);

• Семинар профессоров Дойбера и Аалсведе по дискретной математике в Техническом Университете Билефельда (Билефельд, Германия, 1996);

• 11-я Международная конференция по проблемам теоретической кибернетики (Ульяновск, 1996);

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

• Третий рабочий семинар по Моделям и Алгоритмам в Планировании и Теории Расписаний (Кембридж, Англия, 1997);

• Дагштуль-семинар по Комбинаторным Приближенным Алгоритмам (Шлее Даг-штуль, Германия, 1997);

• Пятый Европейский Симпозиум по Алгоритмам — ЕЭА'97 (Грац, Австрия, 1997);

• Семинар профессора Брэзел по дискретной математике в Техническом Университете Магдебурга (Магдебург, Германия, 1998);

• 13-й рабочий семинар по Дискретной оптимизации (Бург, Германия, 1998);

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

• Четвертый рабочий семинар по Моделям и Алгоритмам в Планировании и Теории Расписаний (Ренесса, Нидерланды, 1999);

• 14-й рабочий семинар по Дискретной оптимизации (Хольцхау, Германия, 2000);

• Семинар профессора Брэзел по дискретной математике в Техническом Университете Магдебурга (Магдебург, Германия, 2000);

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

• Международный рабочий семинар по методам дискретной оптимизации в теории расписаний и компьютерном дизайне (Минск, 2000);

• Семинар профессора Танаева по теории расписаний в Институте Технической Кибернетики (Минск, 2000).

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

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

Диссертация состоит из введения (неформального и вполне формального) и трех частей. Третья часть состоит из четырех глав, а главы и части в свою очередь состоят из разделов.

1. Адельсон-Вельский Г.М., Диниц Е.А., Карзанов A.B. Потоковые алгоритмы. М.: Наука, 1975.

2. Аксенов В.А. Полиномиальный алгоритм приближенного решения одной задачи теории расписаний // Управляемые системы. Новосибирск: Изд-во Ин-та математики, 1988. С. 8-11. (Тр./ АН СССР. Сиб. отд-ние. Ин-т математики. Вып. 28.)

3. Бабушкин А.И., Башта A.JI., Белов И.С. Построение календарного плана для много маршрутной задачи трех станков // Автомат, и Телемех. 1976. Т. 7 С. 154-158.

4. Бабушкин А.И., Башта A.JL, Белов И.С. Построение календарного плана для задачи встречных маршрутов // Кибернетика. 1977. N 4. С. 130-135.

5. Бабушкин А.И., Башта A.JL, Белов И.С., Душин Б.И. Минимизация цикла работы поточной линии // Автомат, и Телемех. 1975. Т. 6. С. 161-167.

6. Белов И.С., Столин Я.Н. Алгоритм в одномаршрутной задаче календарного планирования. В кн.: Математическая экономика и функциональный анализ. М.: Наука, 1974. С. 248-257.

7. Берж К. Теория графов и ее применения. М.: Издательство иностранной литературы, 1962.

8. Боровков A.A. К вероятностной постановке двух экономических задач // Докл. АН СССР, 1962, Т. 146, N 5, С. 983-986.

9. Воегингер Г.Д., Севастьянов C.B. Линейная аппроксимационная схема для многопроцессорной задачи open shop // Дискретный анализ и исследование операций. Сер. 1. 1999. Т. 6, N 2. С. 3-22.

10. Гимади Э.Х., Глебов Н.И. Дискретные экстремальные задачи принятия решений. Учебное пособие // Новосибирск: НГУ, 1991.

11. Гимади Э.Х., Глебов Н.И., Перепелица В.А. Исследования по теории расписаний // Управляемые системы. Новосибирск: Изд-во Ин-та математики, 1974. С. 3-10. (Тр./ АН СССР. Сиб. отд-ние. Ин-т математики. Вып. 12.)

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

13. Гимади Э.Х., Залюбовский В.В., Севастьянов В.В. Полиномиальная разрешимость задач календарного планирования со складируемыми ресурсами и директивными сроками // Дискретный анализ и исследование операций. Сер. 2. 2000. Т. 7, N 1. С. 9-34.

14. Гимади Э.Х., Перепелица В.А. Статистически эффективный алгоритм выделения гамильтонова контура (цикла) // Методы дискретного анализа. Новосибирск: Изд-во Ин-та математики, 1973. С. 15-28. (Тр./ АН СССР. Сиб. отд-ние. Ин-т математики. Вып. 22.)

15. Гимади Э.Х., Перепелица В.А. Асимптотически точный подход к решению задачи коммивояжера // Управляемые системы. Новосибирск: Изд-во Ин-та математики, 1974. С. 35-45. (Тр./ АН СССР. Сиб. отд-ние. Ин-т математики. Вып. 12.)

16. Гринберг B.C., Севастьянов C.B. О величине константы Штейница // Функциональный анализ и его приложения. 1980. Т. 14. С. 56-57.

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

18. Душин Б.И. Алгоритм для 2-маршрутной задачи Джонсона // Кибернетика.1988. N 3. С. 53-58.

19. Душин Б.И. Алгоритм для р-маршрутной задачи Джонсона // Кибернетика.1989. N 2. С. 119-122.

20. Кадец М.И. Об одном свойстве векторных ломаных в n-мерном пространстве // Успехи мат. наук. 1953. Т. 8. С. 139-143.

21. Кадец В.М., Кадец М.И. Перестановки рядов в пространствах Банаха // Тарту: Тартуский государственный университет, 1988.

22. Каширских К.Н., Поттс К.Н., Севастьянов C.B. Улучшенный алгоритм решения двухмашинной задачи flow shop с неодновременным поступлением работ // Дискретный анализ и исследование операций. 1997. Т. 4, N 1. С. 13-32.

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

24. Неумытов Ю.Д., Севастьянов C.B. Приближенный алгоритм с точной оценкой для трехмашинной задачи встречных маршрутов // Управляемые системы. Новосибирск: Изд-во Ин-та математики, 1993. С. 53-65. (Тр./ АН. Сиб. отд-ние. Ин-т математики. Вып. 31.)

25. РОКАФЕЛЛАР Р. Выпуклый анализ. М.: Мир, 1973.

26. Севастьянов C.B. Об асимптотическом подходе к некоторым задачам теории расписаний // III Всесоюз. конф. по проблемам теор. кибернетики. Тез. докл. Новосибирск, 1974. С. 67-69.

27. Севастьянов C.B. Об асимптотическом подходе к некоторым задачам теории расписаний // Управляемые системы. Новосибирск: Изд-во Ин-та математики, 1975. С. 40-51. (Тр./ АН СССР. Сиб. отд-ние. Ин-т математики. Вып. 14.)

28. Севастьянов C.B. О приближенном решении некоторых задач теории расписаний // Методы дискретного анализа. Новосибирск: Изд-во Ин-та математики, 1978. С. 66-75. (Тр./ АН СССР. Сиб. отд-ние. Ин-т математики. Вып. 32.)

29. Севастьянов C.B. К задаче компактного суммирования векторов // Методы дискретного анализа. Новосибирск: Изд-во Ин-та математики, 1979. С. 77-89. (Тр./ АН СССР. Сиб. отд-ние. Ин-т математики. Вып. 33.)

30. Севастьянов C.B. О приближенном решении задачи календарного распределения // Управляемые системы. Новосибирск: Изд-во Ин-та математики, 1980. С. 49-63. (Тр./ АН СССР. Сиб. отд-ние. Ин-т математики. Вып. 20.)

31. Севастьянов C.B. Приближенные алгоритмы в задачах Джонсона и суммирования векторов // Управляемые системы. Новосибирск: Изд-во Ин-та математики, 1980. С. 64-73. (Тр./ АН СССР. Сиб. отд-ние. Ин-т математики. Вып. 20.)

32. Севастьянов C.B. О связи задачи календарного распределения с одной задачей на единичном кубе // Методы дискретного анализа. Новосибирск: Изд-во Ин-та математики, 1980. С. 93-103. (Тр./ АН СССР. Сиб. отд-ние. Ин-т математики. Вып. 35.)

33. Севастьянов C.B. О задаче календарного распределения // V Всесоюз. конф. по проблемам теор. кибернетики. Тез. докл. Новосибирск, 1980. С. 92-93.

34. Севастьянов C.B. О приближенном решении задачи Джонсона // V Всесоюз. конф. по проблемам теор. кибернетики. Тез. докл. Новосибирск, 1980. С. 93-95.Литература277

35. Севастьянов С.В. Оценки и свойства функций Штейница // Методы дискретного анализа. Новосибирск: Изд-во Ин-та математики, 1981. С. 59-73. (Тр./ АН СССР. Сиб. отд-ние. Ин-т математики. Вып. 36.)

36. Севастьянов С.В. Некоторые обобщения задачи Джонсона // Управляемые системы. Новосибирск: Изд-во Ин-та математики, 1981. С. 45-61. (Тр./ АН СССР. Сиб. отд-ние. Ин-т математики. Вып. 21.)

37. Севастьянов С.В. Алгоритмы с оценками для задач теории расписаний. Авто-реф. дис. на соиск. учен. степ. канд. физ.-мат. наук. (01.01.09). Новосибирск, 1981.

38. Севастьянов С.В. Алгоритмы с оценками для задач Джонсона и Акерса-Фридмана в случае трех станков // Управляемые системы. Новосибирск: Изд-во Ин-та математики, 1982. С. 51-57. (Тр./ АН СССР. Сиб. отд-ние. Ин-т математики. Вып. 22.)

39. Севастьянов С.В. Эффективное построение расписаний, близких к оптимальным, для случаев произвольных и альтернативных маршрутов деталей // Докл. АН СССР. 1984. Т. 276, N 1. С. 46-48.

40. Севастьянов С.В. Алгоритм с оценкой для задачи с маршрутами деталей произвольного вида и альтернативными исполнителями // Кибернетика. 1986, N 6. С. 74-79.

41. Севастьянов С.В. Геометрия в теории расписаний // Модели и методы оптимизации. Новосибирск: Наука, Сиб. Отдел., 1988. С. 226-261. (Тр./ АН СССР. Сиб. отд-ние. Ин-т математики. Т. 10.)

42. Севастьянов С.В. Теорема о компактном суммировании векторов в двумерном пространстве // Методы дискретного анализа. Новосибирск: Изд-во Ин-та математики, 1988. С. 61-65. (Тр./ АН СССР. Сиб. отд-ние. Ин-т математики. Вып. 47.)

43. Севастьянов С.В. О компактном суммировании векторов // Дискретная математика. 1991. Т. 3, N 3. С. 66-72.

44. Севастьянов С.В. Полиномиально разрешимый случай задачи open-shop с произвольным числом машин // Кибернетика и системный анализ. 1992. N 6. С. 135-154.

45. Севастьянов С.В. Построение приближенного расписания для системы поточного типа // Управляемые системы. Новосибирск: Изд-во Ин-та математики, 1993. С. 66-71. (Тр./ АН СССР. Сиб. отд-ние. Ин-т математики. Вып. 31.)

46. Севастьянов С.В. Эффективное построение расписаний в системах открытого типа // Сибирский журнал исследования операций. 1994. Т. 1, N 1. С. 20-42.

47. Севастьянов С.В. Нестрогое суммирование векторов в задачах теории расписаний // Сибирский журнал исследования операций. 1994. Т. 1, N 2. С. 67-99.Литература 278

48. Севастьянов C.B. Нестрогое суммирование векторов на плоскости и его применение в задачах теории расписаний // Дискретный анализ и исследование операций. 1995. Т. 2, N 2. С. 69-100.

49. Севастьянов C.B., Черных И.Д. Достаточное условие эффективной разрешимости задачи open shop // Дискретный анализ и исследование операций. 1996. Т. 3, N 1. С. 57-74.

50. Севастьянов C.B. Применение геометрических методов в многостадийных задачах теории расписаний // Тез.докл. на 11 Международной конф. по проблемам теоретической кибернетики. Ульяновск, 10-14 июня 1996. Ульяновск: Изд-во СВ-НЦ, 1996. С. 180-181.

51. Севастьянов C.B. Геометрические методы в теории расписаний // Международная Сибирская конференция по исследованию операций (SCOR-98). Новосибирск, 22-27 июня 1998. Материалы конференции. Новосибирск: Изд-во Ин-та математики, 1998. С. 35-38.

52. Севастьянов C.B. Многопараметрический анализ сложности дискретных задач // Дискретный анализ и исследование операций (DAOR'2000). Материалы конференции. Новосибирск, 26 июня 1 июля 2000. С. 61-62.

53. Сотсков Ю.Н., Струсевич В.А., Танаев B.C. Математические модели и методы календарного планирования. Учебное пособие // Минск: Ушвератэцкае, 1994.

54. Танаев B.C., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы // М.: Наука, 1989.

55. Харари Ф. Теория графов, М.: Мир, 1973.

56. Approximation Algorithms for NP-Hard Problems, Ed. by D.S. Hochbaum, PWS, 1997.

57. Akers, S.B. and Friedman, J. A non-numerical approach to production scheduling problems // Oper. Res. 1955. V. 3. P. 429-442.

58. Alon, N., Spencer, J., and ErdöS, P. The probabilistic method. A Willey-Interscience Publication, 1992.

59. Alon, N., Csirik, J., Sevastianov, S.V., Vestjens, A.P.A., and Woeginger, G.J. On-line and Off-line Approximation Algorithms for Vector Covering Problems // SFB-Report 78, July 1996. TU Graz, Austria.Литература 279

60. Avgustinovich, S.V. and Sevast'janov, S.V. Vector Summation within Minimal Angle // Computational Geometry: Theory and Appl. 1993. V. 2. P. 235-239.

61. Banaszczyk, W. The Steinitz Constant of the Plane // J. Reine und Angew. Math. 1987. V. 373. P. 218-220.

62. Banaszczyk, W. A note on the Steinitz Constant of the Euclidean Plane // C. R. Math. Rep. Acad. Sei. Canada. 1990. V. 12, N. 4. P. 97-102.

63. Banaszczyk, W. The Steinitz Lemma on Rearrangement of Series for Nuclear Spaces // J. Reine und Angew. Math. 1990. V. 403. P. 187-200.

64. Beck, J. and Fiala, T. "Integer-making" theorems // Discrete Appl. Math. 1981. V. 3. P. 1-8.

65. Bergström, V. Ein neuer Beweis eines Satzes von E.Steinitz // Abhendlungen aus dem Mathematischen Seminar der Hamburgischen Universität. 1931. V. 8. P. 148-152.

66. Brucker, P. Scheduling Algorithms. Berlin: Springer, 1995.

67. Carlier, J. and Pinson, E. An algorithm for solving the job-shop problem // Management Science. 1989. V. 35. P. 164-176.

68. Chen, B. Scheduling Multiprocessor Flow Shops // D.-Z. Du and J. Sun (Eds.). New Advances in Optimization and Approximation. Kluwer, 1994. P. 1-8.

69. Chen, B., Potts, C.N., and Woeginger, G.J. A review of machine scheduling: complexity, algorithms and approximability // Handbook of Combinatorial Optimization. D.-Z. Du and P. M. Pardalos (Eds.). Kluwer Academic Publishers, 1998. P. 21-169.

70. Chen, B. and Strusevich, V.A. Approximation algorithms for three-machine open shop scheduling // ORSA Journal on Computing. 1993. V. 5. P. 321-326.Литература 280

71. Dvoretzky, A. Problem // Proceedings of Symposia in Pure Mathematics. V. 7. Convexity. Providence, RI: Amer. Math. Soc., 1963.

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

73. Gabow, H.N. and Kariv, O. Algorithms for Edge Coloring Bipartite Graphs and Multigraphs // SIAM J.Comput. 1982. V. 11. P. 117-129.

74. Garey, M.R. and Johnson, D.S. Complexity Results for Multiprocessor Scheduling under Resource Constraints // SIAM J. Comput. 1975. V. 4. P. 397-411.

75. Gonzalez, T. and Sahni, S. Open Shop Scheduling to Minimize Finish Time // J. ACM. 1976. V. 23, N. 4. P. 665-679.

76. Graham, R.L. Bounds for certain multiprocessing anomalies // Bell System Technical Journal. 1966. V. 45. P. 1563-1581.

77. Grinberg, V.S. and Sevast'janov, S.V. Value of the Steinitz constant // Functional Anal. Appl. 1980. V. 14. P. 125-126.

78. Hall, L.A. Approximability of flow shop scheduling // in: Proceedings of the 36th IEEE Symposium on Foundations of Computer Science. 1995. P. 82-91.

79. Jansen, K., Solis-Oba, R., and Sviridenko, M. Makespan minimization in job shops: a polynomial time approximation scheme // Proceedings of the 31st Annual ACM Symp. on Theory of Computing. 1999. P. 394-399.

80. John, F. Extremum problems with inequalities as subsidiary conditions // Studies and essays, presented to R. Courant on his 60th Birthday. N.Y., 1948. P. 187-204.

81. Johnson, S.M. Optimal Two and Three-Stage Production Schedules with Set-up Times Included // Nav. Res. Log. Quart. 1954. V. 1, N. 1. P. 61-68.

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

83. Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., and Shmoys, D.B. Sequencing and scheduling: algorithms and complexity // Handbooks in Operations Research and Management Science V. 4. Amsterdam: North Holland, 1993. P. 445522.

84. Lee, C.-Y. and Vairaktarakis, G.L. Minimizing Makespan in Hybrid Flow-shops // Opns. Res. Letters. 1994. V. 16. P. 149-158.

85. Leichtweiss, K. Zwei Extremalprobleme der Minkowski-Geometrie // Math. Z. 1955. V. 62. P. 37-49.Литература 281

86. Mas-Colell, A. The theory of general economic equilibrium. A differentiable approach // Cambridge: University-press, 1985.100. nilsson, Bengt J. (private communication).

87. Olson, J. and Spencer, J. Balancing families of sets // J. Comb. Theory. (Ser. A). 1978. V. 25. P. 29-37.

88. Potts, C.N. Analysis of heuristics for two-machine flow-shop sequencing subject to release dates // Math. Орет. Res. 1985. V. 10, N. 4. P. 576-584.

89. Potts, C.N., Sevast'janov, S.V., Strusevich, V.A., Van Wassenhove, L.N., and Zvaneveld, C.M. The two-stage assembly scheduling problem: complexity and approximation // Report 9256/A. Rotterdam, The Netherlands: Erasmus University Rotterdam, 1992.

90. Shmoys, D.B., Stein, C., and Wein, J. Improved Approximation Algorithms for Shop Scheduling Problems // SIAM J. on Computing. 1994. V. 23. P. 617-632.

91. Sevastianov, S.V. Efficient construction of schedules close to optimal for the class of arbitrary and alternative routes of parts // Soviet Math. Dokl. 1984. V. 29. P. 447-450. (translated from Russian)

92. Sevast'janov S.V. An algorithm with an estimate for a problem with routings of parts of arbitrary shape and alternative executors // Cybernetics. 1986. V. 22. P. 773781. (translated from Russian)

93. Sevast'janov, S.V. On a geometric method in scheduling theory // 14th Int. symp. on math, programming (abstracts). Amsterdam, The Netherlands, August 5-9, 1991.

94. Sevast'janov, S.V. Polynomially solvable case of the open-shop problem with arbitrary number of machines // Cybernet. Systems Anal. 1992. V. 28, N. 6. P. 918-933 (1993). (translated from Russian)

95. Sevast'janov, S.V. New polynomially solvable cases of the open shop problem // in: Operations Research 1994. Intern. Conf. on Oper. Res., Aug. 30 Sept. 2, 1994. Program and Abstracts. Berlin: TU Berlin, 1994. P. 111.

96. Sevast'janov, S.V. Nonstrict vector summation in job shop scheduling // in: Operations Research 1994. Intern. Conf. on Oper. Res., Aug. 30 Sept. 2,1994. Program and Abstracts. Berlin: TU Berlin, 1994. P. 112.

97. Sevast'janov, S.V. On some geometric methods in scheduling theory: a survey // Discrete Appl. Math. 1994. V. 55. P. 59-82.

98. Sevast'janov, S.V. Vector summation in Banach space and polynomial algorithms for flow shops and open shops // Math.Oper.Res. 1995. V. 20, N. 1. 90-103.Литература 282

99. Sevastianov, S.V. Nonstrict vector summation in multi-operation scheduling // Memorandum COSOR 95-37. Eindhoven University of Technology, 1995.

100. Sevast'yanov, S.V. Efficient scheduling in open shops // A. D. Korshunov (ed.). Discrete analysis and oper. res. Dordrecht: Kluwer, 1996. P. 235-255.

101. Sevast 'yanov, S.V. Nonstrict vector summation in scheduling problems //A. D. Korshunov (ed.). Discrete analysis and oper. res. Dordrecht: Kluwer, 1996. P. 257287.

102. Sevast'yanov, S.V. and Woeginger, G.J. Makespan minimization in open shops: a polynomial time approximation // SFB-Report 68, Mai 1996. TU Graz, Austria.

103. Sevast'yanov, S.V. and Woeginger, G.J. Makespan Minimization in Preemptive Two Machine Job Shops // SFB-Report 81, July 1996. TU Graz, Austria.

104. Sevast'yanov, S.V. Nonstrict vector summation in the plane and its application to scheduling problems // A. D. Korshunov (ed.), Operations research and discrete analysis. Dordrecht: Kluwer, 1997. P. 241-272.

105. Sevast'janov, S.V. and Banaszczyk, W. To the Steinitz lemma in coordinate form // Discrete Math. 1997. V. 169. P. 145-152.

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

107. Sevastianov, S.V. and Woeginger, G.J. Makespan minimization in preemptive two machine job shops // Computing. 1998. V. 60, N. 1. P. 73-79.

108. Sevastianov, S. Nonstrict vector summation in multi-operation scheduling // Annals of Oper.Res. 1998. V. 83. P. 179-211.

109. Sevastianov, S.V. Geometrical heuristics for multiprocessor flowshop scheduling with uniform machines at each stage // Symposium on operations research 1999, Magdeburg, September 1-3, 1999. Book of Abstracts. P. 10Ы02.Литература 283

110. Sevastianov, S.V. Multi-parameter complexity analysis of discrete problems // Proc. International Workshop Discrete Optimization Methods in Scheduling and Computer-Aided Design, Minsk, September 5-6, 2000. Minsk, 2000. P. 172-174.

111. Shmoys, D.B., Stein, C., and Wein, J. Improved Approximation Algorithms for Shop Scheduling Problems // Proceedings of the 2nd ACM-SIAM Symposium on Discrete Algorithms (SODA), 1991. P. 148-157.

112. Steinitz, E. Bedingt Konvergente Reihen und Convexe Systeme // J. Reine und Angew. Math. 1913. V. 143. P. 128-175.

113. Tarjan, R.E. Data structures and network algorithms. Philadelphia, PA: SIAM, 1983.

114. Tchernykh, I.D., Kashyrskikh, K.N., and Sevastianov, S.V. 4-parameter complexity analysis of the open shop problem // Дискретный анализ и исследование операций (DAOR'2000). Материалы конференции. Новосибирск, 26 июня 1 июля 2000. С. 175.

115. Wallis, W.D., а.о. Combinatorics: Room Squares, Sum-Free Sets, Hadamard Matrices // Lecture Notes in Math. 1972. V. 292.

116. Wallis, J.S. Williamson matrices of even order // Lecture Notes in Math. 1974. V. 403. P. 132-142.

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