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

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

ГАФАРОВ Евгений Рашидович

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

специальность 01 01 09 - дискретная математика и математическая

кибернетика

Автореферат

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

□03171706

Москва - 2008

003171706

Работа выполнена в отделе математических проблем распознавания и методов комбинаторного анализа Вычислительного центра им А А Дородницына Российской академии наук

Научный руководитель доктор физико-математических наук, доцент Лазарев Александр Алексеевич

Официальные оппоненты доктор технических наук,

Ведущая организация Центральный экономико-математический институт РАН

Защита диссертации состоится "27" июня 2008 г в 9 часов на заседании диссертационного совета Д 212 156 05 при Московском физико-техническом инсти1уте (государственном университете)

С диссертацией можно ознакомиться в библиотеке МФТИ (ГУ)

Автореферат разослан "

Лл^Р 2008 г

профессор Коган Дмитрий Израилевич, Московский государственный университет приборостроения и информатики,

кандидат физико-математических наук Посыпкин Михаил Анатольевич, Институт системного анализа РАН

Федько О С

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

Актуальность темы.

Диссертационная работа посвящена исследованию №-трудных задач теории расписаний "Минимизация суммарного запаздывания для одного прибора" (далее 1 || и "Минимизация времени выполнения

проекта" (далее ИСРЭР, как принято в англоязычной литературе), а также алгоритмам решения классических комбинаторных задач "Разбиение" и "Ранец" 1

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

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

Фэри М , Джонсон Д Вычислительные машины и труднорешаемые задачи Пер с англ - М Мир, 1982 - 416 с

Цель работы заключается в исследовании задач 1 11 ^ Т3, НСРЭР для отыскания новых свойств оптимальных расписаний, построения на их основе алгоритмов решения и применения полученных результатов для классических №-трудных задач комбинаторной оптимизации "Разбиение" и "Ранец" Научная новизна.

1 Для задачи "Минимизация суммарного запаздывания для одного прибора" предложены новые точные (полиномиальные и псевдополиномиальные) и метаэвристические алгоритмы решения Проведены экспериментальные исследования алгоритмов Определена трудоемкость известных точных алгоритмов других исследователей Представлено доказательство ЫР-трудности одного частного канонического случая задачи

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

3 Для задачи "Минимизация времени выполнения проекта" проведен анализ известных нижних оценок функционала Получены новые оценки целевой функции Выдвинута гипотеза о том, что оптимальное значение целевой функции для задачи, когда запрещены прерывания при обслуживании требований, не более чем в два раза превышает оптимальное значение функционала в задаче, когда прерывания разрешены Гипотеза доказана для некоторых частных случаев

4 Показано, что для любого проекта (задача "Минимизация времени выполнения проекта") существует соответствующий проект с планарным сетевым графиком отношений предшествования

5 Предложен используемый на практике метаэвристический алгоритм решения задачи "Минимизация времени выполнения проекта", основанный на методе "Муравьиные колонии"

Методы исследования. При формулировке и доказательстве результатов использованы методы дискретной математики и

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

Теоретическая и практическая значимость. Полученные в работе результаты для задачи 1 11 Т3 могут быть использованы для построения алгоритмов решения многоприборных и многостадийных задач выбора очередности обслуживания, возникающих на практике Предложенные методы и подходы могут быть применены к исследованию других задач теории расписаний и комбинаторной оптимизации Результаты, полученные для задачи RCPSP, могут без значительных изменений использоваться на практике в программных продуктах MS Project, Spyder Project, Primavera В частности, результаты были применены в пакете "1С Управление строительной организацией"

Апробация работы. Результаты диссертационной работы

докладывались и обсуждались на XLIII и XLIV Международных студенческих конференциях «Студент и научно-технический прогресс» (Новосибирск, НГУ, 2005, 2006 гг), на XII Международной конференции «INCOM 2006 IFAC Symposium on Information Control Problems in Man-ufacturmg» (Сент-Этьен, Франция, 2006 г), на XVIII Международной конференции «ЕССО'05 European Chapter on Combmatorial Optimizaron» (Минск, Беларусь, 2005 г), на XIX Международной конференции «ЕССО'Об European Chapter on Combmatorial Optimization» (Порто, Португалия, 2006 г), на Международной конференции «OR'2006 International Conference on Operation Research» (Карлсруэ, Германия, 2006 г), на V Московской международной конференция по исследованию операций «ORM'2007 Moscow International Conference on Operation Research» (Москва, 2007 г), на научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук» (Долгопрудный, МФТИ, 2006 г), на научных семинарах Института проблем управления РАН (руководитель семинара профессор ДА Новиков, 2005-2007 гг), на научных семинарах отдела математических проблем распознавания и методов комбинаторного анализа Вычислительного Центра РАН (2005-2007 гг)

Публикации. По теме диссертации опубликовано 13 печатных работ,

в том числе три в изданиях из списка, рекомендованного ВАК РФ [1,2,3]

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, указателя основных обозначений и списка использованных источников (110 наименований) Содержит 21 таблицу и 39 иллюстраций Общий объем диссертации составляет 181 страница

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

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

В первой главе исследуется классическая задача теории расписаний - минимизация суммарного запаздывания для одного прибора (1 II Е Tj) Предложены полиномиальные и псевдополиномиальный алгоритмы решения частных случаев задачи Приводится доказательство NP-трудности в обычном смысле частного случая задачи Показано, что известные точные алгоритмы2,3, для которых не получена оценка трудоемкости, имеют экспоненциальную трудоемкость На основе точного алгоритма и метаэвристического алгоритма "Муравьиные колонии" построен Гибридный алгоритм Приводятся результаты экспериментальных исследований на трех классах примеров

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

Необходимо обслужить п требований на одном приборе Прерывания при обслуживании и обслуживание более одного требования в любой момент времени запрещены Для требования j £ N = {1,2, ,п} заданы продолжительность обслуживания р3 > 0 и директивный срок окончания обслуживания dv где N - множество требований, которые необходимо обслужить Задан момент освобождения прибора

'Лазарев А А Решение NP-трудной задачи теории расписаний минимизации суммарного запаздывания // Журнал Вычислительной математики и математической физиики - 2007 том 47, N 6 - С 1087— 1098

3Szwarc W , Grosso А , Delia Croce F Algorithmic paradoxes of the single machine total tardiness problem // Journal of Scheduling - 2001 - V 4 -P 93-104

to, с которого прибор готов начать обслуживание требований Все требования поступают на обслуживание одновременно в момент времени to Расписание обслуживания требований 7г строится с момента времени ¿о и однозначно задается перестановкой элементов множества N

Требуется построить расписание ж* обслуживания требований множества N, при котором достигается минимум функции F(tt, io) = max{0, с;(тг) — dj}, где с?(тг)- момент завершения обслуживания требования j при расписании ж Пусть 7Г = (j\,j2, ,Jn), тогда сЛ(тг) = ¿о + Р], и Cjk(т) = Сд_,(7г) + рл для к — 2,3, ,п Величина Tj{ir,to) — max{0,Cj(7r) — dj) называется запаздыванием требования j при расписании 7г, a F(tt, io) - суммарным запаздыванием требований множества N при расписании тг, построенном с момента времени to В случае, когда io = 0, будем обозначать Т}{ъ) и F(ir), соответственно Сформулированная задача является NP-трудной в обычном смысле4

В параграфе 12 описаны алгоритмы решения примеров рассматриваемой задачи, основанные на декомпозиционных свойствах задачи Приводится точный алгоритм А, использующий при построении расписания правила исключения 1-42,3 В процессе работы алгоритма А строится дерево поиска решения Ветвление в дереве поиска возникает в ситуации, когда для очередного требования j* с наибольшей продолжительностью обслуживания перебирается список из "подходящих позиций" После постановки требования f на "подходящую позицию", исходный пример разбивается на два подпримера, которые решаются аналогичным образом

В параграфе 1 3 рассмотрен частный случай В исследуемой задачи и алгоритмы его решения Приводится псевдополиномиальный алгоритм В-1 решения частного случая В-1 задачи, при котором выполняются ограничения d\ < < dn, рг > , > рп, dn — d\ < pn Далее кратко описана идея "Графической реализации" алгоритма В-1, с использованием которой становится возможным решать примеры с пецслочисленными параметрами и примеры "большого масштаба" Идея "Графической реализации" подробно рассматривается во второй главе данной диссертации

4Du J , Leung J Y -Т Minimizing total tardiness on one processor is NP-hard // Math Oper Res - 1990 - N 15 - P 483-495

Для частного случая В-1 general, при котором выполняются ограничения dmax — dmm < ртт, приводятся новые свойства оптимальных расписаний

Расписание я = (ji,j2, ,Jn) будем называть SPT-расписанием (short processing time), если выполняется р]к < рМк (для pJk — pJk+1 имеем d3k < dJk+1), к — 1,2, , п — 1 Расписание 7Г называют LPT-расписанием (large processing time), если pJk > рМк (для р3к — р3к+1 выполняется d]k < dn+l), к — 1,2, ,п- 1 Расписание тг = (juj2, ,3п) будем называть EDD-расписанием (early due date), если dJk < d3i+1 (для dJk — dJk+l выполняется pJk < р]к+1), к — 1,2, , n — 1

Лемма 1 Для случая B-l general существует оптимальное расписание вида {kedd,kspt)> ^edd u kspt ~ частичные расписания, построенные по правилам EDD и SPT, соответственно Кроме того, {Я-яяяЮКэрг} = 0, {itedd} LK^spt} = N

Лемма 2 Для случая B-l general существует оптимальное расписание вида {ttlpt,1,itspt)> ^lpt и кspt ~ частичные расписания, построенные по правилам LPT и SPT, соответственно, {тгEDD} fli^spr} = 0, I € N, {itedd} U{ttspt} UW = N

На основании данных двух свойств построен точный алгоритм В-1 general решения частного случая B-l general, трудоемкость которого составляет О^^Рз) операций

В параграфе 1 4 рассматриваются 2 частных NP-^грудных случая задачи Канонические DL-примеры 4 и Канонические LG-примеры Показано, что частный случай В-1 задачи является NP-трудным

в обычном смысле

Доказательство проведено сведением модифицированного примера задачи Четно-Нечетное Разбиение (ЧНР) к частному случаю В-1

Задача Четно-Нечетное Разбиение Задано упорядоченное множество из 2п положительных целых чисел В = {61,62, . ,62П}, 6, > 6,+ь для всех 1 < г < 2п — 1 Требуется определить, существует ли разбиение множества В на два подмножества Si и В2, такое, что выполняется = и для каждой пары чисел

{62,-1, h.i}, г = 1,2, , п, подмножество В\ (следовательно, и В2) содержит в точности один элемент из пары {621-1,621}

Обозначим 6г = Ь2г-1 - 62„ г = 1, ,п, 8 = <5» Построим модифицированный пример задачи ЧНР

«2п = М + Ъ,

°2г = а2,+2 + ъ, г = гг - 1, ,1, (1)

02г-1 = «2i + г — П, ,1,

где b » п5, М > п36

Очевидно выполняется а, > a!+i, Уг = 1,2, , 2n — 1, кроме того 6, = ¿22-1 - &2» = 02:-1 - 02!, 1 = 1, , П

Лемма 3 Исходный пример ЧНР имеет решение "ДА" тогда и только тогда, когда модифицированный пример ЧНР имеет решение "ДА"

Приведем полиномиальную схему сведения модифицированного примера ЧНР к частному случаю В-1

Количество требований в конструируемом примере равно 2n 4- 1 Требования обозначим следующим образом

Vi,V2,V3, V4, ,Vb-i,V2t, , V^n-i, V2n, V2n+i,

N = {1,2, , 2n, 2n + 1} Для упрощения будем использовать следующие обозначения параметров требований pv, = р>, civ, = dt, Ту, = Т„ су, — с,, г = 1, ,2п + 1 Пример, удовлетворяющий следующим ограничениям, будем называть Каноническим LG-примером

Pl>P2> ->Р2п+1, (21)

di < d2 < < d2n+i, (2 2)

d2n+i — d\< p2n+i, (2 3)

ftn+l = M = n\ (2 4)

P2n = Р2П+1 +b = a2n, (2 5)

P2i = P2i+2 + b = a2„ г = п-1, ,1, (2 6)

p2t-l = P2% + <5« = 02,-1, l = n, ,1, (2 7)

d2n+l = ]СГ=1 P2t + Pln+l + (2 8)

d2n = d2n+i — S, (2 9)

d2l = d2t+2 - (n - i)b + 6, г = n - 1, ,1, (210)

d2i~i — d2% — (n —1)6, — е<5г, г — п,. ,1, (2 11)

(2)

гдеЬ = пЧО<е<^|

Лемма 4 Для случая (2) при любом расписании количество запаздывающих требований равно или п, или п +1

Расписание вида

(И,1,^2,1, ^л+ъ^г,

будем называть Каноническим Ю-расписанием, где {Х,ъ Ц^} = {^-1,^2,}, г = 1,2, . ,п

Теорема 1 Для случая (2) все оптимальные расписания являются Каноническими или могут быть преобразованы к Каноническим расписаниям применением правила ЕББ к (п + 1) требованиям, обслуживаемым вначале расписания

Теорема 2 Решение примера ЧНР будет "ДА " тогда и только тогда, когда при оптимальном Каноническом расписании С2П+1(7Г) = ^2п+1

В параграфе 1 5 показано, что точный алгоритм А, использующий при построении расписания правила исключения 1-43 имеет экспоненциальную трудоемкость для некоторых частных случаев задачи 1 ||

Известно, что алгоритм, приведенный в работе Шварца и др 3 имеет трудоемкость, не превосходящую > но более точной оценки

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

Схема работы алгоритма, приведенного в работе Шварца и др, совпадает со схемой работы алгоритма А Как было сказано, в процессе работы алгоритма А конструируется дерево поиска решения

Теорема 3 Для случая ЭЭ алгоритмы, использующие только следующие способы сокращения перебора Правила исключения 1-4, использование Е3 и Ь3, построение модифицированного примера, умеют трудоемкость не меньше 0(п2аз1_1) операций

Теорема 4 Для случая ВР алгоритмы, использующие только следующие правила сокращения перебора правила исключения 1-4, использование Е3 и построение модифицированного примера, имеют трудоемкость 0(п2п!2)

Случай 57) является подслучаем Канонических ИЬ-примеров, а случай ВР - подслучаем случая В-1, при котором количество запаздывающих требований при любом расписаний постоянно Для случая ВР существует точный полиномиальный алгоритм решения

В параграфе 16 приводятся Гибридный алгоритм решения задачи и результаты сравнительного анализа его эффективности и эффективности метаэвристического алгоритма "Муравьиные колонии"

Гибридный алгоритм основан на точном алгоритме А и метаэвристическом алгоритме "Муравьиные колонии" В Гибридном алгоритме используется дерево поиска решения, конструируемое алгоритмом А, но при этом перебираются не все подходящие позиции для очередного требования у*, а только одна позиция, выбранная из множества подходящих согласно накопленной статистике о том, насколько хорошим было "поставить" требование ]* на данную позицию при предыдущих запусках алгоритма Идея "накопления статистики" о "качестве" выбора той или иной позиции и многократный запуск алгоритма - основа метаэвристического алгоритма "Муравьиные колонии"

В этом же параграфе приводятся результаты экспериментального сравнения эффективности Гибридного алгоритма и алгоритма "Муравьиные колонии" По результатам экспериментов, Гибридный а^ггоритм существенно эффективнее алгоритма "Муравьиные колонии" на тестовых примерах Поттса и ван Вассенхова Для 99 5% примеров Гибридным алгоритмом найдено точное решение Относительная погрешность не превосходит 05 % Среднее необходимое "количество муравьев" не превосходит 5

На "трудных" примерах случая В-1 Гибридный алгоритм уступает в точности алгоритму "Муравьиные колонии" , но находит точное решение более чем для 99% примеров Относительная погрешность не превосходит 0 01 %

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

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

Будем рассматривать следующие формулировки задач Задача Разбиение (в оптимизационной постановке) Задано упорядоченное множество из п положительных целых чисел В = {61,62, >6„} Требуется разбить множество В, на два подмножества В\ и ¿?2, так чтобы минимизировать значение

Задачу "Ранец" мы можем представить в виде задачи целочисленного линейного программирования с булевыми переменными

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

Ц>-Х>1

Ь,<еВ2

(3)

В параграфе 21 описан известный алгоритм динамического программирования5 для задачи "Ранец" трудоемкости 0(пА) операций

В параграфе 2 2 представлен Графический алгоритм решения задачи "Ранец" Графический алгоритм имеет ряд преимуществ перед алгоритмом динамического программирования С помощью Графического алгоритма можно решать примеры с нецелочисленными параметрами (а, ^ Z, г = 1,. ,п, А £ Z), примеры большого масштаба Известно, что при увеличении значений А, а„ г = 1, ,п, в к раз трудоемкость алгоритма динамического программирования основанного на принципе оптимальности Беллмана возрастет так же в к раз (особенно если исключить возможность обратного масштабирования небольшим изменением параметров) В Графическом алгоритме увеличение значений исходных параметров в к раз не окажет влияние на трудоемкость В Графическом алгоритме так же учитываются некоторые "внутренние свойства задачи" К примеру, предметы с минимальным соотношением Cj/o, могут не оказывать влияние на решение

Трудоемкость Графического алгоритма обсуждается в параграфе 2 3 Трудоемкость Графического алгоритма для примеров с целочисленными параметрами не превосходит 0(пА), в силу того, что на каждом шаге i = l, ,п рассматривается не более А точек В работе6 предложен альтернативный алгоритм динамического программирования для задачи о ранце с трудоемкостью 0(nfmax) операций Трудоемкость Графического алгоритма не превосходит 0(птт{А, fmax}) операций

В параграфе 2 4 представлен Графический алгоритм для задачи "Разбиение". Трудоемкость Графического алгоритма не превосходит 0(nZb евbj) Для целочисленных примеров, что соответствует трудоемкости алгоритма динамического программирования для задачи "Разбиение", представленного в работе Гэри и Джонсона

Необходимо заметить, что существует класс целочисленных примеров, на котором количество рассматриваемых в Графическом алгоритме

»Сигал И X, Иванова А П Введение в прикладное дискретное программирование теория и вычислительные алгоритмы // М Физматлит, 2002 - 240 с

«Пападимитриу X, Стайглиц К Комбинаторная оптимизация Алгоритмы и сложность // М Мир, 1985, - 512 с

точек t от шага к шагу растет экспоненциальным образом Например в = {ЬиЪ2, А} = {М,М - 1 ,М - 2, ,1,1, ,1}, где М -достаточно большое число, а сумма единиц в примере равна М(М + 1)/2,

В параграфе 2 6 представлены результаты экспериментального исследования трудоемкости Графического алгоритма для задачи "Разбиение"

В первой серии экспериментов предпринята попытка оценить количество точек t, рассматриваемых на каждом шаге алгоритма и выяснить, превосходит ли количество точек п2 или bmaX — max^gßbj

В ходе поставленного эксперимента рассматривались примеры задачи "Разбиение", размерностью п = 4,5, .,10 Для каждого значения п перебирались все примеры с целочисленными параметрами, для которых 30 > &i > 62 > > Ьп > 1 Для каждого примера с помощью Графического алгоритма подсчитывалось количество рассмотренных точек

По результатам экспериментов, для всех рассмотренных примеров количество рассмотренных точек t на каждом шаге не превосходит п2 Для 99% примеров количество рассмотренных алгоритмом точек не превосходит nbmax

В следующей серии экспериментов проведен сравнительный анализ эффективности алгоритма Balsub7 и Графического алгоритма

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

Рассматривались все примеры размерности п = 4,5, ,10, с целочисленными параметрами, для которых 40 > Ь\ > 62 > > К > 1 Во всех рассмотренных примерах трудоемкость алгоритма Balsub была больше, чем у Графического алгоритма, за исключением 38 примеров для п — 4 и 2 примеров для п = 5

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

'Keller Н , Pferschy U , Pismger D Knapsack problems// Springer, 2004, - 546 p

В третьей главе рассматриваются задачи построения расписания на быстродействие (минимизация общего момента окончания обслуживания всего множества требований) с ресурсными ограничениями и отношениями предшествования Данные задачи достаточно часто возникают на практике Например, при строительстве того или иного объекта на разных стадиях строительства необходимо разное количество трудовых ресурсов, строительной техники, материалов и т п Между отдельными стадиями строительства существуют отношения предшествования обусловленные технологией строительства Требуется составить расписание выполнения работ, при котором не нарушаются отношения предшествования, ресурсные ограничения, и при этом срок окончания строительства минимален Для решения данной задачи используются алгоритмы, основанные на методе ветвей и границ В диссертации проведен анализ существующих алгоритмов вычисления нижних и верхних оценок целевой функции Показано, что для задачи "Минимизация времени выполнения проекта" (ЛСРЭР) известные нижние оценки имеют относительную погрешность порядка размерности задачи или их нахождение является №-трудной задачей Выдвинута гипотеза, что оптимальные значения целевой функции для задачи ЛСРЭР с прерываниями в обслуживании требований и без прерываний отличаются не более чем в 2 раза Доказательство (или опровержение) данной гипотезы может оказать существенное влияние на построение эффективных алгоритмов решения задачи НСРЭР

Показано, что любой пример задачи НСРБР можно преобразовать в эквивалентный пример, граф отношений предшествования которого будет планарным, причем "мощность" (сумма количества вершин и ребер) графа не увеличится Некоторые полученные результаты были доведены до практической реализации в программном продукте "1С УСО" и получили хорошее экспериментальное подтверждение

В параграфе 3 1 представлена постановка задачи "Минимизация времени выполнения проекта" (ИСРБР)

Дано множество требований N = {1, , п} и К возобновляемых ресурсов к = 1, , К В каждый момент времени £ доступно С}к единиц ресурса к Заданы продолжительности обслуживания р, Е Z+ каждого требования г = 1, ,п Во время обслуживания требования г требуется < <3к единиц ресурса к = 1, , К После завершения

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

Между некоторыми парами требований заданы ограничения предшествования г —> j означает, что обслуживание требования j начинается не раньше окончания требования г

Обслуживание требований начинается в момент времени t = О Прерывание при обслуживании требований запрещены

Необходимо определить моменты времени начала обслуживания требований S„ г — 1, . ,п, так, чтобы минимизировать момент окончания выполнения всего проекта Стах — max,=li in{C,}, С\ — iSj+Pj При этом должны быть соблюдены следующие ограничения

1 в каждый момент времени t € [0, С^х) выполняется ftfcViW ^ Qk, к = 1, где <p,(f) = 1, если требование г обслуживается в момент времени t и <p,(i) = 0, в противном случае То есть требования в процессе своего выполнения должны быть полностью обеспечены ресурсами,

2 не нарушаются отношения предшествования, т е S, +рг < S]t если

Данную задачу будем называть задачей минимизация времени выполнения проекта и обозначать RCPSP (Resource-constrained Project Scheduling Problem, как принято называть в англоязычной литературе) К данной задаче за полиномиальное время сводится NP-трудная задача о многомерном ранце

Решение задачи RCPSP представляется в виде набора моментов начала обслуживания требований S = {Si, ., Sn) Решение, удовлетворяющее ресурсным ограничениям и ограничениям предшествования, будем называть допустимым

Можем представить структуру проекта как требования-в-вершинах ориентированного графа G = (V, А), где каждой вершине из V = {1, ,п} соответствует некоторое требование множества N — {1, ..,п}, а множество дуг А — {(г,з)\г,з € V\i —* j} соответствует ограничениям предшествования Очевидно, что допустимое решение существует только когда граф предшествования ацикличен

Обычно в рассмотрение вводят два фиктивных требования 0 и п + 1 с продолжительностями обслуживания ро = Рп+г = 0 Отношения предшествования 0-*]-*п+1, ] = 1, ,тг, = Чп+гк = 0 ,к — 1, . ,К

Будем обозначать через 17В верхнюю границу для оптимального значения Стах К примеру, можем принять 11В = рг

Для каждого требования г £ N определим временное окно [г,, с/,], в котором требование г должно быть обслужено при любом допустимом расписании 5

г0 = 0, г, = тах {г, + г = 1, , п + 1,

¿„+1 = 1/В, = тт — р,, г = п,п — 1, ,0

Обозначим - оптимальное значение целевой функции Пусть Стах(В*) - значение целевой функции при оптимальном расписании 5* Также будем обозначать С^аах(ртЫ) - оптимальное значение целевой функции для задачи КСРБР с прерываниями при обслуживании требований

В параграфе 3 2 приведены результаты анализа известных нижних оценок функционала для задачи ЛСРБР и представлена новая нижняя оценка Показано, что рассмотренные нижние оценки (ЬВо, ЬВ\, ЬВ3) не эффективны, либо их (ЬВю, ЬВм) нахождение является в общем случае ОТ-трудной задачей

Путь соединяющий вершины 0ип + 1 в сетевом графике и имеющий наибольшую длину называется критическим путем (длина складывается го продолжительности обслуживания требований, входящих в этот путь) Длина критического пути будет равна Стах(Б*), когда нет ресурсных ограничений То есть длина критического пути является нижней оценкой для Ста1(5*) Эту нижнюю оценку принято обозначать ЬВ0

Лемма 5 Существует пример В.СР8Р, для которого с™^ ^ = п

Другая нижняя оценка ЬВ\ может быть найдена за 0(пК) операций при рассмотрении каждого ресурса отдельно Назовем величину

!C"=i 4ih.Pi суммарной загрузкой ресурса к

Очевидно, что < Як • Cmax(S*), к = 1, , п Тогда значение

п

ЬВг = maxf ^ЪкРг/Як] t=i

является нижней оценкой для Cmax(S*) Лемма 6 Существует пример RCPSP, для которого Cmax{S*)—LBi —

EIUft-1

Обозначим множество требований, принадлежащих критическому пути через CP Для каждого требования г £ CP обозначим через ei максимальную длину интервала, входящего в [гг, dt], в котором требование г может обслуживаться параллельно с требованиями критического пути без нарушения ограничений на ресурсы Если выполняется ег < рг, то не существует допустимого расписания, при котором Cmax(S*) — LB0 Тогда значение

LBs = LBq + тах{тах{рг — ег, 0}} ifCP

также является нижней оценкой для Cmax(S*)

Лемма 7 Существует пример RCPSP, для которого ^ = п/2

В лучшем известном на данный момент алгоритме используется нижняя оценка ЬВц8

Лемма 8 Вычисление оценки ЬВм является NP-трудной задачей

Лемма 9 Существует пример RCPSP, для которого ^ » 2

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

8Mingozzi А , Maniezzo V , Ricciardelli S , Bianco L An exact alforithm for project scheduling with recource constraints based on new mathematical formulation// Management Science, 1998, - V44 - P 714-729

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

В этом же параграфе рассматривается NP-трудный частный случай задачи RCPSP с одним кумулятивным ресурсом мощности Q\ и пустым графом отношений предшествования Для данного частного случая доказана следующая теорема

Теорема 5 2 • С*тах{ртЫ ) > С^ - pmai, где ртах = maxjcNPj

В параграфе 3 4 приводятся свойства частного случая задачи RCPSP - задачи построения расписания для параллельных машин (PMS) Представлены новые свойства частного случая задачи PMS, когда продолжительности обслуживания всех требований равны, те р: = р

Частный случай задачи RCPSP с одним кумулятивным ресурсом Q; = тп и р^ — р, j = 1, , п, рассматривается в параграфе 3 5

В параграфе 3 6 представлены общие свойства задач построения расписания с отношениями предшествования, исследуются свойства планарности сетевого графика, и решение "обратного" примера Описан алгоритм укладки сетевого графика на плоскости без пересечения ребер Два примера задачи RCPSP будем называть эквивалентными, если первый пример сводится ко второму введением "пустых" требований (с нулевой продолжительностью) и удалением "лишних" связей, так что если между вершинами г и j был хотя бы один путь, то путь между ними останется Если пути не было, то он и не появится Значения целевой функции для эквивалентных примеров равны

Теорема 6 Для любого примера задачи RCPSP с п требованиями и е связями в графе G(V,E) отношений предшествования существует эквивалентный пример с планарным графом G'(V',E'), п' требованиями и ё связями, причем п + е>п' + е'

Доказательство теоремы основано на следующих леммах

Лемма 10 Если в графе отношений предшествования встречается подграф то можно его преобразовать, удаляя лишние дуги и добавляя "пустые" вершины

Лемма 11 Если в графе отношений предшествования встречается подграф то можно его преобразовать, удаляя лишние дуги

В параграфе 3 7 представлен метаэвристический алгоритм ACO (основанный на методе "Муравьиные колонии") решения задачи RCP-SP, применяемый в рамках программного продукта "1С Управление строительной организацией" (1С УСО)

В феврале 2007 года в продажу поступил программный продукт 1С УСО Цель создания программы - комплексная автоматизация основных подразделений строительной компании В 1С УСО в единую систему объединены модули бухгалтерский учет, управление финансами, закупками, запасами и тд Ядро системы - модуль "управление строительным производством", в котором реализованы базовые принципы управления проектами с учетом специфики строительного производства К маю 2008 года внедрение 1С УСО было осуществлено более чем на 140 предприятиях с численностью автоматизированных рабочих мест, превышающим 2400

В заключении изложены основные результаты и выводы работы

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

2 Доказано, что частный случай задачи "Минимизация суммарного запаздывания для одного прибора", при котором максимальная разница директивных сроков не превосходит минимального времени обслуживания требований, является NP-трудным в обычном смысле Доказательство проведено сведением известной задачи "Разбиение" к этому частному случаю

3 Предложены два Графических алгоритма решения классических NP-трудных задач "Разбиение" и "Ранец" Доказано, что трудоемкость Графических алгоритмов для целочисленных

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

4 Проведен анализ известных нижних оценок функционала задачи "Минимизация времени выполнения проекта" и предложена новая нижняя оценка Показано, что известные оценки не эффективны, либо их нахождение является в общем случае ОТ-трудной задачей

5 Выдвинута гипотеза о том, что значения целевой функции для задачи "Минимизация времени выполнения проекта" на быстродействие с прерываниями в обслуживании требований и без прерываний отличаются не более чем в 2 раза Приведены аргументы в пользу этой гипотезы

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

7 Ряд полученных результатов доведен до практической реализации в программном продукте "1С Управление строительной организацией" и получил хорошее экспериментальное подтверждение

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

1 Гафаров Е Р Гибридный алгоритм решения задачи минимизации суммарного запаздывания для одного прибора // Информационные технологии, 2007, - №1 - С 30-37

2 Гафаров Е Р, Лазарев А А Доказательство ЫР-трудности частного случал задачи минимизация суммарного запаздывания для одного прибора // Известия РАН Теория и системы управления - 2006 -№ 3-С 120-128

3 Лазарев А А , Кварацхелия А Г, Гафаров Е Р Алгоритмы решения NP-трудной проблемы минимизации суммарного запаздывания для одного прибора // Доклады Академии Наук, 2007 - Том 412, № 6 -С 739-742

4 Лазарев А А, Гафаров Е Р Теория расписаний Минимизация суммарного запаздывания для одного прибора // Научное издание, М Вычислительный центр им А А Дороницына РАН,2006 - 134 с

5 Лазарев А А , Гафаров Е Р Теория расписаний Исследование задач с отношениями предшествования и ресурсными ограничениями // Научное издание, М Вычислительный центр им А А Дороницына РАН, 2007 - 80 с

6 Гафаров Е Р Алгоритмы решения проблемы 1 11 ^ Т: и четно-нечетного разбиения // Материалы XLIII Международной научной студенческой конференции «Студент и научно-технический прогресс» Математика - Новосиб гос ун-т Новосибирск, 2005 -С 201-202

7 Гафаров Е Р Гибридный алгоритм решения проблемы 1 11 Tj // Материалы XLIV Международной научной студенческой конференции «Студент и научно-технический прогресс» Математика - Новосиб гос ун-т Новосибирск, 2006 - С 190-191

8 Lazarev А , Kvaratskheha А , Gafarov Е Algorithms for solving problems 1 11 Y^Tj and Even-Odd Partition // In Book of Abstracts of XVIII International Conference «European Chapters on Combinatorial Optimization» - Minsk, 26-28 V 2005 - P 32-33

9 Lazarev A A , Gafarov E R Graphical approach for solving combinatorial problems // Abstract Guide of International Conference on Operation Research OR 2006, Karlsruhe 6 09-8 09, Germany, P 59

10 Lazarev A A, Gafarov E R Algorithms for the single machine total tardiness problem // Abstract Guide of International Conference on Operation Research OR 2006, Karlsruhe 6 09-8 09, Germany, P 285

11 Lazarev A A , Gafarov E R Estimation of lower bounds for resources constrained project scheduling problem // Proceedings of V Moscow

International Conference on Operation Research (ORM2007), Moscow, 2007, P 236-238

12 Гафаров E P Задачи теории расписаний Алгоритмы и применение // Труды 49 научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук» Управление и прикладная математика, Москва-Долгопрудный, 2006 - С 82-83

13 Гафаров Е Р Алгоритмы решения NP-трудных задач теории расписаний и разбиения // Труды всероссийской конференции студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования», Москва, 2006 - С 120-121

В работах с соавторами лично Гафаровым Е Р сделано следующее В работах [2,3,4] доказана NP трудность частного случая задачи "Минимизация суммарного запаздывания для одного прибора", в работе [4] определена трудоемкость известных точных алгоритмов, разработан алгоритм решения частного случая задачи В-1 general и обоснована его эффективность В работах [l,4,7j предложен Гибридный алгоритм, а в работах [6,8,10] алгоритмы решения частных случаев задачи На основе идеи Лазарева А А о сокращении перебора в алгоритмах динамического программирования Гафаровым Е Р разработаны алгоритмы решения задач "Разбиение" и "Ранец" [9,12] В работах [5,11,12] проведены исследования оценок функционала для задачи "Минимизация времени выполнения проекта", предложено доказательство теоремы о планарности сетевого графика

Выражаю признательность д ф -мн В К Леонтьеву, дтн Сигалу ИХ, дтн Буркову В И, а также своему научному руководителю д ф -мн Лазареву А А за помощь в подготовке диссертации

Гафаров Евгений Рашидович

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

Подписало в печать 16 05 08 Формат 60x84 1/16 Бумага офсетная Уел печ л 1,0 Тираж 90 экз Заказ № 329

Московский физико-технический институт (государственный университет) НИЧ МФТИ 141700, Московская обл , Долгопрудный, Институтский пер, 9

Введение

1 Алгоритмы решения задачи 1 11 Y! Tj и ее частных случаев

1.1 Постановка задачи минимизации суммарного запаздывания для одного прибора 1 11 J2 Tj.

1.2 Точный алгоритм решения задачи

1.3 Случай В задачи 1| | £ Tj.

1.3.1 Случай В-1 и алгоритм его решения.

1.3.2 Алгоритм В-1 модифицированный.

1.3.3 Случай В-1 general и алгоритм его решения.

1.4 Канонические примеры задачи 1||

1.4.1 Проблема Четно-Нечетного Разбиения (ЧНР).

1.4.2 Канонические DL-примеры задачи 11 j Tj.

1.4.3 Канонические LG-примеры задачи 1| | Tj.

1.4.4 Свойства канонических LG-примеров.'

1.5 Трудоемкость известных алгоритмов для некоторых частных случаев задачи 1 ||

1.5.1 Свойства канонических DL-примеров задачи 1||

1.5.2 Трудоемкость известных алгоритмов для канонических DL-примеров.

1.5.3 Трудоемкость известнь£х алгоритмов для случая BF 67 1.6 Метаэвристический подход решения задачи 111 Tj.

1.6.1 Алгоритм АСО для задачи

1.6.2 Гибридный алгоритм.

1.6.3 Эффективность алгоритмов для тестовых примеров Поттса и Ван Вассенхова.

1.6.4 Эффективность алгоритмов для случая В-1.

1.6.5 Эффективность алгоритмов для канонических DL-примеров

Графические алгоритмы решения задач Разбиение и Ранец

2.1 Алгоритм динамического программирования для задачи Ранец

2.2 Графический алгоритм для задачи Ранец.

2.3 Трудоемкость графического алгоритма.

2.4 Графический алгоритм для задачи Разбиение

2.4.1 Сокращение рассматриваемого интервала (схлопывание).

2.4.2 Пример

2.5 Трудоемкость Графического алгоритма для задачи Разбиение

2.6 Экспериментальная оценка трудоемкости Графического алгоритма.

Исследование задач теории расписаний с отношениями предшествования и ресурсными ограничениями

3.1 Постановка задачи построения расписания проекта с учетом ограничений на ресурсы (RCPSP).

3.1.1 Алгоритм диспетчеризации для задачи RCPSP

3.1.2 Задача RCPSP с прерываниями обслуживания требований

3.2 Относительная погрешность нижних оценок для задачи RCPSP

3.2.1 LBq - длина критического пути

3.2.2 LB\ - максимальная загрузка ресурса.

3.2.3 LBs - дополнение критического пути.

3.2.4 Нижняя оценка Mingozzi

3.2.5 Оценка LBlg.

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

3.3.1 Доказательство гипотезы для случая задачи RCPSP с одним ресурсом.

3.4 Задача построения расписания для параллельных машин

3.5 Частный случай задачи RCPSP с одним кумулятивным ресурсом мощности Q\ и р3 = 1.

3.6 Свойства задач построения расписания с ограничениями предшествования.

3.6.1 Планарность сетевого графика для задач RCPSP и PMS

3.6.2 Алгоритм укладки сетевого графика на плоскости

- 53.6.3 Решение обратного примера для задач RCPSP и PMS 157 3.7 Метаэвристический алгоритм решения задачи RCPSP

3.7.1 Алгоритм АСО в рамках 1С:УСО

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

Принято считать, что исследование задач теории расписаний началось с публикации С. Джонсоном своей работы [64], в которой рассматривалась задача выбора очередности обслуживания множества деталей, каждая из которых должна пройти последовательную обработку на нескольких станках с целью минимизации момента окончания обслуживания всех деталей. Начиная с первых публикация по теории расписаний [63, 104, 98] выяснилось, что большинство рассматриваемых задач являются трудоемкими для решения. Поэтому, значительная часть работ в этой области посвящена исследованию и выявлению сложности задач1. Обзоры

На данный момент наиболее полная и постоянно обновляемая классификация NP-трудных и открытых задач теории расписаний приведена на сайтах http://www.mathematik.uni-osnabrueck.de/research/OR/class/ и http://www.lix.polytechnique.fr/ durr/query/. по задачам теории расписаний и их сложности представлены в работах Гэри и Джонсона [12], Карпа [14], Лаулера [81], Ленстры и др. [83], Танаева и др. [32, 33], Брукера [45, 46]

Большинство задач теории расписаний являются NP-трудными, поэтому важным направлением исследований является разработка подходов к их решению. Задачи теории расписаний принадлежат классу экстремальных комбинаторных задач и допускают формулировку в терминах математического программирования. Поэтому при разработке алгоритмов их решения применяются идеи метода ветвей и границ [17, 30], динамического программирования [1, 65], методов нахождения приближенного решения [18, 19, 35]. В последнее время динамически развивается направление разработки алгоритмов параллельных вычислений для решения таких задач [28]. Среди работ, посвященных методам решения задач дискретной оптимизации в целом и теории расписаний в частности, можно выделить статьи [2, 3, 4, 60] и книги [29, 30, 31, 32, 33, 34, 36, 40, 44, 45, 52, 91].

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

Диссертационная работа посвящена исследованию классической NP-трудной (в обычном смысле) задачи теории расписаний минимизации суммарного запаздывания для одного прибора (далее2 - задача 1 | |

2В теории расписаний принята следующая нотация для обозначения задач. Каждой задаче соответствует запись а | /3 | 7, где а обозначает количество и тип доступных приборов, /3 описывает дополнительные ограничения задачи (например, наличие отношения предшествования между требованиями), 7 представляет собой критерий задачи.

Т0), исследованию NP-трудной (в сильном смысле) задачи построения расписания проекта с учетом ограничений на ресурсы (RCPSP), построению новых алгоритмов решения известных NP-трудных задачи Разбиение и задачи Ранец.

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

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

Заключение

Сформулируем основные результаты диссертационной работы:

1. Предложены новые точные алгоритмы решения некоторых частных случаев задачи минимизации суммарного запаздывания для одного прибора 1 || Yl^j, в том числе: Алгоритм В-1 модифицированный решения частного случая В-1, псевдополиномиальный алгоритм (0(п2 YlPj) операций) решения частного случая задачи, когда dmax — dmin ^ Ртгт псевдополиномиальный Алгоритм В-1 canonical решения канонических DL примеров;

2. Доказано, что частный случай В-1 задачи 1 11 Yl^j является NP-трудным в обычйом смысле. Доказательство проведено сведением известной задачи Разбиение к частному случаю В-1;

3. Показано, что известные алгоритмы [107, 108,- 22, 50] решения задачи 1 |( Для которых не получена оценка трудоемкости, имеют экспоненциальную трудоемкость для частного случая BF и канонических DL примеров; х

4. Предложен Гибридный алгоритм решения задачи 1 11 основанный на метаэвристическом алгоритме "муравьиные колонии "и точном Алгоритме А. По результатам экспериментов, Гибридный алгоритм "эффективнее" алгоритма "муравьиные колонии" на трех рассмотренных классах примеров;

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

6. Проведен анализ известных нижних оценок для задачи построения расписания проекта с учетом ограничения на ресурсы (RCPSP) и предложена новая нижняя оценка. Было показано, что известные оценки (LBq, LBi, LBS) пе эффективны, либо их (LBLq,LBm) нахождение является в общем случае NP-трудной задачей;

7. Выдвинута гипотеза, что значения целевой функции для задачи RCPSP на быстродействие с прерываниями обслуживания требований и без прерываний отличаются не более чем в 2 раза. Приводятся псевдодоказательство гипотезы, а так же рассуждения о ее практическом применении;

8. Приводятся некоторые оценки значения целевой функции для частного случая задачи RCPSP с одним кумулятивным ресурсом и пустым множеством отношений предшествования;

9. Показано, что любой пример задачи RCPSP можно преобразовать в аналогичный пример, граф отношений предшествования которого будет планарным, причем "мощность" графа не увеличится;

10. Найдены некоторые общие свойства задач теории расписаний с ограничениями предшествования;

11. Некоторые полученные результаты были доведены до практической реализации в программном продукте 1С:УСО и получили хорошую экспериментальную оценку.

169 — i

1. Беллман Р. Динамическое программирование М.: ИЛ, 1960. - 400 с.

2. Бурдюк В.Я., Шкурба В.В. Теория расписаний. Задачи и методы решений // Кибернетика 1971. - № 1. - С. 89-102.

3. Бурков В.Н., Ловецкий С.Е. Методы решения экстремальных комбинаторных задач (обзор) // Известия АН СССР, Техническая кибернетика. 1968. - № 4. - С. 82-93.

4. Бурков В.Н., Ловецкий С.Е. Методы решения экстремальных задач комбинаторного типа (обзор) // Автоматика и телемеханика. 1968. -№11.-С. 68-93.5. под редакцией Буркова В.Н. Математические основы управления проектами М:Высшая школа, 2005, - 432 с.

5. Гафаров Е.Р. Гибридный алгоритм решения задачи минимизации суммарного запаздывания для одного прибора // Информационные технологии, 2007, №1 - С. 30-37.

6. Гафаров Е.Р., Лазарев А.А. Доказательство NP-трудности частного случая задачи минимизация суммарного запаздывания для одного прибора // Известия АН: Теория и системы управления. 2006.№.3. С. 120-128

7. Гафаров Е.Р. Алгоритмы решения проблемы 1 || Х^Т,- и чётно-нечётного разбиения // Материалы XLIII Международной научной студенческой конференции «Студент и научно-технический прогресс»: Математика. Новосиб. гос. ун-т. Новосибирск, 2005. - С. 201-202

8. Гафаров Е.Р. Гибридный алгоритм решения проблемы 1 11

9. Матеррталы XLIV Международной научной студенческой конференции «Студент и научно-технический прогресс»: Математика. Новосиб. гос. ун-т. Новосибирск, 2006. - С. 190-191

10. Гафаров Е.Р. Задачи теории расписаний. Алгоритмы и применение. // Труды 49 научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук»: Управление и прикладная математика. Москва-Долгопрудный, 2006. - С. 82-83.

11. Гафаров Е.Р. Алгоритмы решения NP-трудных задач теории расписаний и разбиения // Труды всероссийской конференции студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования» Москва, 2006. - С. 120-121.

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

13. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов М:Наука, 1990, - 384 с.

14. Карп P.M. Сводимость комбинаторных проблем // Кибернетический сборник. М.: Мир. - 1972. - Вып. 12. - С. 16-38.

15. Кварацхелия А.Г. Методы решения задачи минимизации суммарного запаздывания для одного прибора и задачи Разбиения: Дис. канд. физ.-мат. наук. Москва, 2007. - 126 с.

16. Ковалев М.Я. Интервальные е приближенные алгоритмы решения дискретных экстремальных задач: Дис. канд. физ.-мат. наук. - Минск, 1986. - 110 с.

17. Корбутп А.А., Сигал И.Х., Финкельштейн Ю.Ю. Методы ветвей и границ. Обзор теорий, алгоритмов, программ и приложений // Operations Forsch. Statist., Ser. Optimiz. — 1977. — V.8, N.2. — P. 253—280.

18. Корбут А.А., Сигал И.Х., Финкельштейн Ю.Ю. Гибридные методы в дискретном программировании j j Изв. АН СССР. Техн. кибернет.- 1988. № 1. - С. 65-77.

19. Корбут А.А., Финкельштейн Ю.Ю. Приближенные методы дискретного программирования // Изв. АН СССР. Техн. кибернет. — 1983. № 1. - С. 165-176.

20. Лазарев А.А. Алгоритмы в теории расписаний, основанные на необходимых условиях оптимальности // Исследования по прикладной математике. Казань: Изд-во Казан, гос. ун-та, 1984. -Вып. 10. - С. 102-110.

21. Лазарев А.А. Алгоритмы декомпозиционного типа решения задачи минимизации суммарного запаздывания // Исследования по прикладной математике. Казань: Изд-во Казан, гос. ун-та, 1990. -Вып. 17. - С. 71-78.

22. Лазарев А.А. Эффективные алгоритмы решения некоторых задач теории расписаний для одного прибора с директивными сроками обслуживания требований: Дис. канд. физ.-мат. наук. Казань, 1989.- 108 с.

23. Лазарев А.А., Гафаров Е.Р. Теория расписаний. Минимизациясуммарного запаздывания для одного прибора. М.: Вычислительныйцентр им. А.А. Дороницына РАН, 2006. 134 с. i

24. Лазарев А.А., Гафаров Е.Р. Теория расписаний. Исследование задач с отношениями предшествования и ресурсными ограничениями. М.: Вычислительный центр им. А.А. Дороницына РАН, 2007. - 80 с.

25. Лазарев А.А. Графический подход к решению задач комбинаторной оптимизации // Атоматика и телемеханика, 2007, №4 - С. 13-23.

26. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985, - 512 с.

27. Посыпкин М.А., Сигал И.Х., Галимьянова Н.Н. Алгоритмы параллельных вычислений для решения некоторых классов задач дискретной оптимизации. М.: Вычислительный центр им. А.А. Дороницина РАН, 2005. - 44 с.

28. Современное состояние теории исследования операций Под ред. Н.Н.Моисеева. — М.: Наука, 1979. — 464 с.

29. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: теория и вычислительные алгоритмы. М.: Физматлит, 2002. - 240 с.

30. Танаев B.C., Шкурба В.В. Введение в теорию расписаний. М.: Наука, 1975.

31. Танаев B.C., Гордон B.C., Шафранский Я.М. Теория расписаний. Одностадийные системы. М.: Наука. Гл. ред. физ.-мат. лит., 1984. -384 с.

32. Танаев B.C., Сотпсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. М.: Наука. Гл. ред. физ.-мат. лит., 1989. - 328 с.

33. Танаев B.C., Ковалев М.Я., Шафранский Я.М. Теория расписаний. Групповые технологии. Минск: Институт технической кибернетики НАН Беларуси, 1998. - 290 с.

34. Финкелъштейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования М.: Наука, 1976.

35. Хачатуров В.Р., Веселовский В.Е., Злотов А.В. и др. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности М.: Наука. - 2000.

36. Шкурба В.В., Подчасова Т.П., Пшичук А.Н., Тур Л.П. Задачи календарного планирования и методы их решения Киев: Наукова думка, 1966. - 154 с.

37. Alidaee В., Gopalan S. A note of the equivalence of two heuristics to minimize total tardiness // European Journal of Operation Research. -1997. V.96. - P. 514-517.

38. Baev I.D., Meleis W.M., Eichenberger A. Lower bounds on Precedence-Constrained Scheduling for Parallel Processors //IEEE, 2000.

39. Baker K.R. Introduction to sequencing and scheduling. Wiley, New York. - 1974.

40. Baker K.R., Bertrand W.M. A dynamic priority rule for scheduling against due dates // Journal of Operation Management. 1982. - V.3. - P. 37-42.

41. Baker K.R., Schrage L. Finding am optimal sequence by dynamic programming: an extension to precedence-related tasks // Operations Research. 1978. - V. 26. - P. 111-120.

42. A. Bauer, B. Bullnheimer, R.F.Hartl, C. Strauss. Minimizing Total Tardiness on a Single Machine Using Ant Colony Optimization. // Proceedings of the 1999 Congress on Evolutionary Computation (CEC99). Washington D.C, 1999. - P. 1445-1450.

43. Blazewicz J., Ecker K., Pesch E., Schmidt G., Weglarz J. Scheduling Computer and Manufactoring Processes. Springer Berlin. - 1996.

44. Brucker P. Scheduling Algorithms. Springer-Verlag, 2001. - 365 p.

45. Brucker P., Lenstra J.K., Rinnoy Kan A.N.G. Complexity of machine scheduling problems // Math. Cent. Afd. Math Beslisk. Amsterdam, 1975. - BW 43. - 29 pp.

46. Brucker P., Knust S. Complex scheduling Springer-Verlag Berlin, Heidelberg, Germany, 2006

47. Burkov V.N. Problems of optimum distribution of resources // Control and cibernetics, 1972, vol.1, №1/2 - P. 27-41.

48. Carroll D. С. Heuristic sequencing of single and multiple components PhD Thesis: Massachusets Institute of Technology. 1965.

49. Chang S., Lu Q., Tang G., Yu W. On decomposition of the total tardiness problem, j j Oper. Res. Lett. 1995. - V.17. - P. 221-229.

50. Cheng T.C.-E., Lazarev A.A., Gafarov E.R. A Hybrid Algorithm for the Single Machine Total Tardiness Problem, // Computers & Operations Research. In Print.

51. Conway R. W., Maxwell W.L., Miller L. W. Theory of Scheduling -Addison-Wesley, Reading, MA. 1967.

52. Delia Croce F., Grosso A., Paschos V. Lower bounds on the approximation ratios of leading heuristics for the single-machine total tardiness problem j j Journal of Scheduling. 2004. - V.7. - P. 85-91.

53. Demeulemeester E.L., Herroelen W.S. Experimental evaluation of state-of-the-art heurisitcs for the resource-constrained project scheduling problem // EJOR, 1996, V90 - P. 334-348.

54. Du J., Leung J. Y.-T. Minimizing total tardiness on one processor is NP-hard // Math. Operation Research. 1990. - V.15. - P. 483-495.

55. Elmaghraby S.E. The one machine scheduling ptoblem with delay costs 11 Journal of Industrial Engineering. 1968. - V.19. - P. 105-108.

56. Emmons H. One machine sequencing to minimizing certain function of job tardiness // Operations Research. 1969. - V.17. - P. 701-715.

57. Fisher M.L. A dual problem for the one machine scheduling problem // Mathematics Programming. 1976. - V.ll. - P. 229-251.

58. Graham R.L. Bounds for certain multiprocessing anomalies //SIAM J. Appl.Math., 1966, -VI7 P. 263-269.

59. Graham R.L., Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G Optimization and approximation in detcrmenistic sequencing and scheduling: a servey. // Ann. Descrete Optimization. 1979. - V.2. - P. 287-325.

60. Hartmann S., Kolish R. Experimental evaluation of state-of-the-art heurisitcs for the resource-constrained project scheduling problem // EJOR, 2000, V127 - P. 394-407.

61. Ни Т.О. Parallel sequencing and assembly line problems //Operation Research, 1961, -V9 P. 841-848.

62. Jackson J.R. Scheduling a production line to minimize maximum tardiness // Res. Report 43 Sci. Res.Project. UCLA, 1955.

63. Johnson S.M. Optimal two- and three-stage production schedules with setup times included. // Naval Research Logistics Quarterly. 1954. -V.l. - P. 61-68.

64. Held M., Karp R.M. A dynamic programming approach to sequencing problems // SIAM Journal. 1962. - V.10. - P. 196-210.

65. Holsenback J.E., Russell R.M. A heuristic algorithm for sequencing on one machine to minimize total tardiness // Journal of Operation Research Society. 1992. - V.43. - P. 53-62.

66. Kao Е.Р. C., Queyranne M. On dynamic programming methods for assembly line balancing // Operations Research. 1982. - V.30. - P. 375-390.

67. Keller H., Pferschy U., Pisinger D. Knapsack problems // Springer, 2004, 546 p.

68. Kolish R., Padman R. An Integrated Survey of Project Scheduling // 1997

69. Kolish R., Hartmann S. PSPLIB A project scheduling problem library // Manuscripte aus den Intsituten fur Betriebswirtschaftslehre, 1996, No.396, Kiel, Germany

70. Kolish R., Hartmann S. Heuristics Algorithms for Solving the Resource-Constrainde Project Scheduling Problem: Classification and Computational Analysis // Manuscripte aus den Intsituten fur Betriebswirtschaftslehre, 1998, No.469, Kiel, Germany.

71. Koulamas C.P. The total tardiness problem: Review and extensions // Operations Research. 1994. - V.42. - P. 1025-1041.

72. Lazarev A., Kvaratskhelia A., Tchernykh A. Solution algorithms for the total tardiness scheduling problem on a single machine. // Workshop Proceedings of the ENC'04 Mexican International Conference in Computer Science. Mexico, 2004. - P. 474-480.

73. Lazarev A., Kvaratskhelia A., Gafarov E. Algorithms for solving problems 1 || Y^Tj and Even-Odd Partition. //In Book of Abstracts of XVIII International Conference «European Chapters on Combinatorial Optimization». Minsk, 26-28.V.2005. - P. 32-33.

74. Lazarev A. A., Gafarov E.R. Graphical approach for solving combinatorial problems // Abstract Guide of International Conference on Operation Research OR 2006, Karlsruhe 6.09-8.09, Germany, P.59

75. Lazarev A.A., Gafarov E.R. Algorithms for the single machine total tardiness problem // Abstract Guide of International Conference on Operation Research OR 2006, Karlsruhe 6.09-8.09, Germany, P.285

76. Lazarev A.A., Gafarov E.R. Estimation of lower bounds for resources constrained project scheduling problem // Proceedings of V Moscow International Conference on Operation Research (ORM2007), Moscow, 2007, P.236-238

77. Lawler E.L. On scheduling problems with deferral costs // Management Science. 1964. - V.ll- P. 280-288.

78. Lawler E.L. A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness 11 Ann. Discrete Math. 1977. - V.l. - P. 331-342.

79. Lawler E.L. A fully polynomial approximation scheme for the total tardiness problem // Oper. Res. Lett. 1982. - V.l. - P. 207-208.

80. Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G., Shmoys D.B. Sequencing and Schedling: Algorithms and Complexity // Elsevier Science Publishers B.V. 1993. - V.4. - P. 445-520.

81. Lenstra J.K., A.H.G. Rinnoy Kan Complexity of scheduling under precedence constraints //Operation Research, 1978, -V26 P. 22-35.

82. Lenstra J.K., Rinnooy Kan A.H.G., Brucker P. Complexity of machine scheduling problems // European Journal of Operational Research. -1980. V.4. - P. 270-275.

83. McNaughton R. Scheduling with deadlines and loss functions // Management Science. 1959. - V.6. - P. 1-12.

84. Merkle D., Middendorf M., Schmeck H. Ant Colony Optimization for Resource-Constrainted Project Scheduling. // IEEE Transactions on Evolutionary Computation, 2002 vol.6, №4 - P. 333-346.

85. D. Merkle, M. Middendorf. An Ant Algorithm with a New Pheromone Evaluation Rule for Total Tardiness Problem. // EvoWorkshops 2000. -Springer-Verlag, 2000. P. 287-296.

86. Mingozzi A., Maniezzo V., Ricciardelli S., Bianco L. An exact alforithm for project scheduling with recource constraints based on new mathematical formulation // Management Science, 1998, V44 - P. 714-729.

87. Morton Т.Е., Rachamadugu R.M., Vepsalainen A. Accurate myopic heuristics for tardiness scheduling // GSIA Working Paper 36-83-84, Carnegie Mellon University. 1984.

88. Panwalkar S.S., Smith M.L., Koulamas C.P. A heuristic for the single machine tardiness problem // European Journal of Operation Research.- 1993. V.70. - p. 304-310.

89. Picard J., Queyranne M. The time-dependent travelling salesman problem and its application to the tardiness problem in one machine // Operations Research. 1978. - V.26. - P. 86-110.

90. Pinedo M. Scheduling: Theory, Algorithms, and Systems. Prentice-Hall? Englewood Cliffs, New Jersey. - 1995.

91. Potts C.N., Van Wassenhove L.N. A decomposition algorithm for the single machine total tardiness problem // Oper. Res. Lett. 1982. - V.5.- P. 177-182.

92. Potts C.N., Van Wassenhove L.N. A branch-and-bound algorithm for the weighted tardiness problem // Operations Research. 1985. - V.33. - P. 363-377.

93. Potts C.N., Van Wassenhove L.N. Dynamic programming and decomposition approaches for the single machine total tardiness problem European Journal of Operational Research. 1987. - V.32. - P. 405-414.

94. Potts C.N., Van Wassenhove L.N. Single machine tardiness sequencing heuristics // HE Transactions. 1991. - V.23. - P. 93-108.

95. Rinnooy Kan A.H.G., Lageweg B.J., Lenstra J.K. Minimizing total cost in one machine scheduling // Operations Research. 1975. - V.23. - P. 908-927.

96. Rykov I. Approximate solving of RCPSP // Abstract Guide of OR 2006, Karlsruhe 6.09-8.09, Germany, P.226

97. Schild L., Fredman K.R. Scheduling tasks with linear loss function // Management Science. 1961. - V.7. - P. 280-285.

98. Sen Т., Austin L.M., Ghandforoush P. An algorithm for the single machine sequencing problem to minimize total tardiness // HE Transactions.- 1983. -„V.15. P. 363-366.

99. Sen Т., Borah B.N. On the single machine sheduling problem with tardiness penalties // Journal of Operational Research Society. 1991. - V.42.- P. 695-702.

100. Sen Т., Sulek J.M., Dileepan P. Static scheduling research to minimize weighted and unweighted tardiness: A state-of-the-art survey. // International Jornal of Production Economics. 2003. - V.83. - P. 1-12.

101. Schrage L., Baker K.R. Dynamic programming solution of sequencing problems with precedence constraints // Operations Research. 1978. -V.26. - P. 444-449.

102. Shwimer J. On the n-job one machine sequence-independent scheduling problem with tardiness penalties // Management Science. 1972. - V.18.- p. 301-313.

103. Smith W.E. Various optimizers for single stage production // Naval Research Logistics Quarterly. 1956. - V.3. - R 59-66.

104. Srinivasan V. A hybrid algorithm for the one machine sequencing problem to minimize total tardiness // Naval Research Logistics Quaterly. 1971.- V.18. P. 317-327.

105. Szwarc W. Single machine total tardiness problem revised // Creative and Innovate Approaches to the Science of Management, Quorum Books.- 1993. R 407-419.

106. Szwarc W., Delia Croce F., Grosso A. Solution of the single machine total tardiness problem // Journal of Scheduling. 1999. - V.2. - P. 55-71.

107. Szwarc W., Grosso A., Delia Croce F. Algorithmic paradoxes of the single machine total tardiness problem // Journal of Scheduling. 2001. - V.4.- P. 93-104.

108. Szwarc W., Mikhopadhyay S. Decomposition of the single machine total tardiness problem //Орет. Res. Lett. 1996. - V.19. - P. 243-250.

109. Ullman J.D. Complexity of sequencing problems //Coffman, 1976, P. 139-164. ,