Актуальные задачи теории расписаний: вычислительная сложность и приближенные алгоритмы тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

\л

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

АКТУАЛЬНЫЕ ЗАДАЧИ ТЕОРИИ РАСПИСАНИЙ: ВЫЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ И ПРИБЛИЖЕННЫЕ АЛГОРИТМЫ

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

АВТОРЕФЕРАТ 15ШШ5

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

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

005557355

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

Официальные оппоненты: Кузюрин Николай Николаевич

доктор физико-математических наук, профессор, Институт системного программирования РАН, зав. отделом

Хачай Михаил Юрьевич

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

Институт математики и механики

им. Н.Н Красовского УрО РАН, зав. отделом

Хамисов Олег Валерьевич

доктор физико-математических наук, профессор, Институт систем энергетики им. Л.А. Мелентьева СО РАН, зав. отделом

Ведущая организация: Федеральное государственное бюджетное

образовательное учреждение высшего профессионального образования «Омский государственный университет им. Ф.М. Достоевского»

Защита состоится 18 февраля 2015 г. в 16 час. 30 мин. на заседании диссертационного совета Д 003.015.01 при Федеральном государственном бюджетном учреждении науки Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук (ИМ СО РАН) по адресу: 630090 г. Новосибирск, пр. Ак. Коптюга, 4.

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

Автореферат разослан 12 января 2015 г.

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

Ю. В. Шамардин

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

Актуальность темы. Объектом исследования настоящей диссертации являются задачи теории расписаний. Это широкий круг, как правило, NP-тpyдныx задач комбинаторной оптимизации, имеющих обширные приложения в организации производства, в бизнесе, в оптимизации компьютерных вычислений, в индустрии сервиса и во многих других областях человеческой деятельности. Предметом исследования являются энергетические задачи теории расписаний, задачи с воспроизводимым ресурсом, задачи оптимизации параллельных вычислений с задержками передачи данных и цеховые задачи с маршрутизацией, для которых исследуются вопросы алгоритмической сложности и построения точных или приближенных алгоритмов.

Задачи теории расписаний и задачи календарного планирования связаны с распределением ограниченных ресурсов для выполнения множества работ и поиском расписания с наилучшим значением заданной целевой функции. Оба направления возникли в 50-х годах прошлого столетия [27, 28, 30, 31, 36] и обусловлены как ростом сложности комбинаторных задач по управлению производственными процессами, так и появлением первых быстродействующих вычислительных устройств, давших надежду решить эти задачи за приемлемое время. Хотя формально все задачи теории расписаний можно отнести к задачам календарного планирования, длительное время теория расписаний развивалась как отдельное направление дискретной оптимизации. В классических задачах теории расписаний фактически не рассматриваются ресурсы, отличные от ресурса "машина", а основной упор делается на различные технологии выполнения множества работ и на разнообразие целевых функций. К середине 80-х годов прошлого столетия были выделены основные модели классической теории расписаний и установлена комбинаторная сложность большинства задач, возникающих в рамках этих моделей. Не удивительно, что примерно в то же время были предприняты первые попытки расширить классические модели теории расписаний внедрением в них таких дополнительных ресурсов, как энергия, деньги, машинная память и многие другие [13, 15, 16]. Новое направление исследований получило название "задачи теории расписаний с ограничениями на ресурсы"

[14] и стало одним из наиболее популярных направлений в теории расписаний в последние два десятилетия.

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

В частности, одно из популярных направлений развития компьютерных вычислений — это параллельные вычисления. При этом основная сложность при проектировании параллельных программ состоит в том, чтобы обеспечить правильную последовательность взаимодействий между различными вычислительными процессами, а также координацию ресурсов, распределяемых между процессами. В 1987 году Рэйвард-Смит [33] предложил рассмотреть однородную коммуникационную модель выполнения множества заданий параллельной программы как задачу теории расписаний с коммуникационными задержками. Идея, предложенная Рэйвард-Смитом, оказалась очень плодотворной, и задачи с коммуникационными задержками интенсивно изучаются уже больше двух десятилетий. Результатам в данном направлении посвящены главы в монографиях [22] и [20] и несколько обзоров [21, 34], каждый из которых содержит большой список открытых проблем.

Другим важным достижением в развитии компьютерных технологий стала возможность современных многопроцессорных компьютеров, таких как Intel SpeedStep или AMD PowerNow, варьировать свою скорость. Высокие скорости вычислений приводят к более быстрому и качественному обслуживанию, но при этом и к большим затратам энергии. Поиск золотой середины между экономией энергии и сохранением качества обслуживания породил новый класс задач, в которых требуется найти энергетически эффективные расписания. Результаты, полученные в этой области, настолько интересны, а открытые проблемы настолько важны, что обзор, посвященный различным задачам минимизации энергии при построении расписаний, был опубликован в одном из самых престижных журналов по проблемам передачи информации " Communications of the ACM" [2].

Еще одним интересным современным направлением исследова-

ния является слияние задач теории расписаний с другими классическими задачами дискретной оптимизации в одну общую задачу. Это в некоторой степени относится к задачам теории расписаний с ограничениями на ресурсы, в которых к исходной постановке задачи в терминах теории расписаний добавляются ограничения, характерные для задач об упаковках и зада1! календарного планирования. Другим интересным примером являются цеховые задачи теории расписаний с маршрутизацией, которые обобщают цеховые задачи с широко известной метрической задачей коммивояжера. Удивительно, что постановки таких проблем независимо появились при рассмотрении задач, возникающих как на производстве [8, 9], так и в индустрии обслуживания [19, 38].

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

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

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

применяются и для практических задач.

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

• С точки зрения нахождения точных решений почти все ЫР-трудные задачи эквивалентны друг другу. Построение приближенных алгоритмов или доказательство невозможности их построения при условии несовпадения классов Р и № дает возможность сравнить между собой Г\тР-трудные задачи по тому, насколько хорошо они могут быть аппроксимированы.

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

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

Цель данной работы состоит в изучении комбинаторных свойств задач теории расписаний и установлении их вычислительной сложности. Работа посвящена построению точных полиномиальных алгоритмов для рассматриваемых задач или доказательству их КР-трудности и разработке для ХР-трудных задач приближенных алгоритмов с гарантированной оценкой точности.

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

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

Научная новизна. Все представленные в диссертации результаты являются новыми.

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

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

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

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

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

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

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

— Международный рабочий семинар по моделям и алгоритмам для задач планирования и теории расписаний (MAPSP): 2001 (Ас-суа, Франция), 2003 (Ассуа, Франция), 2005 (Сиена, Италия), 2009 (Ролдюк, Нидерланды), 2011 (Нимбурк, Чехия); 2013 (Понт-а-Мус-сон, Франция);

— Симпозиум по параллельным алгоритмам и архитектуре (SPAA): 2001 (Гераклион, Греция), 2003 (Сан Диего, США);

— Всероссийская конференция «Проблемы оптимизации и экономические приложения»: 2003, 2006, 2012 (Омск, Россия);

— Российская конференция «Дискретный анализ и исследование операций»: 2004, 2010 (Новосибирск, Россия);

— Международный рабочий семинар по календарному планированию и теории расписаний (PMS): 2004 (Нанси, Франция), 2010 (Тур, Франция), 2012 (Левен, Бельгия);

— Байкальская международная школа-семинар «Методы оптимизации и их приложения»: 2005, 2014 (Иркутск, Россия);

— Международный рабочий семинар по приближенным и онлайн алгоритмам (WAOA), 2009 (Копенгаген, Дания);

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

— Международная конференция по вычислительным методам и комбинаторике (COCOON) 2013 (Гуанчжоу, Китай);

— Международная конференция по основам технологии программного обеспечения и теоретической информатики (FSTTCS) 2013 (Гувахити, Индия).

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

— «Математические модели принятия решений», Институт математики им. С.Л. Соболева СО РАН, Новосибирск;

— «Дискретные экстремальные задачи», Институт математики им. С.Л. Соболева СО РАН, Новосибирск;

— семинар лаборатории информатики (LIP 6) университета Пьера и Марии Кюри, Объединенный университет Сорбонны, Париж, Франция;

— семинар факультета информационного менеджмента Национального университета Чиао-Тунг, Хсинчу, Тайвань.

— семинар школы бизнеса и экономики университета Маастрихта, Нидерланды.

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

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

Публикации. По теме диссертации автором опубликована 61 работа, в том числе 26 статей, все — в журналах и продолжающихся изданиях из списка ВАК или включенных в базы данных Scopus, Web of Science, ZBMath и 35 работ — в трудах российских и международных конференций.

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

1. Решен открытый вопрос о вычислительной сложности задачи построения кратчайшего расписания единичных работ на двух параллельных идентичных машинах при наличии воспроизводимого ресурса, поставленный Амиром и Капланом в 1988 году [5]. Доказано, что данная задача является ИР-трудной в сильном смысле. Также установлена ХР-трудность в сильном смысле следующих задач с воспроизводимым ресурсом:

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

- задача минимизации суммы моментов завершения работ на одной машине,

- задача минимизации взвешенной суммы моментов завершения единичных работ на одной машине.

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

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

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

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

5. Построены приближенные алгоритмы с гарантированными оценками точности для различных ХР-трудных вариантов цеховой задачи открытого типа с маршрутизацией машин. Все построенные алгоритмы имеют лучшие оценки точности среди известных алгоритмов одинаковой с ними трудоемкости.

6. Построен точный псевдо-полиномиальный алгоритм для двухмашинной цеховой задачи открытого типа с маршрутизацией для ХР-трудного случая, когда работы и машины расположены на двухвершинной сети. Как следствие, решен открытый вопрос о вычислительной сложности этой задачи.

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

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

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

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

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

Второй раздел посвящен описанию классификации задач теории расписаний, первоначально введенной в [23] и позднее развитой в многочисленных англоязычных монографиях [17, 18, 32]. Для обозначения каждой задачи используется а |/317-идентификатор, в котором в поле а вносится информация о типе ресурсов задачи, в том числе о конфигурации машин, в поле (3 описываются характеристики работ и в поле 7 — вид целевой функции. Данная классификация адаптируется к задачам, рассматриваемым в диссертации.

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

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

Вторая глава диссертации посвящена задачам теории расписаний с воспроизводимым ресурсом. Множество работ 3 — {•/],..., Jrl} должно быть выполнено на одной или нескольких машинах. Задан общий ресурс объема По. Перед началом выполнения работа Ji потребляет щ единиц ресурса и воспроизводит Д единиц ресурса сразу после своего завершения. Величина щ называется расходолг ресурса на работу ./¿, величина Д - доходом ресурса от работы Ж, и величина дг = /Зг — а, прибылью ресурса от работы •Л. Длительность работы ./,; равна щ. Прерывания в обслуживании работ запрещены. Требуется найти такое расписание а, в котором выполнены все работы, и в каждый момент времени Ь остаток общего ресурса неотрицателен.

Понятие воспроизводимого ресурса обобщает понятия как возобновимого, так и невозобновимого ресурсов. Действительно, по-

лагая в определении воспроизводимого ресурса сц = для всех работ, получаем возобновимый ресурс. А в случае, если для всех работ выполнено /Зг = 0, имеем невозобновимый ресурс. Более того, классическая задача об упаковке в контейнеры может быть сформулирована, как задача с возобновимым ресурсом и единичными длительностями работ. Таким образом, задача с воспроизводимым ресурсом и единичными длительностями работ является естественным обобщением этой известной задачи.

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

• задача с единичными длительностями всех работ и неположительной прибылью ресурса от каждой работы (задача \¥1,1\ VI = Мг < 0|Х>сг),

• задача с единичными длительностями всех работ и неотрицательной прибылью ресурса от каждой работы (задача IV1, "11

• задача с единичными весами всех работ и неположительной прибылью ресурса от каждой работы (задача < 0| ^ С*),

• задача с единичными весами всех работ и неотрицательной прибылью ресурса от каждой работы (задача 1|<5г > 0| ^ С¿).

Установлено, что все четыре подзадачи являются ХР-трудпыми в сильном смысле. Следующие две теоремы — основные результаты раздела 2.1.

Теорема 1 Задача \У1,1 — 1 ,дj < 0| и^С^ является ЛГР-трудной в сильном смысле.

Теорема 2 Задача \¥1Л\р^ = 1,53 > 0| ^ является МР-трудной в сильном смысле.

В конце раздела представлены 2-приближенные жадные алгоритмы для задач 1У1,1]р^ = 1,> 0| ^ и ТУ1,11<5^ < 0| ^ С^.

Второй и третий разделы посвящены задачам минимизации длины расписания множества работ на параллельных идентичных ма-

шинах. В задаче W1, Р\\Стах число параллельных машин не фиксировано и может быть различным для каждой индивидуальной задачи. В задаче Wl,Pm\\Cmax число параллельных машин фиксировано и равно т. В этом разделе также изучается задача W\\\Cmax, в которой отсутствует ресурс типа "машина", т.е. произвольное число работ может выполняться параллельно.

Во втором разделе исследуется комбинаторная сложность задачи на двух параллельных машинах с единичными длительностями работ. Легко показать, что задачи Wl\\Cmax, Wl,P\\Cmax и W1, Рт\\Стах при ш > 3 являются NP-трудными в сильном смысле, даже если все работы имеют единичную длительность. Действительно, все эти задачи являются обобщением различных NP-трудных вариантов задачи об упаковке в контейнеры. В [29] Кап-лан и Амир поставили вопрос о комбинаторной сложности задачи Wl, P2\pi = 11С max • В диссертации показано, что к этой задаче сводится классическая NP-полная в сильном смысле задача ПА-РОСОЧЕТАНИЕ С ОГРАНИЧЕНИЯМИ ПО ВЕСУ (задача МР-17 в списке NP-иолных задач в [1]), и доказана следующая

Теорема 7 Задача Wl,P2\pj = 1 ,Sj > 0|Стах является NP-трудной в сильном смысле.

Отметим, что задача остается NP-трудной, даже если назначение работ по машинам фиксировано.

В конце раздела рассматривается задача Wl\pj = 1|Стах, в которой длительности работ единичные и произвольное число работ может выполняться параллельно. Устанавливается, что для нее не существует асимптотического /э-приближенного алгоритма с р < | при условии несовпадения классов Р и NP. Этот результат подчеркивает, что с точки зрения аппроксимации задача Wl\pj = 1\Стах является более сложной, чем классическая задача об упаковке в контейнеры, обобщением которой она является.

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

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

Все результаты главы, кроме 0(log п)-приближенного алгоритма для задачи

Wl\\Crnax, получены в соавторстве с Б.М.-Т. Липом. Последний результат получен совместно с А. Григорьевым и М. Свириденко.

В третьей главе рассматривается задача построения энергетически эффективных расписаний. Множество работ J = {Jj,..., Jn} должно быть выполнено на одной или нескольких машинах. В однородной модели для каждой работы Jj задан ее объем Wj и интервал времени, в котором она должна быть выполнена [rj,dj). Длительность работы зависит от скорости, с которой она выполняется. Выбор скорости работы каждой машины S(t) определяется при составлении расписания и может меняться с течением времени. Широко известное в инженерных кругах правило кубического корня для устройств, использующих микросхемы CMOS, гласит, что потребляемая мощность пропорциональна третьей степени (кубу) от скорости вычислений. В статьях по теории расписаний, как правило, рассматривается произвольное значение ct > 1 этого степенного параметра. Расход энергии определяется интегрированием функции мощности на интервале времени работы машины. Требуется выполнить все работы внутри заданных интервалов обслуживания так, чтобы суммарный расход энергии был минимален.

Содержание главы разделено на два больших раздела в зависимости от подхода к построению приближенных алгоритмов.

В первом разделе рассматривается подход, основанный на преобразовании оптимальных решений, в которых есть прерывания работ, в допустимые решения без прерываний. Данный подход является одним из основных для построения приближенных алгоритмов с гарантированной оценкой точности для классических задач теории расписаний [35]. Часто построение оптимального расписания в задаче с прерываниями легче, чем построение оптимального решения в аналогичной задаче без прерываний. Например, как показано в [3, 6], задача P\pmtn, rj, dj\Е построения энергетически

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

трудна в сильном смысле [4]. Однако необходимым условием для построения хорошего приближенного решения является близость между собой значений оптимального решения задачи с прерываниями и задачи без прерываний. В разделе 3.1 приведен пример задачи минимизации энергии на одной машине, для которого отношение оптимума расписания без прерываний к оптимуму расписания с прерываниями больше, чем .

Таким образом, в задачах, рассматриваемых в главе 3, в общем случае оптимум расписания с прерываниями не является хорошей нижней оценкой на оптимум расписания без прерываний. Тем не менее, для частных случаев задачи и Р\г3, с!^\Е удается

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

Основными результатами раздела являются разработка алгоритмов 3.2 и 3.3 и анализ их точности в худшем случае.

Для задачи 1|алгоритм 3.2 находит расписание а с оценкой Е(а) < (1+ ^™*)аОРТ, которая зависит от отношения максимального объема работы И^щах к минимальному Для задачи, в которой все работы имеют одинаковые объемы, алгоритм является 2-приближенным.

Для задачи Р\г^, \Е, в которой никакие два интервала выполнения работ не вложены друг в друга, предложен 2-приближенный алгоритм 3.3. С использованием оптимального решения задачи с прерываниями, в алгоритме вычисляется длительность каждой работы, а затем работы упорядочиваются по неубыванию директивных сроков.

Результаты этого раздела получены в соавторстве с Е. Бампи-сом, Д. Лукарелли, Д. Летсиосом и И. Немпарисом.

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

переменных. По сравнению с релаксациями стандартных задач ЦЛП релаксации задач очень большой размерности дают значительно лучшую нижнюю оценку, однако их решение связано с дополнительными трудностями. Заметим, что если задача линейного программирования имеет экспоненциальное число переменных и полиномиальное число ограничений, то двойственная к ней задача имеет экспоненциальное число ограничений и полиномиальное число переменных. Предположим, что для двойственной задачи можно построить полиномиальный отделяющий оракул, то есть алгоритм, который для заданного решения либо устанавливает его допустимость, либо находит ограничение линейной программы, которое нарушается. Существование полиномиального отделяющего оракула позволяет решить двойственную задачу методом эллипсоидов [24]. В свою очередь, построенное методом эллипсоидов оптимальное решение двойственной задачи позволяет найти оптимальное решение прямой задачи за полиномиальное время, так как значения прямых переменных, соответствующих двойственным ограничениям, которые не были нарушены в ходе решения двойственной задачи, равны нулю. Округление полученного решения задачи ЛП с экспоненциальным числом переменных позволяет находить хорошие приближенные решения для неоднородных задач построения энергетически эффективных расписаний, в которых параметры работ зависят от машин, на которых они выполняются.

Для произвольного действительного параметра а > 1 назовем обобщенным числом Белла величину

соответствующую а-му (дробному) моменту случайной величины с распределением Пуассона и математическим ожиданием равным единице. Пусть г > 0 — произвольное фиксированное число. В разделе 3.2 представлены следующие рандомизированные приближенные алгоритмы для задач построения энергетически эффективных расписаний:

• (1 + е)а-Вс-приближенный алгоритм для неоднородной задачи на параллельных машинах с прерываниями без переноса работ с машины на машину,

• 2а 1 (1 + е)аВа-приближенный алгоритм для задачи на одной машине без прерываний работ,

• (1 + е)аВ ^-приближенный алгоритм для неоднородной цеховой задачи рабочего типа с прерываниями работ.

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

Результаты раздела 3.2 получены в соавторстве с Е. Бамписом, Д. Лукарелли, Д. Летсиосом и М.Свириденко.

Четвертая глава посвящена задачам построения расписаний с малыми задержками передачи данных. Данные задачи моделируют вычисление на параллельных компьютерах и были впервые описаны в статье Рэйварда-Смита [33] в 1987 г. Множество работ J = {Л, • • •, Jn) должно быть выполнено на m идентичных параллельных машинах. На множестве работ задан частичный порядок. Если работы, связанные отношением предшествования, выполняются на разных машинах, то требуется дополнительное время на передачу данных от одной машины к другой. Если обе работы выполняются на одной машине, то считается, что величина задержки несущественна, и она полагается равной нулю. В [25] показано, что задачи минимизации длины расписания (Стах) и минимизации взвешенной суммы моментов окончания работ wjCj) на неограниченном числе машин (m > п) являются NP-трудными, даже если все задержки и длительности всех работ единичные. Поэтому большинство теоретических работ в этом направлении связаны с построением приближенных алгоритмов с гарантированными оценками точности. Основные результаты четвертой главы посвящены задачам с малыми задержками, т.е. когда величина наибольшей задержки не превосходит минимальной длительности работы. Для обозначения задач с малыми задержками во втором поле трехин-дексной записи используется сокращение set от термина "small communication time" в английском языке.

• Задача Poo\sct|Cmax, ^ 'шгС\ — двухкритериальная задача построения расписания работ на неограниченном множестве па-

раллельных машин с малыми задержками передачи данных.

• Задача Роо(Р2)|яс£|Стах — задача минимизации длины расписания работ на неограниченном множестве параллельных двухпроцессорных машин с малыми задержками передачи данных.

В первом разделе изучается задача Роо|ас£|Стах1 1С 'шгСг-, в которой требуется найти "хорошее" расписание относительно двух критериев Стах и в 1371 Штайн и В айн для большого

класса задач доказали существование расписаний, для которых значения целевых функций Стах и ^ С3 не более чем в два раза отличаются от оптимальных значений этих целевых функций в однокритериальных версиях рассматриваемых задач. В последующем Аслам, Рассала, Штайн и Юнг [7] улучшили эту оценку до значения 1.806.

Допустимое расписание о относительно критериев /о и /х называется (а, /3)-расписанием, если /0(ст) < а/0(схо) и М<т) < /Щстг), где <то - оптимальное расписание для критерия /о, и о\ - оптимальное расписание для критерия Д. Алгоритм, строящий такое расписание для любого примера двухкритериальной задачи, называется (а, ¡3)-приближенным алгоритмом.

Основным результатом раздела является семейство (а, /^-приближенных алгоритмов для задачи Роо|5с£|Стах, (алгоритм 4.2).

Теорема 20 Для любого ф € [0.721,1.5] алгоритм 4.2 является (а:, /3)-приближенным алгоритмом для задачи Роо|5С<;|Ста;г;, ^С^,

где а=^ + йфи/3 = -—3-.

5 9 з-Э(1-§0)г

В частности, для ф = 0.927 алгоритм 4.2 находит (1.746,1.746)-раснисание.

Полученные результаты обобщаются для задачи, в которой для каждой работы ■1] дополнительно задано время доставки qj и требуется одновременно минимизировать величины Cj+qj и

Заметим, что рассматриваемые в этом разделе задачи не попадают в список задач Штайна и Вайна, для которых доказано существование (а, /?)-расписаний. Следующий результат показывает,

что для задачи Роо\исЬ,Р] = 11Сгпах, Е WjCj, в которой длительности всех работ и задержки равны между собой, существует (а, ¡3)-расписание лучше чем то, что находит алгоритм 4.2.

Теорема 22 Для любого ф € [0,1] существует (1 + приближенное решение для задачи Рос\исЛ,р^ = 1|Стах, ^ ги^С^.

Из теоремы 22 следует, что для любого примера задачи Роо\ис(, ■р^ = 1\Стах, существует (1.445,1.445)-расписание.

В конце раздела приближенное решение задачи с неограниченным числом машин используется для получения приближенного решения задачи с заданным (фиксированным) числом машин. В частности, для задачи с единичными задержками предложен (а, /3)-приближенный алгоритм 4.3.

Теорема 23 Для любого ф е [0,1.5] алгоритм 4-3 является (а, (3)-приближенным алгоритмом для задачи Р\исЬ,р— 1|Стах,

Е^-С,- со значениями а = ^ + ^фи(3— ™ + |((1 — §</>)~3 — I)-1.

Результаты этого раздела получены в соавторстве с Е. Бампи-сом.

Во втором разделе рассматривается задача Роо{Р2)\ясЦС1Ш1^, в которой каждая машина может обрабатывать две работы одновременно. Обозначим через Ф отношение минимальной длительности работы к максимальной задержке. Как и в предыдущем разделе, предполагается, что задержки малы, то есть Ф > 1. В [12] показано, что существование ^приближенного алгоритма с р < | для этой задачи влечет совпадение классов Р и ИР, даже если длительности всех работ и все задержки равны 1. В разделе 4.2 представлен 12(Ф + 1)/(12Ф + 1)-приближенный алгоритм для задачи Роо(Р2)|5с^ Стах. Алгоритм основан на округлении решения соответствующей задачи линейного программирования. Интересно отметить, что целочисленная постановка этой задачи (ЦЛП) не эквивалентна задаче Роо(Р2)\зс1\Ст;-1Х, и оптимальное решение задачи ЦЛП может быть хуже, чем оптимальное решение задачи Рсх>(Р2)МСтах.

Результаты этого раздела получены в соавторстве с Е. Бампи-сом и Р. Жиродо.

В пятой главе рассматриваются цеховые задачи открытого типа с маршрутизацией. Данные задачи являются обобщением двух классических МР-трудиьтх задач дискретной оптимизации: цеховой задачи открытого типа и метрической задачи коммивояжера. Множество работ J = {./1,..., ,7,1} должно быть выполнено на т специализированных машинах Мь ..., Мт. Каждая работа Jj состоит из т операций ■ ■ ■ Операция Ог] выполняется на машине Ми ее длительность составляет р^ € Z+ единиц времени. Работы и машины расположены в узлах транспортной сети (3 = (V, Е), которая задается полным реберно-взвешенным графом. Веса ребер удовлетворяют неравенству треугольника и соответствуют времени перемещения машины из одной вершины в другую. Для выполнения любой работы каждая машина должна переместиться в вершину, в которой эта работа находится. Изначально все машины расположены в одной вершине «о и должны вернуться в нее после выполнения всех работ. Все машины перемещаются с одинаковой скоростью, то есть затрачивают на перемещение из вершины V] в вершину ь/г время т^. Операции каждой работы могут выполняться в произвольном порядке. Прерывания в процессе выполнения операций запрещены. Различные машины не могут выполнять операции одной работы одновременно, и каждая машина обрабатывает не более одной работы в каждый момент времени. Требуется минимизировать длину расписания, т.е. момент возвращения последней машины в вершину ед после выполнения всех работ.

Цеховые задачи, в которых машины перемещаются между работами, расположенными в узлах транспортной сети, впервые были рассмотрены в [8, 9, 10, 11]. Примеры задач, в которых машины должны перемещаться между деталями, возникают при обработке тяжелых или громоздких деталей или при построении расписания работы роботов, которые осуществляют ежедневное техническое обслуживание неподвижных объектов, расположенных в различных частях цеха [9]. Цеховая задача открытого типа с маршрутизацией также возникла при автоматическом планировании маршрутов экскурсий в Национальном Дворцовом музее в городе Тайбэй, входящим в пятерку крупнейших музеев мира [19, 38].

Цеховая задача открытого типа с маршрутизацией является

КР-трудной в сильном смысле, даже если работы требуется выполнить одной машиной или все работы лежат в одной вершине. Более того, как показано в [11], эта задача МР-труд на для случая двух машин, когда все работы расположены в узлах сети, состоящей из двух вершин. Поэтому данная глава посвящена построению приближенных алгоритмов для различных вариантов цеховой задачи открытого типа с маршрутизацией.

В первых двух разделах приводятся приближенные алгоритмы для задачи с произвольным числом машин и произвольной транспортной сетью. Первый алгоритм (алгоритм 5.3) основан на простых комбинаторных свойствах рассматриваемой задачи. В нем строится гамильтонов цикл, длина которого не более чем в полтора раза больше длины минимального гамильтонова цикла. Затем п исходных работ преобразуется в 0(у/т) новых работ. Новый пример решается жадным алгоритмом, и полученное расписание перестраивается в допустимое расписание исходной задачи. Алгоритм 5.3 находит расписание, длина которого не более чем в ((\/3 + у/2)у/т + 3.5) раз больше нижней оценки, за время 0(п3). Трудоемкость алгоритма может быть понижена до 0(п2) за счет увеличения константы перед л/т.

Алгоритм 5.4, рассматриваемый во втором разделе, является 0(1о» т)-приближенным алгоритмом и имеет асимптотически лучшую точность по сравнению с алгоритмом 5.3. Алгоритм 5.4 основан на сведении цеховой задачи открытого типа с маршрутизацией к цеховой задаче рабочего типа с единичными длительностями работ. Для последней задачи все известные алгоритмы основаны на применении локальной леммы Ловаша и, хотя теоретически их трудоемкость ограничена полиномом от размера входа задачи, их реализация сопряжена со значительными трудностями.

В третьем разделе рассматривается задача с двумя машинами и произвольной транспортной сетью. В [11] для этой задачи предложен ^-приближенный алгоритм. В разделе 5.3 предложен новый приближенный алгоритм (алгоритм 5.7), который имеет ту же трудоемкость, но лучшую оценку качества получаемых решений.

Теорема 28 Алгоритм 5Л является 1.625-приближенным алгоритмом для задачи 1Ю2\\Стах, и время его работы равно 0(п3).

В следующем разделе рассматривается задача с двумя машинами в предположении, что кратчайший обход вершин транспортной сети может быть найден за полиномиальное время. Для этой задачи предложен (4/3)-приближенный алгоритм, который имеет линейную трудоемкость, если оптимальный обход сети уже известен.

Результаты разделов 5.1, 5.3 и 5.4 получены в соавторстве с С. Севастьяновым и И. Черных.

Основными и наиболее интересными результатами пятой главы являются точный алгоритм динамического программирования и вполне полиномиальная приближенная схема для задачи Ж)2||У| = 21Стах с двумя машинами на двухвершинной сети, представленные в разделе 5.5.

Авербах, Берман и Черных [11] доказали, что задача ГЮ2\\У\ = 21¿тах является ХР-трудгюй в обычным смысле и предложили для ее решения (6/5)-приближенный алгоритм, оставив открытым вопрос о существовании для нее точного псевдополиномиального алгоритма. Построению такого алгоритма и посвящен последний раздел пятой главы.

Первым шагом к построению алгоритма динамического программирования для задачи маршрутизации с двумя машинами на двухвершинной сети является разбиение множества примеров этой задачи на простые и сложные. Обозначим через Лг() — множество работ в вершине г>0 и через — множество работ в вершине У\. Напомним, что изначально обе машины расположены в вершине уо и должны вернуться в нее после выполнения всех работ. Пусть 1тах обозначает максимальную нагрузку машины. Напомним, что каждая работа состоит из двух операций. Обозначим через «/о работу с максимальной меньшей операцией. Пусть с10 — сумма длительностей двух операций работы ./ц, а Ля — тривиальная нижняя оценка длины расписания. Тогда следующие примеры задачи 1102\\У\ = 2|С,тах разрешимы за линейное от числа работ время.

Теорема 30 Если в примере I задачи Л02||У| = 2\Стах выполнено одно из двух следующих условий:

а) ,70 £ Л'о,

Ь) ,]() £ АТ1 и (¡0 >

то оптимальное расписание имеет длину Лд и может быть построено за время 0(п).

Таким образом, только примеры, в которых работа /о лежит в удаленной вершине и ее длина меньше /тах, являются КР-трудными. Расписание называется каноническим, если множество работ может быть разбито на не более чем восемь непересекающихся подмножеств, для которых выполнены следующие условия:

1) все работы, принадлежащие одному подмножеству, расположены в одной вершине;

2) все работы, принадлежащие одному подмножеству, выполняются блоком на каждой машине;

3) все работы, принадлежащие одному подмножеству, выполняются либо сначала на машине А, потом на машине В, либо наоборот;

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

Показано, что для любого трудного примера существует каноническое оптимальное расписание. Причем, длина канонического расписания зависит только от разбиения исходного множества работ на непересекающиеся подмножества и может быть вычислена за полиномиальное от числа работ время. Используя свойства канонических расписаний, трудный пример задачи Я.02\\У\ = 2|Стах можно решить алгоритмом динамического программирования за время 0(пА24), где А = ^з^а^г

Используя стандартную технику округления [26], можно трансформировать алгоритм динамического программирования во вполне полиномиальную приближенную схему, т.е. для любого фиксированного е > 0 построить (1 + е)-приближенный алгоритм, время работы которого ограничено полиномом от числа работ и величины р

В заключении перечисляются основные результаты диссертации.

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

[1] Гэри М., Джонсон Д. Вычислительные машины и труднореша-емые задачи. — М.: Мир, 1982. — 416 с.

[2] Albers S. Energy-efficient algorithms // Communications of the ACM — 2010 - Vol. 53(5) - P. 86-96.

[3] Albers S., Antoniadis A., and Greiner G. On multi-processor speed scaling with migration: extended abstract // Proceedings of 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2011) - 2011 - P. 279-288.

[4] Albers S., Miiller F., and Schmelzer S. Speed scaling on parallel processors // Proceedings of 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2007) - 2007 - P. 289298.

[5] Amir A., Kaplan E.H. Relocation problems are hard // International Journal of Computer Mathematics — 1988 — Vol. 25 - P. 101-110.

[6] Angel E., Bampis E., Kacem F., and Letsios D. Speed scaling on parallel processors with migration // Proceedings of 18th International European Conference on Parallel and Distributed Computing (Euro-Par 2012), Lecture Notes in Computer Science, Berlin: Springer - 2012 - Vol. 7484 - P. 128-140.

[7] Aslam J., Rasala A., Stein C., Young N. Improved bicriteria existence theorems for scheduling // Proceedings of ACM-SIAM Symposium on Discrete Algorithms — 1999 — P. 846-847.

[8] Averbakh I., Berman O. Routing two-machine flowshop problems on networks with special structure // Transportation Science — 1996 - Vol 30(4) - P. 303-314.

[9] Averbakh I., Berman O. A simple heuristic for m-machine flow-shop and its applications in routing-scheduling problems // Operations Research - 1999 - Vol. 47(1) - 165-170.

[10] Averbakh I., Berman O., Chernykh I. A f-approximation algorithm for the two-machine routing open shop problem on a 2-node network // European Journal of Operational Research — 2005 - Vol. 166(1) - P. 3-24.

[11] Averbakh I., Berman O., Chernykh I. The routing open-shop problem on a network: complexity and approximation // European Journal of Operational Research — 2006 — Vol. 173(2) — P. 521539.

[12] Bampis E., Giroudeau R., König J.-C. On the hardness of approximating the precedence constrained multiprocessor scheduling problem with hierarchical communications // RAIRO-RO — 2002 — Vol. 36 — P. 21-36.

[13] Blazewicz J., Barcelo J., Kubiak W., Röck H. Scheduling tasks on two processors with deadlines and additionsl resources // European Journal of Operational Research — 1986 — Vol. 26 (3) — P. 364 -370.

[14] Blazewicz J., Brauner N., Finke G. Scheduling with discrete resource constraints // Handbook of Scheduling. Algorithms, Models, and Performance Analysis, Ch. 23. — Boca Raton, London, New York, Washington, D.C.: Chapman k Hall, — P. 23-1 - 23-18.

[15] Blazewicz J. and Ecker K. A linear time algorithm for restricted bin packing and scheduling problems // Operations Research Letters — 1983 — Vol. 2 (2) — P. 80-83.

[16] Blazewicz J., Lenstra J.K., Rinnoy Kan A.H.G. Scheduling subject to resource constraints: classification and complexity // Discrete Applied Mathematics — 1983 — Vol. 5 (1) — P. 11-24.

[17] Bo Chen, Potts C.N., 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 Publisher, Amsterdam (1998), Vol. 3 - P. 21-169.

[18] Brucker, P. Scheduling algorithms — Springer-Verlag, Berlin, Heidelberg, Germany — 1998.

[19] Chou S.-Y., Lin S.-W., Museum visitor routing problem with the ballaneing of concurrent visitors // Complex Systems Concurrent Engineering - 2007 - Vol. 6 - P. 345-353.

[20] Chrétienne P., Coffman Jr. E.J., Lenstra J.K., and Liu. Z. Scheduling theory and its applications. — New-York: Wiley, 1995.

[21] Darte A., Robert Y., Vivien F. Scheduling and automated parallelization. — Birkhauser, Boston, 2000.

[22] Drozdowski M. Scheduling for parallel processing— London: Springer-Verlag, 2009.

[23] Graham R.L., Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G. Optimization and approximation in determenistic scheduling: a servey // Annals of Discrete Mathematics — 1979 — Vol. 5 — P. 287-326.

[24] GrÔtschel M., Lovas L., Schrijver A. Geometric algorithms and combinatorial optimization. — Springer-Verlag, 1988.

[25] Hoogeveen J.A., Lenstra J.K. and Veltman B. Three, four, five, six, or the complexity of scheduling with communication delays // Operations Research Letters — 1994 — Vol. 16 — P. 129-137.

[26] Ibarra O.H., Kim C.E. Fast approximation algorithm for the knapsack and sum of subset problems // Journal of the Association for Computing Machinery - 1975 - Vol. 22 - P. 463-468.

[27] Jackson J.R. An extension of Johnson's results on job lot scheduling // Naval Research Logistics Quaterly. — 1956. — Vol. 3. - P. 201-203.

[28] Johnson S.M. Optimal two- and three stage production schedules with set-up times included / / Naval Research Logistic Quaterly — 1954 — Vol. 1. - P. 61-68.

[29] Kaplan E.H. and Amir A. A fast feasibility test for relocation problems // European Journal of Operational Research — 1988 — Vol. 38. — P. 201-205.

[30] Kelley J.E. Computers and operations research in road building // Operations Research, Computing and Management Decisions, Symposium Proceedings, Case Institute of Technology (Jan. 31, Feb. 1, 2, 1957) — 1957 — P. 58-68.

[31] Kelley J.E., Walker M.R. Critical path planning and scheduling: an introduction. — Mauchly Associates, Ambler PA, 1959.

[32] Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G., and Shmoys D.B. Sequencing and scheduling: algorithms and complexity // in Handbooks in Operations Research and Management Science, Volume 4, Logistics of Production and Inventory, ed. S. Graves, A.H.G. Rinnooy Kan, and P. Zipkin. North Holland, Amsterdam.

— 1993. — P. 445-522.

[33] Ray ward-Smith V.J. UET scheduling with unit interprocessor communication delays // Discrete Applayd Mathematics — 1987

- Vol. 18 - P. 55-71.

[34] Sinen O. Task scheduling for parallel systems. — New Jersey: Wiley, Hoboken, 2007.

[35] Skutella M. List scheduling in order of a-points on a single machine // Efficient Approximation and Online Algorithms: Recent Progress on Classical Combinatorial Optimization Problems and New Applications in: Lecture Notes in Comp. Sci. — 2006 — Vol. 3484. - P. 250 - 291.

[36] Smith W.E. Various optimizers for single stage production // Naval Research Logistics Quaterly. — 1956 — Vol. 3. — P. 59-66.

[37] Stein C., Wein J. On the existence of schedules that are near-optimal for both makespan and total weighted completion time // Operations Research Letters — 1997 — Vol. 21, N 3 — PI 15-122.

[38] Yu V. F., Lin S.-W., Chou S.-Y. The museum visitor routing problem // Applied Mathematics and Computation — 2010 — Vol. 216(3) - P. 719-729.

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

1. Баптист Ф., Карлье Ж., Керан М., Кононов A.B., Севастьянов C.B., Свириденко М. Структурные свойства оптимальных расписаний с прерываниями операций // Дискретный анализ и исследование операций. — 2009. — Т 16, N 1. — С. 3-36.

2. Каширских К.Н., Кононов A.B., Севастьянов C.B., Черных И .Д. Полиномиально разрешимый случай двухстадийной задачи open shop с тремя машинами / / Дискретный анализ и исследование операций. Серия 1. - 2001. - Т 8, N 1. - С. 24-40.

3. Кононов A.B. О расписаниях работ на одной машине с длительностями, нелинейно зависящими от времени. // Дискретный анализ и исследование операций. — 1995. — Т 2, N 1. — С. 21-35.

4. Кононов A.B. Комбинаторная сложность составления расписаний для работ с простым линейным ростом длительностей // Дискретный анализ и исследование операций. — 1996. — Т 3, N 2. - С. 15-32.

5. Кононов A.B. Задачи теории расписаний на одной машине с длительностями работ, пропорциональными произвольной функции // Дискретный анализ и исследование операций. — 1998. — Т 5, N 3. - С. 17-37.

6. Кононов A.B. О цеховой задаче открытого типа на двух машинах с маршрутизацией в двух-вершшшой сети // Дискретный анализ и исследование операций. — 2012. — Т 19, N 2. — С. 54-74.

7. Ageev A., Fishkin A., Kononov A., Sevastianov S. Open block scheduling in optical communication networks. // Theoretical Computer Science. - 2006. - V. 361. - P. 257-274.

8. Angel E., Bampis E., Kononov A. On the approximate tradeoff for bicriteria batching and parallel machine scheduling problems. // Theoretical Computer Science. - 2003. - V. 306, N 1-3 - P. 319-338.

9. Bampis E., Giroudeau R., Kononov A. Scheduling tasks with small communication delays for clusters of processors. // Annals of Operations Research. — 2004. — V.129, N 1. — P. 47-63.

10. Bampis E., Kononov A. Bicriteria approximation algorithms for scheduling problems with communication delays. // Journal of Scheduling. — 2005 — V.8, N 4. — P. 281-294.

11. E. Bampis, A. Kononov, D. Letsios, G. Lucarelli, I. Nemparis, Prom preemptive to non-preemptive speed-scaling scheduling. // COCOON 2013, Lecture Notes in Computer Science — 2013 — V 7936 — p. 134-146.

12. Bampis E., Kononov A., Letsios D., Lucarelli G., Sviridenko M. Energy efficient scheduling and routing via randomized rounding // FSTTCS 2013, LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik — 2013.

13. Baptiste Ph., Carlier J., Kononov A., Queyranne M., Sevastianov S., Sviridenko M. Properties of optimal schedules in preemptive shop scheduling. // Discrete Applied Mathematics. — 2011 — V 159 — P 272-280.

14. Baptiste Ph., Carlier J., Kononov A., Queyranne M., Sevastianov S., Sviridenko M. Integer preemptive scheduling on parallel machines. // Operations Research Letters. — 2012 — V. 40, N 6. — P. 440-444.

15. Chernykh I., Kononov A., Sevastyanov S. Efficient approximation algorithms for the routing open shop problem. // Computers & Operations Research. — 2013 — V. 40, N 3. — P. 841-847.

16. Gawiejnowicz S., Kononov A. NP-hard cases in scheduling deteriorating jobs on dedicated machines. // Journal of the Operational Research Society. — 2001. — V.52. — P. 708-717.

17. Gawiejnowicz S., Kononov A. Complexity and approximability of scheduling resumable proportionally deteriorating jobs. // European Journal of Operational Research. — 2010. — V. 200, N 1. — P. 305-308.

30

18. Gawiejnowicz S., Kononov A. Isomorphic scheduling problems. // Annals of operations research. - 2014 - V. 213. - P. 131-145.

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

— 2012. — V. 15. — P. 487-497.

20. Kononov A., Lin B.M.-T. Relocation problems with multiple working crews. // Discrete Optimization. — 2006. — V. 3. — P. 366381.

21. Kononov A., Lin B.M.-T. Minimizing the total weighted completion time in the relocation problem. // Journal of Scheduling. — 2010 — V.13, N 2. — P. 123-129.

22. Kononov A., Sevastyanov S. Graph structure analysis and computational tractability of scheduling problems // In: M. Dehmer and F. Emmert-Streib (Eds.) Analysis of Complex Networks: From Biology to Linguistics, 2009, Wiley-VCH Verlag Gmbh & Co. KGaA, Weinheim ISBN 978-3-527-32345-6, P. 295-322.

23. Kononov A., Sevastianov S., Sviridenko M. A complete 4-para-metric complexity classification of short shop scheduling problems. // Journal of Scheduling. - 2012. - V. 15. - P. 427-446.

24. Kononov A., Sevastianov S., Tchernykh I. When the difference in machine loads leads to efficient scheduling in open shops. // Annals of Operations Research. - 1999 - V. 92. - P. 211-239.

25. Kononov A., Sviridenko M. Linear time combinatorial approximation scheme for makespan minimization in open shop with release dates. // Operations Research Letters. - 2002. - V.30. - P. 276-280.

26. Lin B.M.-T., Kononov A. Customer order scheduling to minimize the number of late jobs. // European Journal of Operational Research.

— 2007. — V. 183, N 2. — P. 944-948.

Кононов Александр Вениаминович

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

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

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

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