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

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

Лазарев Александр Алексеевич

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

01 01 09 — дискретная математика и математическая кибернетика

Автореферат

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

ииУ158811

Москва - 2007

003158811

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

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

Официальные оппоненты доктор физико-математических

наук, профессор Н Н Кузюрин,

доктор технических

наук, профессор И X Сигал,

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

Ведущая организация Институт проблем управления

им В А Трапезникова РАН

Защита диссертации состоится "1 " ноября 2007 г в 13 00 часов на заседании диссертационного совета Д 002 017 02 при Вычислительном Центре имени А А Дородницына Российской академии наук (119333, г Москва, ул Вавилова, 40, конф зал)

С диссертацией можно ознакомиться в библиотеке ВЦ РАН

Автореферат разослан "28" сентября 2007 г

Ученый секретарь

диссертационного совета,

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

в в Рязанов

Общая характеристика работы Актуальность темы

Диссертационная работа посвящена исследованию iVP-трудных задач теории расписаний для одного и нескольких приборов, а также задач РАЗБИЕНИЕ и РАНЦА Важным является разработка новых математических методов и эффективных алгоритмов решения этих задач

Направление в науке, получившее название "теория расписаний", берет свое начало с известной работы Генри Гантта 1903 г (Gantt Н L 1), предложившего то, что сегодня называют диаграммами Гантта, которые встречаются во многих работах по теории расписаний, в том числе и в данной работе С 50-х годов 20-го века началось активное теоретическое исследование задач теории расписаний, что было обусловлено возрастающими запросами промышленности и военной сферы

Рассмотрим постановку задачи теории расписаний Множество требований N = {1,2, , п} должно быть обслужено без прерываний на одном или нескольких приборах Мг,г = 1, , т, которые могут обслуживать не более одного требования в каждый момент времени Время обслуживания требования j £ N на приборе Мг обозначается как рп,рзг > О Момент, когда требование j становится доступным для обслуживания, задается временем поступления г3 Требование j может иметь директивный срок d3 (время, до которого желательно завершить обслуживание требования), а также вес w} (значимость, важность требования) Между требованиями могут быть заданы отношения предшествования в виде ациклического ориентированного графа G Момент окончания обслуживания требования j при расписании ж будем обозначать через С3(ж) Определим L3(ж) = С3(-к) — d3 как временное смещение требования j при расписании ж, а Т3(ж) = max{0,Ь3{ж)} — как его запаздывание Uj(ж) обозначает запаздывает ли требование j при расписании ж или нет 113(ж) = 1, если j запаздывает (С3(ж) > d3), иначе из(ж) = 0 (требование j обслуживается вовремя) Классическими критериями в задачах теории расписаний являются Стах — минимизация максимального времени окончания обслуживания (задача на быстродействие), Lmax — минимизация максимального временного смещения, — минимизация суммарного запаздывания, ~ минимизация взвешенного числа

1 Gantt HL ASME Transactions, 1903, 24,-Р 1322-1336

запаздывающих требований

Через щ будем обозначать перестановку (расписание) из элементов множества N, обслуживаемых на приборе Мг,г = 1, , m, множество требований в расписании щ обозначим {щ} С N, а через п = (J™ i 7гг, {""a} flí71"/?} = 0) если а ф ß, расписание для всего множества требований N = {7г} Рассматриваются только допустимые расписания, удовлетворяющие отношениям предшествования Для любого ациклического графа G множество допустимых расписаний не пусто Момент окончания обслуживания требования j на приборе Мг при расписании ж определяется как

С,(7г) = max{r,,maxCfc(7r), max С\(иг)} + р]г,

где Nj — множество требований предшествующих требованию j, согласно графу G, и (к —» требования, согласно расписанию щ на приборе Мг, предшествующих обслуживанию требования j € {щ}

В работе Грэхэма и др 2 была введена классификация для задач теории расписаний По данной классификации каждой задаче соответствует а I ß I 7, где а обозначает число и тип доступных приборов, ß описывает дополнительные ограничения задачи (например, обозначение г3 указывает на наличие неодинаковых времен поступления требований, ргес обозначает наличие отношений предшествования в обслуживании требований), 7 определяет критерий задачи

Подавляющее большинство из исследованных задач теории расписаний являются TVP-трудными3 Для решения таких задач существуют три основных класса алгоритмов эвристические, приближенные и алгоритмы сокращенного перебора Эвристические алгоритмы позволяют получить "хорошее" решение за приемлемое время, однако они не могут дать оценок качества полученного решения Приближенные алгоритмы4

2 Graham R L , Lawler Е L , Lenstra J К, Раппооу Кап A H G Optimization and approximation m deterministic sequencing and scheduling a survey// Ann Discrete Math - 1979 - V 5 - P 287 - 326

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

Tanate ВС, Гордон ВС, Шафранский ЯМ Теория расписаний Одностадийные системы// M Наука Гл ред физ -мат лит, 1989 - 384 с

Peter Bracker, Sigrid Knust Complex Scheduling// Springer, 2006,- 284 p

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

гарантируют оценку качества полученного решения (погрешность), которое будет найдено за полиномиальное (от п) время Приближенные алгоритмы для некоторых задач теории расписаний разработаны, например, в работах Ковалева5, Севастьянова6 Алгоритмы сокращенного перебора используются для оптимального решения УУ.Р-трудной задачи Наиболее распространенным подклассом алгоритмов сокращенного перебора являются алгоритмы, построенные по методам ветвей и границ (branch and bounds), программирования в ограничениях (ПвО, в англоязычной литературе - Constraint Programming), отсечения и ветвления (brunch and cuts) В каждом из этих алгоритмов происходит "разбиение" примера (с конкретными значениями параметров приборов, требований и графом предшествования) задачи на подпримеры и существенным является нахождение эффективных нижних оценок решения подпримеров и как следствие происходит сокращение дерева поиска

Цель работы

Целью работы является разработка новых алгоритмов, как приближенных, так и точных алгоритмов сокращенного перебора, для решения ./VP-трудных задач теории расписаний как для одного, так и для нескольких приборов 1 | г3 | Lmax,Cmax, 1 | г, | j2wjuj> 1 ii y,tv ipiryq} i prec,r3 | {¿шах, Cmax}, а также алгоритмов решения классических задач РАЗБИЕНИЯ и РАНЦА Кроме того, важным является введение метрики для задач теории расписаний минимизации максимального временного смещения

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

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

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

6Севастьянов СБ Геометрические методы и эффективные алгоритмы в теории расписаний// Дис док физ -мат наук - Новосибирск 2000 - 280 с

Научная новизна

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

Предложена новая схема нахождения приближенного решения задач теории расписаний, состоящая из двух этапов На первом этапе, решая задачу линейного программирования, находится такое изменение исходных параметров примера А & N,1 £ М), чтобы полученный пример В с параметрами требований (г^е N,1 е М) принадлежал заданному полиномиально/псевдополиномиально разрешимому классу примеров исходной ЛГР-трудной задачи и был на минимальном расстоянии от примера А в метрике р На втором этапе для решения примера В используется уже известный для данного класса примеров полиномиальный/псевдополиномиальный алгоритм, а затем найденную им оптимальную перестановку требований применим к примеру А Абсолютная погрешность такого решения не будет превосходить расстояния р(А, В) между примерами Данный подход позволяет находить эффективные нижние оценки целевой функции, которые можно использовать в методах сокращенного перебора для оптимального решения задачи

Поставлена и решена задача, в некотором смысле "двойственная" к задаче 1 | г, | /тах при произвольных неубывающих функциях штрафа, трудоемкость алгоритма 0(п2) операций Решение данной задачи является оценкой снизу для исходной АгР-трудной задачи 1 \ г3 \ /тах и может быть использована в алгоритмах сокращенного перебора

Для Л^Р-трудной задачи 1 11 когда параметры требований удо-

влетворяют ограничениям рг>р2> > рп, ^ < ¿2 < < <1П, построен псевдополиномиальный алгоритм трудоемкости 0(п2 ^Ро) операций Предложена графическая реализация метода динамического программирования, на основе которой построены алгоритмы решения задач РАЗБИЕНИЯ и РАНЦА, показавшие лучшую экспериментальную эффективность по сравнению с представленными в научной литературе Алгоритмы позволяют решать примеры с нецелочисленными и отрицательными значениями параметров

б

Теоретическая и практическая значимость

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

Апробация результатов

Результаты диссертации докладывались и обсуждались на 4-ом международном конгрессе по промышленной и прикладной математике (Эдинбург, Шотландия, 1999 г), международных конференциях по оптимизации (Намур, Бельгия, 1998 г, Монтпелье, Франция, 2000 г), международных семинарах "Дискретная математика и ее приложения" (Москва, МГУ, 2001, 2004, 2007 гг), Российской конференции "Дискретный анализ и исследование операций" (Новосибирск, 2002, 2004 гг), международных семинарах по методам и алгоритмам для задач календарного планирования и теории расписаний МАРЭР (Сиена, Италия, 2003, 2005 гг, Стамбул, Турция, 2007 г), 3-ей международной конференции "Математические методы и компьютеры в экономике" (Пенза, 1998 г), международной школе-семинаре "Методы оптимизации и их применение" ( Байкал 1998 г), научно-исследовательской конференции "Практика использования мини и микро ЭВМ в ГАП механической обработки" (Казань, 1988 г), симпозиуме "Программное обеспечение решения задач оптимального планирования" (Нарва, Эстония, 1988 г), конференции "Проблемы теоретической кибернетики" (Иркутск, 1985 г, Казань 2002 г), международной конференции по исследованию операций (Карлсруэ, Германия, 2006 г), международной конференции по комбинаторной оптимизации ЕССО XVIII (Минск, Беларусь, 2005 г), международной конференции Е1\ГС'04 (Колима, Мексика, 2004 г), 1РАС симпозиуме по проблемам контроля в производстве ЩСОМ'2006 (Сент-Этьен, Франция, 2006 г), международном семинаре по сложности многомерных задач (Гон-Конг, Китай, 1999 г), VI Международной конференции «Дискретные модели в теории управляющих систем» (Москва, МГУ, 2004 г), 9-ой Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 1999 г), международной конференции по теории распи-

саний М18ТА'07 (Париж, Франция, 2007 г), семинарах кафедр прикладной математики и экономической кибернетики Казанского университета (1980-2002 гг), семинарах математического департамента СЮЕЭЕ (Энсе-нада, Мексика, 2004 г), семинарах профессора П Брукера (Оснабрюк-ский университет, Германия, 2002, 2003 гг), семинарах профессора Ф Баптиста (Эколь Политекник, Полиазье, Франция, 2007 г), семинаре отдела "Математических проблем распознавания и методов комбинаторного анализа" Вычислительного центра им А А Дородницына Российской академии наук (Москва, 2007 г)

Публикации

Основные результаты диссертации опубликованы в 56 работах, в том числе 8 в центральной российской печати (из списка ВАКа), четырех книгах, а также в материалах и тезисах международных, всесоюзных и всероссийских конференций Список публикаций автора по теме диссертации приведен в конце автореферата

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

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

Благодарности

Считаю своим долгом выразить благодарность В С Танаеву , Е Г Ла-

заревой, Ю И Журавлеву, В К Леонтьеву, И X Сигалу, Ю А Флерову, Л С Иртышевой, В H Буркову, Д А Новикову, С В Севастьянову, M Я Ковалеву, Я M Шафранскому, Ю H Сотскову, H H Кузюрину, В В Шкурбе, А А Сапоженко, M H Вялому, С П Тарасову, Р Р Сады-кову, А Г Кварацхелия, Р Р Сираеву, Е Р Гафарову, С А Скиндереву, А H Черных, Я И Заботину, О H Шульгиной, А Ф Кадомцевой, Р Ф Хабибуллину, А А Корбуту, П Брукеру (Германия), Ф Баптисте (Франция), В Шварцу (США) за помощь в работе и обсуждение полученных результатов

Работа выполнена при финансовой поддержке фондов РФФИ и НШ (Россия), DAAD (Германия), CNRS (Франция), NSC (США)

Содержание работы

Введение содержит обоснование актуальности темы диссертации и характеристику области исследований Дается обзор научных результатов исследований по тематике диссертации, приводятся основные цели и задачи исследований, отражаются методы решения задач, основные результаты, отмечается их научная новизна и практическая ценность Приводятся сведения об апробации результатов диссертации и публикациях В разделе 1 1 первой главы рассматриваются постановки задач минимизации максимального временного смещения (1/тах), дан краткий исторический обзор задач, приведены основные результаты, существующие в литературе В разделе 1 2 вводятся обозначения и определения, которые используются далее в работе В разделе 1 3 формулируется и доказывается теорема об абсолютной погрешности [15]

Теорема 1 Пусть А = {С?, 3 еЩиВ = {О, (г,в.р^) е

Л^} (с идентичным графом предшествования О) - два примера ИР-трудной задачи Р | ргес, г3 \ Ьтзх, тогда

рг(А, В) = та\jeNirf ~ ^} - гшп^л^г/ - г^}, ра{А, В) = тах,бЛг{<^ - } - - },

РР(Л,В) = ^ем \pf~pfl

Мы можем использовать оптимальное расписание примера В для решения исходного примера А Если пример В принадлежит некоторому полиномиально/псевдополиномиально разрешимому подмножеству примеров, то необходимо найти такой пример из этого подмножества, до которого расстояние р(А, В) было бы минимальным Искомое оптимальное значение £тах будет принадлежать интервалу е [¿тахС71"8) ~

(1)

р(А, В) = рг(А, В) + рл{А, В) + рр(А, В)

(2)

р(А,В),Ь^( ттв)}

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

XR + YP + ZD < Н, (3)

где R = (гь ,rn)T, Р = (pi, ,рп)т, D = (di, ,dn)T, и X, Y, Z - матрицы размерности к х n, a H = (h\, ,hk)T - ^-мерный вектор (верхний индекс т обозначает операцию транспонирования) Затем в этом классе примеров (3) находим пример В с минимальным расстоянием р(А, В) до исходного примера А, решая следующую задачу

(xd - yd + хт - ут) + Y,jeN rf —> mm yd<df-df<xd, 3 = 1, ,n, < yr <rf -rf <xr, j = l, ,n, -xp3 < pf - pf < X?, 3 = 1, , n, 0<x^, 3 = 1, ,n, XRB + YPB + ZDB < H

Задача линейного программирования (4) с 3n + 4 + n переменными (rf,pf, df, з = 1, , n, и xd, yd, xr, ут, и j = 1, , n) и 7n + к неравенствами иногда может быть решена за полиномиальное (от п) операций, учитывая специфику ограничений задачи (4) Для всех известных полиномиально/псевдополиномиально разрешимых случаев задачи Р | ргес, г, | Lmax количество ограничений к = 0(п)

Рассмотрим совокупность примеров задачи P\prec,rt\Lmax с количеством требований п, количеством приборов m и ориентированным графом предшествования G Данная совокупность примеров образует 3п-мерное линейное пространство (3п параметров rj,pj,dj,3 = 1,n) Два примера А = {G, (rf,pf,df)\3 € N} и В = {G, (rf.pf.df) | j € N} будем называть эквивалентными, если существуют константы dur, что df = df + d,rf = rf + r, pf = pf Уз € N Полученное семейство классов эквивалентности является (3п — 2)-мерным линейным пространством, которое обозначим через Сп Будем говорить, что пример А принадлежит классу Сп, если выполняется условие ri = <¿1 = 0 Несложно показать, что у эквивалентных примеров совпадают множества оптимальных расписаний На пространстве классов эквивалентности приме-

(4)

ров рассмотрим следующий функционал

VA е Сп, ip(A) = maxrf - ттИ + тах/ - mincí? + V^ \т£\ > О jgíV 3 3eN 3 jeN 3 j€N 3 ¿-y'-^1-

Данный функционал удовлетворяет трем свойствам нормы

ц>(А) = 0 А = 0, <р(аА) = а<р(А), <р(А + В) < <р(А) + <р(В)

Таким образом, Сп является (Зп — 2)-мерным линейным нормированным пространством с нормой ||Л|| = <р[А)

Теорема 2 [15] Функция р(А, В) = ||j4 — В\\ удовлетворяет свойствам нормированной метрики в (Зп —2)-мерном линейном пространстве параметров требований dj)\j G N}

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

Теорема 3 Пусть А = {G, (г/, pf, df)\j eN}uB = {G, (rf, pf, df) | j e N} (с идентичным графом предшествования G) два примера, тогда для любого приближенного расписания 7Т верно

О < LtJ?г) - LtJ^) < + Р{А, В),

где 5В{тг) = L^M ~ LLAkB)

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

Во второй главе представлены новые полиномиально и псевдополи-номиально разрешимые случаи NP-трудной в сильном смысле задачи

\\г3\Ьтах В разделе 2 1 рассмотрен случай [11, 14, 31], когда параметры требований удовлетворяют следующим ограничениям

I d\ - п - pi > >dn-rn-pn Данным ограничениям соответствует случай, когда d} = r3 + р3 + z, j = 1, ,п, где z - константа, те когда все требования имеют одинаковый запас времени до своего директивного срока Алгоритмом [14] за 0(п3 logn) операций может быть найдено Парето-оптимальное множество (по критериям Lmax и Стах), состоящее не более чем из п расписаний, решение общей двукритериальной задачи 1\г3\Ьтах, Стах

Теорема 4 [30, 31] Для любого примера А задачи 1 | r3 | Lmax, не принадлежащего классу (5), и для любого примера С, наследующего длительности обслуживания примера А и принадлежащего данному классу, справедлива оценка расстояния между А и С

р(А, С) > pL(A) = max mm {df-df, (df-rf-pf) - (df-rf-pf)} (6)

Оценка (6) достигается на некотором примере С, который может быть найден за время O(nlogn)

Кроме того, был рассмотрен полиномиально разрешимый случай Хо-гевена7 задачи l\r3\Lmax ms,xkeN{dk - Гк—pk} < d3 — rv Vj € N Оптимальное расписание находится за 0(п2 logn) операций

Теорема 5 Для любого примера А задачи l|rj¡Lmax, не принадлежащего классу Хогевена, и для любого примера С, наследующего длительности обслуживания примера А и принадлежащего классу Хогевена, справедлива оценка расстояния между А и С

р(А, С) > рн(А) = max{df - rf - pf - df + rf} (7)

rHoogeveen J A Minimizing maximum promptness and maximum lateness on a single machine// Math Oper Res- 1996-V 21 - P 100-114

Оценка (7) достигается на некотором примере С, который может быть найден за время 0(п)

Для более сложного iVP-трудного подслучая задачи l\r3\Lmax, когда параметры требований удовлетворяют ограничениям

di<d,2< < dn,

П>г2> > r„, (8)

r3,pvd3 eZ+Vj 6 N,

предлагается псевдополиномиальный алгоритм решения [36, 40] трудо-

п

емкости 0(п2Р + npmaxP) операций, где Р = max{rmax, t} + J^Pj ~

j=i

max{rmm,i}, rmax = maxrj, rmm — mmr,, pmax = таxp,, a t- момент

jen jeN j€N

времени, с которого прибор готов начать обслуживать требования множества N

Для получения нижних оценок целевой функции был также использован следующий подход Рассмотрим общую постановку iVP-трудной задачи l\r3\fm&3i

тгеп(N) к=1,п

где fjk{CJk(ir))~ произвольные неубывающие функции штрафа Решим задачу нахождения величины и*

v* = max mm f3k (С3к (тг)) к—1,п тгеЩЮ

Теорема 6 [6, 11] Для NР-трудной задачи l|f"j|/max с произвольными неубывающими функциями штрафа f3{t),Vj £ N, верно и* < р* и величина и* может быть найдена за 0(п2) операций

Третья глава диссертации посвящена алгоритмам оптимального решения задачи 1 | r2 | -Lmax В разделе 3 1 рассмотрены существующие подходы к решению задачи, такие как алгоритм Карлье8 и метод про-

8Carher J The one-machme sequencing problem// European J of Oper Res - 1982 - V 11. N 1 -P 42 - 47

граммирования в ограничениях9 (ПвО) Данный метод близок к методу ветвей и границ Отличие заключается в том, что для сокращения перебора в ПвО используется пропагация ограничений, которая удаляет несовместимые значения из множеств допустимых значений переменных В разделе 3 2 предлагаются два алгоритма оптимального решения задачи 1 | г3 | Lmax Первый алгоритм построен по методу ПвО На каждом шаге алгоритма для исходной задачи решается задача распознавания с помощью метода ПвО, в котором используется предложенное нами правило ветвления, основанное на следующей теореме

Теорема 7 Пусть построено расписание Шраге10 ~ка и требования пронумерованы в том порядке, в котором они упорядочены в тг" Пусть Ъ £ N - наименьший номер, для которого Ьъ(п") = Lmax(7ra), и а £ N - наибольший такой номер, что а < Ъ и

Ca(ir") -Pa - mm rj < Lb(7Ta) - UB, a<j<b

где UВ < UB - верхняя оценка оптимального решения При-

мем S = {а, , ЬУ, тогда

• если не существует такого требования с £ S, что dc > йь, то не существует расписания с Lmax меньшим, чем UВ,

• если с £ S - последнее требование с директивным сроком dc > db, то в любом расписании -к', что Ьтах(тг') < UB, выполняется либо (с —» J)„i, либо (J —¥ с),г<, где J = {с+ 1, , Ь}

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

9Baptiste Ph , Le Раре С , Nuijten W Constraint-based scheduling applying constraint programming to scheduling problems// Kluwer Academic Publishers, 2001 - 198 p

10Schrage, L Solving Resource-Constrained Network Problems by Implicit Enumeration Non-Preemptive Case// Oper Res - 1970 - V 18 - P 263 - 278

В разделе 3 3 приводятся результаты экспериментального сравнения точных алгоритмов решения задачи 1 | г3 | Lmax, предложенных в работе, и подходов, существующих в литературе

В разделе 3 4 рассматривается вариант распознавания задачи 1 | r: \ Lmax Назовем расписание 7г допустимым по отношению к константе L', если Lmax(n) < L' Множество требований S допустимо по отношению к константе I/, если существует допустимое расписание 7г е П(5), и недопустимо, если не существует такого расписания В рассматриваемом варианте задачи требуется определить допустимо ли множество требований N по отношению к заданной константе L' Если N допустимо, то необходимо найти допустимое расписание Если же N недопустимо, то требуется найти как можно меньшее недопустимое подмножество требований из множества N Для данного варианта задачи предлагается алгоритм, который является эвристическим в том смысле, что он находит некоторое недопустимое подмножество требований S С N, не обязательно минимальное, когда множество требование N недопустимо В тоже время, алгоритм точно определяет, допустимо ли множество требование N Правило ветвления алгоритма основано на следующей теореме

Теорема 8 Пусть Iímax(7r<T) > L' и требования пронумерованы в том порядке, в котором они упорядочены в ir", Ъ £ N — наименьший номер, для которого Ьь(-тга) > L', и а £ N ~ наибольший номер, что а < Ь и

СаЬга) - Ра - mm г, < Ьь(7Т°) - L', jes

где S = {а, , 6} Тогда

• если не существует такого требования с £ S, что d,c > db, то множество требований S недопустимо по отношению к L',

• если с £ S - последнее требование с директивным сроком dc > <¿¡,, и существует допустимое расписание гг', то выполняется либо (с —>• J)„i, либо (J с)л>, где J = {с + 1, , Ь}

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

дерева поиска, где не происходит ветвления, согласно теореме 8, мы располагаем подмножеством 5, недопустимым для задачи с текущими параметрами требований Данное подмножество "передается родительскому" узлу дерева поиска Способ построения недопустимого подмножества для узла, имеющего "дочерние" узлы, обоснован в теореме 9

Теорема 9 Пусть при любом допустимом расписании -к' £ П(N) требование с £ N обслуживается до или после всех требований множества J С N, S' С N - недопустимое множество требований, когда (с J),г- a S" С N - недопустимое подмножество, когда (J —> c)w< Тогда

• если с $ S' (с $ S"), то множество S' (S") недопустимо,

• если с £ S' и с £ S", то множество S = JU S'U S" недопустимо

В четвёртой главе диссертации предлагается точный алгоритм решения задачи 1 | г, \ Алгоритм построен по "гибридному" методу11 отсечения и ветвления12, который представлен в разделе 4 1

В последующих разделах задача 1 | г3 | формулируется как

задача целочисленного линейного программирования (ЦЛП) и решается методом отсечения и ветвления Пусть булева переменная х3 принимает значение 1, если требование j £ N обслуживается вовремя и 0 - если требование j £ N запаздывает

Y^Wjil-Xj)—mm (9)

JdN

nD(x), (10)

disjunctive (ж), (11)

a; e {0,1}" (12)

Ограничение disjunctive^) выполняется тогда и только тогда, когда множество требований J = {j х3 = 1} может быть обслужено на одном

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

12 Финкельштейн Ю Ю Метод отсечения и ветвления для решения задач целочисленного линейного программирования//Изв АН СССР Техн кибернет - 1971-N 4 - С 34-38

приборе без прерываний и с соблюдением времен поступления и директивных сроков, (10) — релаксация ограничения disjunctive

В разделе 4 4 рассматриваются различные варианты релаксации (10)

Лемма 1 Пусть для двух требований i,j € N выполняется гг < d3 Если вектор х удовлетворяет ограничению disjunctive, тогда х также удовлетворяет ограничению13

У^ mm[dj - г„ (pi - max{a:fe, Pji})+}xt < d} - r„ (13)

len

где ah = (r, - n)+ и fa = - d3)+

Раздел 4 5 посвящен вопросу проверки на допустимость решения х задачи ЦЛП (9), (13), (12), а также вопросу построения отсечений в случае недопустимости х Алгоритм выполняется для множества требований J = {j х3 = 1}, к в случае его недопустимости находится недопустимое подмножество S С J, для которого строится ограничение

5>,<isi-I (14)

jeS

Следующее утверждение представляет отсечения второго вида

Лемма 2 Пусть заданы такие множество требований D, С N и требование к £ N \ что к может быть обслужено только с момента времени г^, г^ > rk, если все требования из выполняются вовремя Положим также afk = (г^ — г;)+ Тогда вектор х, удовлетворяющий ограничению disjunctive, удовлетворяет неравенству

]Г mm [dj - (pi - max{apfc, fa})+] xt+

ien\q\{k}

(pk - fa)+xk <d3-r%+ (r£ - rfc)(| Q | - E

oefi

для каждого требования j E N \ tt, d3 > rjj?

13(*)+ = {siis.. w- = {i:>o . м = +w-

В работе предлагается алгоритм сложности 0(п3) операций, который проверяет существование отсечения вида (15) В разделе 4 6 рассматриваются различные варианты предложенного алгоритма отсечения и ветвления В заключительном разделе 4 7 представлены результаты экспериментального исследования предложенного алгоритма на множестве общедоступных тестовых примеров Показанно, что разработанный алгоритм для задачи 1 | r3 | YlwjU3 является более эффективным, чем лучший алгоритм для данной задачи, существующий в литературе14

В пятой главе рассматриваются комбинаторные свойства iVP-трудн-ой в обычном смысле15 задачи минимизации суммарного запаздывания для одного прибора 1 11 ^ Т3 Получены свойства оптимальных расписаний, на основе которых построены алгоритмы решения задачи Построены оценки оптимального значения целевой функции В разделе 5 1 приводится постановка рассматриваемой задачи, вводятся необходимые понятия и определения

В разделе 5 2 приводятся алгоритмы решения рассматриваемой задачи, основанные на "декомпозиционных" свойствах задачи Одно из первых "декомпозиционных" свойств задачи было получено Лоулером, который предложил алгоритм решения задачи трудоемкости 0(n4Y^P]) операций16

Перенумеруем требования множества N в порядке неубывания директивных сроков di < < dn (при этом, если d3 = dJ+1, то р3 < p3+i, j = 1,2, , п — 1) Пусть J* будет требованием с максимальной продолжительностью (если таких требований несколько, то выберем требование с наибольшим номером), те J* = max{j € N р3 = maxрг} Пусть

içN

Sk = ta + Y,k3=iP],k = 1,2, ,7i и 5 = 5„

Через L(I) обозначим множество индексов к > j*, для которых выполнены неравенства d3 + р3 < Sk (j = J* + 1, , fc) и < dk+1, доопределив dn+1 = +00 Множество L(I) будем называть множеством подходящих позиций для требования j*

Peridy, L , Pinson Е, Rwreau D Using short-term memory to minimize the weighted number of late jobs on a single machine// European J Oper Res - 2003 - V 148 P 591 - 603

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

l6Lawler E L A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness // Ann Discrete Math - 1977 - No 1 - P 331-342

Теорема 10 [12] Для любого примера I множество подходящих позиций L(I) для требования j* не пусто и существует оптимальное расписание ж* б П*(1), при котором требование j* обслуживается на месте к £ Ь{1) При этом для подходящего места к выполняется

О ]*)*- для j £ {1,2, ,k}\{f} и {]* для j £ {к + 1, ,п}

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

В разделе 5 3 рассматриваются свойства оптимальных расписаний и предлагается алгоритм решения примеров I в случае, когда при любом расписании -ж £ П(/) запаздывает одно и тоже количество требований т (О < т < п) При этом запаздывающие требования упорядочены в конце расписания ж (те расписание ж можно представить в виде ж = (tti,тгг), где подрасписание Ж2 содержит все m запаздывающих требований) Через 0(ж) обозначим множество запаздывающих требований при расписании ж В рассматриваемом случае верны следующие утверждения

Лемма 3 При любом оптимальном расписании ж* требования множества D(ir*) обслуживаются в SPT порядке17

17SPT - Shortest Processing Time Расписание гг называется SPT-расписанием, если требования

Далее, перенумеруем требования примера I в порядке невозрастания продолжительностей обслуживания р\ > Р2 > > рп, при этом, если Р] = Рз+1 0 = 1, 1), то ¿, > <1]+1

Лемма 4 Существует оптимальное расписание 7г* такое, что если для некоторого к £ N выполняется к £ 0{к*), то (у —> к)п- для всех требований ] £ {к + 1, , п}

Найденные свойства позволяют построить алгоритм нахождения оптимального расписания за 0(п3) операций (алгоритм РА) Построение оптимального расписания алгоритмом РА сводится к обходу дерева, каждая ветка которого соответствует некоторому порядку обслуживания запаздывающих требований

В разделе 5 4 приводятся две оценки оптимального значения суммарного запаздывания, основанные на свойствах ЭРТ-расписаний Полученные оценки позволяют найти абсолютную погрешность значения суммарного запаздывания при ЭРТ-расписании18

Перенумеруем требования множества N в порядке неубывания продолжительностей обслуживания, т е р\ < Р2 < < рп БРТ-расписание (1,2, , п) будем обозначать через Рассмотрим пример задачи / = ({р3, ¿о) с оптимальным значением целевой функции Р*(1) Пусть

дтт = тт^дг йу и с?тах = тах_,ел/ Выберем величины С и 8 такими, что

Лтт < с < дтш и 5 = тах{с£тах - С, С - с1т1П} Рассмотрим пример V = ({р= о)

Теорема 11 (первая оценка) Для выбранных значений С и 8 верно неравенство

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

"Относительная погрешность значения суммарного запаздывания при ЕОБ-расписании (расписании, требования при котором упорядочены в порядке невозрастания значений директивных сроков) установлена Лоулером в 1977 г

Для формулировки второй оценки рассмотрим функцию

п ]

/(¿) = ^ тах{0, *0 + А - *}

Значение этой функции в точке t равно оптимальному значению суммарного запаздывания для параметрического примера /(£) = ¿0)> при котором директивные сроки всех требований равны f Функция / является кусочно-линейной, невозрастающей, непрерывной и неотрицательной функцией, принимающей значения 0 для всех t +

Теорема 12 (вторая оценка) Для любого примера I справедливы неравенства Дс2тах) < < /((¿тт)

Раздел 5 5 посвящен результатам экспериментальных исследований задачи

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

В шестой главе диссертации рассматривается частный АГР-трудный [3] случай задачи минимизации суммарного запаздывания

Предлагается подход решения задачи в случае (16), при котором исходное множество требований N разбивается на к таких непересекающихся подмножеств Л4х,М.2, , -Мь, что N = А^иЛ^и и^к и таУн^еМс Иг ~ < тт= 1, , к, а затем на основе этого разбиения строится оптимальное расписание

В разделе 6 1 формулируется и доказываются две леммы, отражающие свойства оптимальных расписаний для случая (16)

(16)

Лемма 5 Существует оптимальное расписание -к*, при котором выполняется либо (к —» г)я-., либо (з —> к)ж» для любой тройки требований г,3, к £ ЛГ; что \йг — <13\ < тт{рг,р^}, к < тт{»,;} и (г —ь 3)^

Лемма 6 Существует оптимальное расписание к*, при котором выполняется либо (к —> з)-ж'> либо ((к + 1) —> к)п* для любой пары требований к,з £ N, к < з

На первом этапе решения задачи производится разбиение множества требований N на непересекающиеся подмножества Л4\, М.% , Л4ь, такие, что разность между максимальным и минимальным директивными сроками требований каждого подмножества не превышает величины минимальной продолжительности требований из этого подмножества19

Определим параметрический пример I= ({р3, д,3^)}зещ, 0), где Н/е = {к, к + 1, ,тг} и й3{Ь) = й3 — йп + Ь — Ц - это пример

исследуемой задачи обслуживания требований множества Ыь с моментом начала обслуживания равным нулю и директивными сроками й3{Ь), линейно зависящими от параметра t

Идея предлагаемого подхода заключается в построении оптимальных расписаний тг£(£) для примеров Iк = п,п — 1, ,1, для всех целочисленных точек £ £ [^о, <1п] Расписания 7г£(£) строятся на основе построенных на предыдущих шагах расписаний 7г^(£'), I > к,1/ £ [¿о,

Согласно леммам 5 и 6, при построении оптимального расписания для исходного примера I можно исключить из рассмотрения все расписания 7Г, при которых

В разделе 6 3 рассматривается случай к = 1, когда параметры требований удовлетворяют условиям

(a) (г -» к з)ж, к < тт{г, з},г,з £ Ма,к £ Мр, /3 < а,

(b) (з к -»• (к + 1)),, к < з

19Такое разбиение множества требований может быть выполнено за 0(п) операций

В этом случае при построении оптимального расписания с помощью описанного выше подхода для каждой точки t требуется просмотреть только две позиции для требования к до всех требований множества N¡¡+1 и после всех требований этого множества При обслуживании требования к до всех требований множества получаем расписание — Рк)), после всех требований - расписание {ъ*к+1{1),к) Расписание с наименьшим значением суммарного запаздывания среди двух полученных расписаний будет оптимальным расписанием для примера Алгоритм, реализующий данный подход к построению расписания в случае (17), мы назвали алгоритмом В-1

Теорема 13 Алгоритм В-1 находит оптимальное расписание для ЫР-трудного случая (17) за 0(п^р3) операций

В разделе б 4 рассматривается случай для произвольного значения к Приводится описание алгоритма В-к нахождения оптимального расписания в случае (16), трудоемкость алгоритма 0(кп^2р3) операций

В разделе 6 5 рассматриваются примеры, параметры требований которых удовлетворяют условиям

{Л\<й2< < <1п, <1п - й < 1, (18) ¿о

Алгоритм С-1 находит оптимальное расписание для случая (18) за 0(п2) операций Отметим, что данный алгоритм можно использовать для решения примеров в случае, когда в условиях (18) второе неравенство заменено на с1п — < НОД (рь ,рп)

В разделе 6 6 рассматриваются примеры, параметры требований которых удовлетворяют условиям

Л3 - д.,-1 > р3, з = 2,3, ,п (19)

Поскольку р3 > 0, У^ € Я, то выполняется й\ < < йп Отметим, что случай (19) является "предельным" подслучаем (16), когда количество подмножеств к = п, т е каждое подмножество ЛАа, а = 1, , к, состоит ровно из одного требования

Показано, что для случая (19) существует оптимальное расписание ■к* £ П*{1), при котором требование у* обслуживается на первой позиции

из множества Ь(1) Данное свойство позволяет построить алгоритм В-п решения задачи трудоемкости 0(п2) операций

В разделе 6 7 построен алгоритм трудоемкости 0(п3) операций для случая

Г VI < Р2 < < Рп, \ Р1 + ¿1 < р2 + ¿2 < < Р2 + ¿2 В седьмой главе диссертации исследуются свойства алгоритма В-1, показано, что данный алгоритм может быть использован для нахождения решения следующих УУР-полных задач разбиения РАЗБИЕНИЕ, ЧЕТНО-НЕЧЕТНОЕ РАЗБИЕНИЕ (ЧНР), ЧЕТНО-НЕЧЕТНОЕ РАЗБИЕНИЕ С ОГРАНИЧЕНИЯМИ (ОЧНР)

Расписание тг назовем расписанием, обладающим свойством В-1, если для всех требований А- е {1,2, ,п— 1} при расписании 7Г выполняется либо (к —> либо (у к)ж для всех ] € {к + 1, , п}

Множество всех расписаний, обладающих свойством В-1 для примера I, будем обозначать через Пв_!(/) Пусть П^_1(/) = Пв_х(/) ПП*(7)

Теорема 14 Алгоритм В-1 находит оптимальное расписание примера I задачи 1 || Е^з тогда и только тогда, когда П^_1(7) ^ 0

Раздел 7 2 посвящен классической NР-полной задаче РАЗБИЕНИЕ, рассматривается схема полиномиального сведения примеров этой задачи к примерам задачи теории расписаний 1 11 Е

В классической задаче РАЗБИЕНИЕ требуется определить, существует ли такое разбиение множества п целых положительных чисел на два подмножества, что суммы чисел в обоих подмножествах равны Задача ЧНР представляет собой модификацию задачи РАЗБИЕНИЕ, когда на разбиение множества накладывается ограничение, что соседние числа (первое и второе, третье и четвертое и т д ) должны оказаться в разных подмножествах Задача ОЧНР представляет собой задачу ЧНР с дополнительными ограничениями на значения чисел исходного множества

Показано, что любое (в том числе, и оптимальное) расписание канонического вида обладает свойством В-1 Таким образом, мы можем использовать алгоритм В-1 для нахождения решения канонических примеров задачи 1 11 £ Т3 и, соответственно, задач РАЗБИЕНИЕ, ЧНР, ОЧНР, хотя канонические примеры не принадлежат случаю (17) С учетом особенностей канонических примеров предложен алгоритм В-1-канонический,

(20

трудоемкость которого не хуже известного алгоритма из книги Гэри и Джонсона20 для задачи РАЗБИЕНИЕ

В разделе 7 3 приводится модификация алгоритма В-1, которая позволяет снизить трудоемкость решения примеров в случае (17) Идея алгоритма В-1-модифицированный заключается в том, что процесс построения оптимального расписания сведен к процессу построения кусочно-линейной функции специального вида Рассматриваются три операции над функциями "сдвиг" функции, сложение двух функций и нахождение функции минимума двух функций Полученные свойства рассматриваемых функций были использованы для построения алгоритма В-1-модифицированный Преимущество этого алгоритма заключается в том, что при построении решения для примеров случая (17) нет необходимости рассматривать все целочисленные точки интервала £ 6 Трудоемкость решения полиномиально зависит от максимального количества точек изменения наклона функций, рассматриваемых в ходе решения Преимуществом Алгоритма В-1-модифицированный является то, что при масштабировании всех параметров примера, трудоёмкость алгоритма решения не меняется Также данный алгоритм может быть использован для решения задач 1 11 (в случае (17)), РАЗБИЕНИЕ, ЧНР и ОЧНР с нецелочисленными параметрами

В восьмой главе рассматривается графическая реализация метода динамического программирования на примерах решения задач РАЗБИЕНИЕ и РАНЦА Проведен сравнительный анализ предлагаемого метода с известными алгоритмами решения этих задач

Задача РАЗБИЕНИЕ Задано упорядоченное множество из п положительных целых чисел В = {61, £>2; , Ьп}, > 62 > > Ьп Требуется разбить множество В, на два подмножества В\ и В2, В\ У В2 = В, В\^\В2 — 0, так, чтобы минимизировать значение

I £ Ъг - £ Ьг\ —> шш (21)

ь,еВх ь,ев2

Задача об одномерном РАНЦЕ

Дя) = 2Г=1 ЬЪ —> шах

ЕГ=1 (22)

хг е {0,1}, г = 1, ,п

20 См 3

Когда Cj = аг = Ьг, г = 1,2, ,п, и А = ^ т0 задачи (21) и (22)

являются эквивалентными

В разделе 8 1 представлен графический алгоритм для решения задачи РАЗБИЕНИЯ В алгоритме последовательно на шаге а = 1,2, ,п рассматриваются следующие функции

K(t) = I Е Ь>~ Е Fl{t) = \ Е Е M

bjgSiit+bc) ъ3ев2^+ьа) На каждом шаге а алгоритма B\(t)\JB2{t) = {bi,b2, ,ba-i}, Vi Последовательно "добавляется" очередное число Ьа, где а = 1,2, ,п, в множество Bi{t) или B2(t) В каждой точке t "добавление" числа Ъа выбирается таким образом, чтобы минимизировать значение функции I L^eBiW Ъз + Ь ~ ^XeB2(t)bJ I На очередном шаге а из функции ■Fa-ii» = I ¿ft3€ßi(i) bJ - iZb^BM ЬзI» полученной на предыдущем a - 1 шаге, строится функция

Fa{t) = nnn{irQ:_i(i - 6a), Fe_i(f + ba)} = тт^'й.^й}, где F0(t) = О, V t Если F*(t) < F*(t), то B^t) = Вi(t - ba) \J{ba}, иначе B2(t) = B2{t + ba) Кусочно-линейную функцию Fa(t) можно представить (и хранить) в табличном виде по точкам "излома" to, t\, , tma На промежутке [t, — , -t- *'+12~*'),г = 1,2, , ma — 1, кусочно-линейная функция Fa(t) задается уравнением Fa(t) = \t — i,|, те график функции пересекает ось t в точке tt Каждому временному интервалу + 1+12 ') соответствует некоторое фиксированное разбиение (Bi,B2), те = B^t2) = Въ Vi1,*2 G [f, - b^.i, + (аналогично и для ^(i)) Пусть на предыдущем шаге а — 1 получена функция Fa_!(i), заданная таблично На шаге а мы рассматриваем две функции Fa_i(i — ba) и Fa-\(t + ba), заданные двумя таблицами в точках "излома" to - ba, tx - ba, tt - ba, , ima_i - ba и to + ba, tx + ba, , t% 4" ba, , t7Ua_1 -j- ba

В разделе 8 2 показано сокращение рассматриваемых интервалов Учитывая, что на шаге п нам требуется вычислить значение целевой функции и найти разбиение лишь в точке t = 0, то на шаге п — 1 нам достаточно рассчитать значения в точках t е [—bn,bn] Аналогично на шаге п — 2 достаточно рассмотреть интервал [—bn — &п-ь bn + bn_i] и т д

Следовательно, на каждом шаге а достаточно рассматривать интервал [- Еj=Q+i £"=<*+1 ьзЬ вместо интервала [- Ъ}, i У

При построении функции FQ(i) рассматриваются только точки t € [— bj I £"=a+i У Чтобы интервал сокращался максимально быст-

ро необходимо упорядочить Ь3 по невозрастанию Учитывая, что функция Fa(t),a = 1,2, , п, является четной, поэтому достаточно хранить "половину" таблицы Кроме того, следует отметить, что при "масштабировании с небольшим изменением параметров" примера, те когда Ь'3 = Kbj + £j, где ¡Ejl -С К, К— некоторая достаточно большая положительная константа, j = 1, 2, , п, трудоемкость алгоритма, построенном на методе динамического программирования21, составит 0(Кп ^ Ъ3) операций, в то время как у графического алгоритма трудоемкость не изменится Для алгоритма Balsub22 с трудоемкостью 0{пЬтах) операций такое "масштабирование" примера также приведет к увеличению трудоемкости в К раз Таким образом, графический алгоритм находит решение за одно и тоже количество операций для всех точек некоторого конуса в п—мерном пространстве, если представить параметры примера как точку (£>i,&2> , Ьп) в п—мерном пространстве Причем параметры примера могут быть как отрицательными, так и нецелочисленными

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

1 В = {ЬиЬ2, А} = {М,М-1,М-2, ,1,1, ,1} М- достаточно большое число, сумма единиц в примере равна М(М + 1)//2, те n = М + М(М + 1)/2,

2 класс нецелочисленных примеров В = {&i, b2, , bn}, если не существует такого набора чисел Л, = ±1,г = 1, , п, что выполняется АА + Л2&2 + + А пЬп = О

В разделе 8 3 представлена графическая реализация метода динамического программирования решения задачи РАНЦА Также как и для задачи РАЗБИЕНИЕ в ранец последовательно "добавляются предметы" На шаге (а + 1) строится график g2{t) из графика ga(t) смещением "наверх" на са+1 и "вправо" на аа+\ График д1 (t) полностью повторяет график ga{t) Следовательно, чтобы построить ga+i{t) = max{g1{t),g2{t')} необходимо рассмотреть не более 2та интервалов, образованных точками из

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

22 Keller Н, Pf erseht/ U, Pismger D Knapsack problems, Springer, 2004, - 546 p

множества {t0,ti, ,tma,t0 + <v+i,ii + aa+1, ,tma + oa+i}, которые принадлежат интервалу [О, А] Количество точек не превосходит А для аг € Z+, г = 1, , гг. Параметры задачи могут быть и отрицательными В заключении диссертации перечислены основные результаты работы и намечены пути дальнейших исследований

Основными результатами диссертации являются следующие.

1 Для Л^Р-трудных задач {Р, R, Q}\prec, г31{Ьтах, Стах} найдены оценки абсолютной погрешности целевой функции Для этих классов задач введена метрика Предложена новая схема нахождения приближенного решения данных задач, состоящая из двух этапов На первом этапе, решая задачу линейного программирования, находится изменение исходных параметров примера A (rf,pft, df\j € TV, г € М), что полученный пример В с параметрами требований [rf >pfz> df \з £ N, г £ М) принадлежал известному полиномиаль-но/псевдополиномиально разрешимому классу примеров исходной NP-трудной задачи и был на минимальном расстоянии от примера А в метрике р На втором этапе для решения примера В используется уже известный для данного класса примеров полиномиальный/псевдополиномиальный алгоритм, а затем найденную им оптимальную перестановку требований применим к примеру А Абсолютная погрешность такого решения не будет превосходить расстояния р(А, В) между примерами,

2 Для AfP-трудной задачи 1 | r3 \ Ьтах предложен новый точный алгоритм решения на основе методов ветвей и границ и программирования в ограничениях Найдены новые эффективные нижние оценки оптимального значения целевой функции Экспериментальное исследования на множестве тестовых примеров показало преимущество (время работы алгоритма и количество ветвлений в дереве поиска существенно меньше) предложенного алгоритма над существующими алгоритмами,

3 Для ./VP-трудной задачи 1 | r3 \ ^WjUj предложен точный алгоритм отсечения и ветвления Преимущество (время работы алгоритма и количество ветвлений в дереве поиска) предложенного алгоритма над наилучшим алгоритмом для данной задачи, представленном в литературе, на множестве общедоступных тестовых примеров подтверждено численными экспериментами,

4 Поставлена и решена задача, в некотором смысле "двойственная" к задаче 1 | г3 | /тах, трудоемкость алгоритма 0(п2) операций Решение данной задачи является оценкой снизу для исходной ЫР-трудной задачи 1 | г, | /тах и может быть использована в алгоритмах сокращенного перебора,

5 Для АГ-Р-трудной задачи 1 || Т} доказаны новые свойства оптимальных расписаний МР-трудного частного случая, когда параметры требований удовлетворяют ограничениям > > > рп, с?1 < ¿2 < < (1п, и предложен алгоритм решения этого случая задачи за 0(п2 р^) операций Выделен один псевдополиномиаль-но разрешимый (0(п ^Рз) операций) и два полиномиально (0(п2) операций) разрешимых подслучая этого случая Получены необходимое и достаточное условия того, что построенный пседополино-миальиый алгоритм находит оптимальное решение

Показано, что любой алгоритм решения задачи 1 || основан-

ный на "декомпозиционных" правилах23, при решении канонических примеров будет иметь трудоемкость не менее 0(п2%~1) операций,

6 Построены алгоритмы решения задач РАЗБИЕНИЯ и РАНЦА, показавшие лучшую экспериментальную эффективность по сравнению с представленными в научной литературе Алгоритмы позволяют решать примеры с нецелочисленными и отрицательными значениями параметров

23Szmarc W, délia Croce F, Grosso A Solution of the single machine total tardiness problem // Journal of Scheduling - 1999 - V 2 - P 55-71

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

[1] Белялов Т К, Конное И В , Лазарев А А , Перфилов С Н, Хали-тов Ф Р Программное обеспечение оптимального управления систем ГАП-ТВ // Материалы научно-исследовательской конференции "Практика использования мини и микро ЭВМ в ГАП механической обработки" 1988, Казань С 110-125

[2] Беркута ОН, Лазарев А А Алгоритмы сложности 0(п3) решения задачи суммарного запаздывания // Иссл по прикл мат - Выпуск 22 - Казань, 1995 - С 67-78

[3] Гафаров Е Р, Лазарев А А Доказательство А^Р-трудности одного частного случая задачи минимизации суммарного запаздывания// Известия РАН Теория и системы управления — 2006 — N 3, —

С 120-128

[4] Лазарев А А Эффективный алгоритм для задачи минимизации максимальной задержки // Теория управления и методы оптимизации - Деп в ВИНИТИ № 6633-83 - С 14-21

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

[6] Лазарев А А Двойственная проблема к задаче минимизации максимального штрафа // Исследования по прикладной математике -Казань, 1984 - Выпуск 10 - С 111-113

[7] Лазарев А А Алгоритмы решения задачи минимизации суммарного запаздывания для одного прибора // Теория управления и методы оптимизации - Деп в ВИНИТИ № 3795-85 - С 21-30

[8] Лазарев А А Исследование задач теории расписаний с помощью преобразований // Исследования по прикладной математике - Казань, 1985 - Выпуск 12 - С 63-74

[9] Лазарев А А К решению задачи минимизации суммарного запаздывания // VII конференция "Проблемы теоретической кибернетики", 1985, Тезисы , часть I, Иркутск, - С 114-115

[10] Лазарев А А Об одном эффективном алгоритме решения задачи минимизации суммарного запаздывания // Х-ый симпозиум "Программное обеспечение решения задач оптимального планирования", Нарва, 1988, Тезисы докладов С - 135-136

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

[12] Лазарев А А Декомпозиционные алгоритмы решения задачи минимизации суммарного запаздывания // Исследования по прикладной математике, Вып 21, Казань, 1994 - С 105-110

[13] Лазарев А А Минимизация оценки абсолютной погрешности для задач 1||Tj и l\\Vj // Исследования по прикладной математике, Вып 22, Казань, 1995 - С 56-62

[14] Лазарев А А Парето-оптимальное множество NP-трудной задачи минимизации максимального временного смещения// Известия РАН Теория и системы управления - 2006 - N 6 - С 103-110

[15] Лазарев А А Оценка абсолютной погрешности задач теории расписаний с критерием минимизации максимального временного смещения // Доклады Академии Наук - 2007 - Том 415, № 4 - С 446-449 (Англ вариант статьи A A Lazarev Estimation of Absolute Error in Scheduling Problems of Minimizing the Maximum Lateness// Doklady Mathematics - 2007 - Vol 76, No 1 - P 572-574)

[16] Лазарев А А Решение NP-трудной задачи теории расписаний минимизации суммарного запаздывания // Журнал вычислительной математики и математической физики — 2007 — Том 47, № 6 —

С 1087-1099

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

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

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

[20] Лазарев А А , Кварацхелия А Г Стохастическое исследование методов ветвей и границ для NP-трудной задачи теории расписаний минимизации суммарного запаздывания для одного прибора // Материалы VII Международного семинара «Дискретная математика и ее приложения» (29 января - 2 февраля 2001 г) Часть III - M Изд-во центра прикладных исследований при мех -мат факультете МГУ, 2001 г - С 379-381

[21] Лазарев А А , Кварацхелия А Г Исследование проблемы теории расписаний 1 11 // Проблемы теоретической кибернетики Тезисы докладов XIII Международной конференции (Казань, 27-31 мая 2002 г) Часть II - M Изд-во центра прикладных исследований при механико-математическом факультете МГУ, 2002 - С 107

[22] Лазарев А А , Кварацхелия А Г Исследование проблемы теории расписаний 1 11 ^ Т3 // Материалы Российской конференции «Дискретный анализ и исследование операций», 24-28 июня, 2002 г -Новосибирск, 2002 - С 218

[23] Лазарев А А , Кварацхелия А Г Теоретическое и экспериментальное исследование NP-трудной проблемы теории расписаний минимизации суммарного запаздывания на одном приборе // Исследования по прикладной математике и информатике - Казань Изд-во Казан гос ун-та, 2003 - Вып 24 - С 90-106

[24] Лазарев А А , Кварацхелия А Г Алгоритм 0(п2^Рз) решения NP-трудной проблемы теории расписаний 1 11 // Материалы VIII Международного семинара «Дискретная математика и ее приложения» (2-6 февраля 2004 г ) - Изд-во механико-математического факультета МГУ, 2004 - С 211-213

[25] Лазарев А А , Кварацхелия А Г Алгоритм решения проблем 1 11

Т3 и четно-нечетного разбиения // Труды VI Международной конференции «Дискретные модели в теории управляющих систем»

(7-11 декабря 2004 г) М Изд-во факультета вычислительной математики и кибернетики МГУ, 2004 - С 184-187

[26] Лазарев А А , Кварацхелия А Г, Гафаров ЕР Алгоритмы решения NP-трудной проблемы минимизации суммарного запаздывания для одного прибора // Доклады Академии Наук, 2007 - Том 412, № 6 - С 739-742 (Англ вариант статьи A A Lazarev, A G Kvaratskhehya, and Е R Gafarov Algorithms for Solving the NP-Hard Problem of Minimizing Total Tardiness for a Single Machine // Doklady Mathematics - 2007 - Vol 75, No 1 - P 130-133)

[27] Лазарев A A , Садыков P P Эффективность полиномиального алгоритма 0(n3 log n) для решения NP-трудной проблемы минимизации максимального временного смещения 1 | r} \ Ьтях// Материалы VII Международного семинара "Дискретная математика и ее приложения", 29 января - 2 февраля - М Изд-во центра прикладных исследований при мех -мат факультете МГУ, 2001 - С 381 - 383

[28] Лазарев А А , Садыков Р Р К исследованию проблемы теории расписаний 1 | г3 | ¿max// Материалы российской конференции "Дискретный анализ и исследование операций", 24 июня - 28 июня - Новосибирск Изд-во Ин-та математики, 2002 - С 219

[29] Лазарев А А , Садыков Р Р Схема приближенного решения проблемы 1 | г, | Ьтях// Материалы российской конференции "Дискретный анализ и исследование операций", 28 июня - 2 июля - Новосибирск Изд-во Ин-та математики, 2004 - С 173

[30] Лазарев А А , Садыков Р Р Теория расписаний Минимизация максимального временного смещения и суммарного взвешенного числа запаздывающих требований // Научное издание Вычислительный центр им А А Дородницына РАН - 2007 - 135 С

[31] Лазарев А А , Садыков Р Р, Севастьянов С В Схема приближенного решения проблемы 1 | r} \ Lm3x// Дискретный анализ и исследование операций - 2006 - Сер 2 - Т 13, N 1 - С 57-76

[32] Лазарев А А , Сираев Р Р Решение задач календарного планирования методом ветвей и границ //Материалы 11-ой Байкальской международной школы-семинара "Методы оптимизации и их примене-

ние", Июль, 5-12, 1998, Секция 1 Математическое программирование -С 159-163

[33] Лазарев А А , Сираев Р Р К решению задачи календарного планирования методом ветвей и границ//Материалы 3-ей международной конференции "Математические методы и компьютеры в экономике", май, 26-27, 1998, Часть 1, Пенза - С 27-28

[34] Лазарев А А , Сираев Р Р Системы обработки экономической информации Часть I Кредитование в банке // Казань, Издательство Казанского математического общества, 1998 - 285 С

[35] Лазарев А А , Хабибуллин Р Ф Эффективные алгоритмы для некоторых задач теории расписаний// VII конференция "Проблемы теоретической кибернетики" — 1985, Тезисы , часть I, Иркутск — С 115-116

[36] Лазарев А А , Шульгина О Н Псевдополиномиальный алгоритм решения NP-трудной задачи минимизации максимального временного смещения// Труды 11-й международной Байкальской школы -семинара "Методы оптимизации и их приложения", 5-12 июля-Иркутск, Байкал, 1998 - С 163 - 167

[37] Лазарев А А , Шульгина О Н Псевдополиномиальный алгоритм решения iVP-трудной задачи минимизации максимального временного смещения //Материалы 11-ой Байкальской международной школы-семинара "Методы оптимизации и их применение", Июль, 5-12,1998, Секция 1 Математическое программирование - С 163-167

[38] Лазарев А А , Шульгина О Н Задача минимизации максимального временного смещения для одного прибора свойства, процедуры, алгоритмы// 9-я Всероссийская конференция "Математическое программирование и приложения", 22 - 26 февраля - Екатеринбург, 1999 - С 183 - 184

[39] Лазарев А А , Шульгина ОН К решению задачи планирования производственно - экономической деятельности предприятия// Иссл по прикл мат - Выпуск 21 - Казань, 1999 - С 155 - 169

[40] Лазарев А А , Шульгина О Н Полиномиально разрешимые частные случаи задачи минимизации максимального временного смещения//

Ред Журн "Изв Вузов Математика" - Казань, 2000 - 11 с - Библ 8 назв - Деп в ВИНИТИ 28 11 00, N 3019-ВОО

[41] Gafarov Е R, Lazarev A A Graphical approach for solving combinatorial problems // International Conference on Operations Research, - Karlsruhe, Germany, 6-8 September 2006, P 59

[42] Gafarov E R, Lazarev A A Algorithms for single machine total tardiness problem // International Conference on Operations Research - Karlsruhe, Germany, 6-8 September 2006, P 83

[43] Lazarev A A Scheduling algorithms based on necessary optimality // Journal of Soviet Mathematics, V 44, N 5, 1989, P 635-642

[44] Lazarev A A Analysis of Scheduling Problems Using Transformation // Journal of Soviet Mathematics, Vol 45, N 2, April 1989 P 1029-1036

[45] Lazarev A Scheduling to minimize maximum lateness for single machine new approach of investigation// 9-th Belgian-French-German Conference on Optimization, Namur, September, 7-11, 1998,

http //www fundp ac be/ bfgconf9/

[46] Lazarev A A Anahze of structure of optimal schedule the problem minimizing maximum lateness for single machine// the Fourth International Congress on Industrial and Applied Mathematics, 5-9 July 1999, Edinburgh, Scotland - P 283

[47] Lazarev A A Minimum absolute error for ./VP-hard scheduling problem for single machine - minimizing maximum lateness// Workshop on the Complexity of Multivariate Problems, October 4-8, 1999, Hong Kong, China - P 13

[48] Lazarev A A , Gafarov E R Special case of the single machine total tardiness problem is ./VP-hard // 12th IFAC Symposium on Information Control Problems m Manufacturing INCOM'2006 Preprints, Vol III, Operational Research, May 17-19, 2006 — Saint-Etienne, France — P 155-157

[49] Lazarev A , Kvaratskheha A Methods to research problem of scheduling theory minimizing total tardiness on a single machine // Abstracts of VI Workshop «Models an Algorithms for Planning and Scheduling Problems» (Aussois, France, 30 III - 4 IV 2003) - P 143-144

[50] Lazarev A , Kvaratskheha A , Tchernykh A Solution Algorithms for the Total Tardiness Scheduling Problem on a Single Machine // Proceedings of XV International Conference ENC'04 (Colima, Mexico, 20 - 24 X 2004) - P 474-480

[51] Lazarev A , Kvaratskheha A Algorithms for solving problems 1 | | ^ T3 and Even-Odd Partition // Abstracts of XVIII International Conference «European Chapters on Combinatorial Optimization» (26-28 May, Minsk, Belarus) - Minsk United Institute of Informatics Problems on the National Academy of Sciences of Belarus, 2005 - P 32-33

[52] Lazarev A A , Sadykov R R A polynomial approximation scheme for the 1 | fj | ¿max scheduling problem with guaranteed absolute error// Arias Estrada M , Gelbukh A (eds ) Avances en la Ciencia de la Computación Proceedings of Fifth Mexican International Conference ENC'04, 20 - 24 September - Colima, Mexico 2004 - P 465 - 473

[53] Lazarev A , Sehul'gina O Problem minimizing maximum lateness for single machine properties, procedures, algorithms// 9-th Belgian-French-German Conference on Optimization, Namur, September 7 — 11 — Namur, 1998 - P 45

[54] Lazarev A , Siraev R Scheduling to minimize total weighted completion time branch and bound method// 9-th Belgian-French-German Conference on Optimization, Namur, September, 7-11, 1998,

http //www fundp ac be/ bfgconf9/

[55] Sadykov R R , Lazarev A A , Kvaratskheha A G Research of absolute error for NP-hard scheduling problem minimizing maximum lateness// Proceedings of the Tenth Franch-German-Italian Conference on Optimization FGI'00, 4-8 September - Montpelier, France 2000-P 56-57

[56] Sadykov R R , Lazarev A A Experimental comparison of branch-and-bound algorithms for the 1 | r3 \ Lmax problem// Proceedings of the Seventh International Workshop MAPSP'05, 6-10 june - Siena, Italy 2005 - P 239 - 241

Лазарев Александр Алексеевич

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

Подписано в печать 11 09 2007

Формат бумаги 60x84 1/16 Уч -изд л 2,2. Уел -печ. л 2,25 Тираж 100 экз. Заказ 27

Отпечатано на ротапринтах в Вычислительном центре им А А Дородницына Российской академии наук 119333, Москва, ул Вавилова, 40

Введение

1 Оценка абсолютной погрешности задач минимизации максимального временного смещения

1.1 Постановка задачи 1 | rj \ Lmax.

1.2 Обозначения и определения основных понятий.

1.3 Абсолютная погрешность приближённого решения.

1.4 Схема нахождения приближённого решения.

1.4.1 Вариант схемы на основе случая l\di<dj,di-ri-pi>dj-rj-pj\Lmax

1.4.2 Вариант схемы на основе случая Хогевена.

1.5 Экспериментальное исследование полииомиальных алгоритмов решения задачи 1 | rj \ Lmax.

1.5.1 Способ генерации примеров.

1.5.2 Оценка экспериментального значения абсолютной погрешности.

1.5.3 Эффективность применения полиномиальных алгоритмов для общего случая задачи.

1.6 Свойства оптимальных расписаний общего случая задачи l\rj\Lmax

1.7 Свойства оптимальных расписаний частных случаев задачи l\rj\Lmax.

1.8 Оценки абсолютной погрешности.

1.8.1 Задачи для нескольких приборов.

1.8.2 Оценка абсолютной погрешности.

1.8.3 Схема приближённого решения задачи Р | prec,rj ( Lmax.

1.9 Нормированное пространство примеров.

1.10 Схемы нахождения приближённого решения.

1.10.1 Схема сведения задач а | /3 | Lmax а | /? | Cmax и а | Р, Tj | £max a I /3,rj = 0 I £max.

1.10.2 Схема сведения задач а \ (3,Pj | Lmax а | /3,pj = р \ Lmax и a\P,pj\Lm№-^a\ptPj = l\Lmax.

1.10.3 Схема сведения задач {R, Q} | /3 | Lmax —> Р | /3 | Lmax

1.10.4 Схема сведения задачи R \ /3 | Lmax Q \ /3 \ Lmax.

1.10.5 Схема сведения задачи а | /3 | Lmax a\/3,pj е {pi, • • • ,Рл}|Стах

2 Полиномиально и псевдополиномиально разрешимые случаи задачи

1 М £тах

2.1 Задача 1 | с?г < c?j, di г,- — Pi > dj — fj — pj | Lmax.

2.1.1 Свойства задачи.

2.1.2 Задача на быстродействие при ограничении на максимальное временное смещение.

2.1.3 Алгоритм построения множества Парето-расписаний по критериям (7тах и Lmax

2.2 "Двойственная" задача.

2.3 "Обратная" задача.

3 Алгоритмы оптимального решения задачи 1 | гj | Lmax

3.1 Существующие методы решения задачи 1 | гj | Lmax

3.1.1 Алгоритм Карлье.

3.1.2 Метод программирования в ограничениях.

3.2 Алгоритмы решения задачи 1 | г, | Lmах

3.3 Экспериментальное сравнение алгоритмов решения задачи 1 | fj- | Lmax.

3.4 Модифицированный алгоритм Карлье.

3.5 Эффективные алгоритмы решения задачи минимизации максимального временного смещения.

3.5.1 Процедура построения приближённого решения задачи rj>di > dj\Lmax. Оценка абсолютной погрешности.

3.5.2 Процедура построения допустимого расписания для задачи l|rj < rj,di > dj\Lmax.

3.5.3 Алгоритм решения задачи 1|гг- < rj,di > dj\Lmax

3.5.4 Полиномиальные алгоритмы решения частных случаев задачи 1|r{ < r^di > rfj|Lmai.

3.6 Приближённый алгоритм решения общего случая задачи. Оценка абсолютной погрешности.

4 Алгоритм ветвей и отсечений для решения задачи 1 | гj | WjUj

4.1 "Гибридная" схема решения одного класса задач целочисленного линейного программирования.

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

4.3 Формулировка задачи 1 | rj | ^WjC/j как задачи ЧЦЛП.

4.3.1 Дополнительные ограничения.

4.4 Генерация отсечений.

4.5 "Гибридный" алгоритм ветвей и отсечений.

4.6 Экспериментальная оценка эффективности

5 Исследование свойств задачи 1 11 7}

5.1 Постановка задачи суммарного запаздывания для одного прибора

5.2 Алгоритмы построения оптимальных расписаний, основанные на "декомпозиционных" свойствах задачи.

5.3 Построение оптимальных расписаний в случае фиксированного количества запаздывающих требований.

5.4 Канонические примеры задачи 1|| J^Tj.

5.4.1 Задача ЧЁТНО-НЕЧЁТНОЕ РАЗБИЕНИЕ (ЧНР).

5.4.2 Канонические DL-примеры задачи l|j

5.4.3 Канонические LG-примеры задачи

5.4.4 Свойства канонических LG примеров задачи

5.5 Трудоёмкость алгоритмов

5.5.1 Канонические DL-примеры задачи

5.5.2 Трудоёмкость алгоритмов для канонических DL-примеров

5.5.3 Трудоёмкость алгоритмов решения задач случая BF.

5.6 Оценки SPT расписаний.

5.6.1 Первая оценка.

5.6.2 Вторая оценка.

5.6.3 Задача построения набора требований с заданным оптимальным значением целевой функции.

5.7 Результаты экспериментальных исследований.

6 Полиномиально и псевдополиномиально разрешимые случаи задачи 1||£2)

6.1 Свойства оптимальных расписаний.

6.2 Подход к решению задачи

6.3 Алгоритмы решения задачи 1 || £7}.

6.3.1 Алгоритм В

6.3.2 Алгоритм В-к

6.3.3 Алгоритм С

6.3.4 Алгоритм В-п.

7 Исследование свойств и приложения алгоритма В

7.1 Свойство В-1.

7.2 Алгоритм решения задачи РАЗБИЕНИЕ.

7.2.1 Постановка и полиномиальная сводимость задач разбиения

7.2.2 Алгоритм В-1 -канонический.

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

8 Графический подход к решению задач комбинаторной оптимизации

8.1 Графический алгоритм для задачи РАЗБИЕНИЕ.

8.1.1 Идея графического алгоритма.

8.1.2 Сокращение рассматриваемых интервалов

8.1.3 Пример задачи РАЗБИЕНИЕ.

8.1.4 Трудоёмкость алгоритма.

8.1.5 Экспериментальная оценка трудоёмкости алгоритма.

8.2 Графический подход для задачи одномерный РАНЕЦ (0 — 1 knapsack)

8.2.1 Алгоритм динамического программирования для задачи РАНЕЦ

8.2.2 Графический подход.

8.2.3 Эффективность графического алгоритма.

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

Люди на протяжении всей жизни сталкиваются с проблемами составления расписаний. В обычной жизни эти проблемы решаются интуитивно. Но даже на обыденном уровне человек исполняет алгоритмы, пусть даже не осознавая этого. Часто мы планируем наши действия в порядке возрастания крайних сроков исполнения работ. Например, студенты во время экзаменационной сессии учат предмет с наименьшим директивным сроком (ближайший по дате сдачи экзамен), тем самым они минимизируют максимальное временное смещение. Так как лучше получить на экзаменах три четвёрки, чем две пятерки и одну тройку,— стипендии не будет. Для решения бытовых вопросов применение интуитивного подхода оказывается достаточно. Развивающаяся стремительными темпами автоматизация производства и неуклонно увеличивающиеся его масштабы ставят перед научным сообществом всё более и более трудные задачи разработки алгоритмов составления расписаний.

Теория расписаний является одним из разделов исследования операций. Термин "теория расписаний" предложил Р. Беллман в 1956 году [84]. Методы и алгоритмы решения задач теории расписаний применяются для решения задач комбинаторной оптимизации.

Диссертационная работа посвящена исследованию iVP-трудных задач теории расписаний для одного и нескольких приборов, а также задач РАЗ

БИЕНИЕ и РАНЕЦ. Важным является разработка новых математических методов и эффективных алгоритмов решения этих задач.

Данное направление в науке, получившее название "теория расписанийберёт свое начало с известной работы в данной области Генри Гантта 1903 г. (Gantt H.L. [117]), предложившего то, что сегодня называют диаграммами Гантта, которые встречаются во многих работах по теории расписаний, в том числе и в данной работе. С 50-х годов 20-го века началось активное теоретическое исследование задач теории расписаний, следует отметить работы Джонсона (Johnson [131]), Джексона (Jackson [129]) и Смита (Smith [197]), а также монографии [12, 61].

Одним из главных вопросов нового направления была классификация задач и установление их сложности. В настоящее время наиболее устоявшаяся на нынешний день классификация задач теории расписаний была предложена Грэхэмом и др. (Graham at al. [121]). Относительно быстро была установлена сложность большого числа задач. Достаточно полные обзоры по задачам теории расписаний и их сложности представлены в работах Гэ-ри и Джонсона (Garey, Johnson [7]), Ленстры и др. (Lenstra et al. [162]), Лоулера и др. (Lawler et al. [142]), Танаева и др. [61, 62, 63], Брукера и ДР. [95, 96].

Рассмотрим постановку задачи теории расписаний. Множество требований N = {1,2,.,п} должно быть обслужено без прерываний на одном или нескольких приборах Mi,i = 1 ,.,m, которые могут обслуживать не более одного требования в каждый момент времени. Время обслуживания требования j Е N на приборе Mi обозначается как Pji,Pji > 0. Момент, когда требование j становится доступным для обслуживания, задаётся временем поступления rj. Требование j может иметь директивный срок dj (время, до которого желательно завершить обслуживание требования), а также вес Wj (значимость, важность требования). Между требованиями могут быть заданы отношения предшествования в виде ациклического ориентированного графа G. В подавляющем большинстве задач теории расписаний целью является построение оптимального расписания по определённому критерию или совокупности критериев. Для представления различных критериев нам необходимы следующие определения. Момент окончания обслуживания требования j при расписании тг будем обозначать через Cj(тг). Определим L^k) = Cj(тг) — dj как временное смещение требования j при расписании тг, a Tj{тг) = шах{0, Lj(tt)} ~ как его запаздывание. Uj(ir) обозначает запаздывает ли требование j при расписании тг или нет: Uj(тг) = 1, если j запаздывает (Cj(тг) > dj), иначе Uj(тг) = О (требование j обслуживается вовремя). Классическими критериями в задачах теории расписаний являются: Стах — минимизация максимального времени окончания обслуживания (задача на быстродействие); Lm3X — минимизация максимального временного смещения; ^ Tj — минимизация суммарного запаздывания; J^WjUj — минимизация взвешенного числа запаздывающих требований. Заметим, что данные критерии являются регулярными, т.е. данные функции являются неубывающими по отношений к моментам окончания обслуживания требований. При наличии регулярного критерия мы можем ограничиться рассмотрением только ранних расписаний, без искусственных простоев приборов.

Через TTj будем обозначать перестановку (расписание) из элементов множества N, обслуживаемых на приборе Mi, i ~ 1,., m, множество требований в расписании щ обозначим {щ} С JV, а через 7г = jj™ х тг,-, {тга} П!71"/?} = 0, если а Ф (3, расписание для всего множества требований N = {тг}. Рассматриваются только допустимые расписания, удовлетворяющие отношениям предшествования. Для любого ациклического графа G множество допустимых расписаний не пусто. Момент окончания обслуживания требования j на приборе М( при расписании 7Г определяется как

Cj(7г) = max{r;-, max С* (7г), max Ck(щ)} + ри, keNj {k->j)ni где Nj — множество требований предшествующих требованию j, согласно графу G, и (к —> j)n. требования, согласно расписанию щ на приборе Mi, предшествующих обслуживанию требования j Е {^i}- Предполагается, что для пустого расписания С&(0) = г^ +ры для всех требований к, для которых нет предшествующих требований, при обслуживании на приборе Mi. Множество расписаний обслуживания требований множества N, допустимых относительно графа предшествования G, будем обозначать через П (N).

Если обслуживание требования i предшествует обслуживанию требования j, i,j G N, при расписании тг, то это будем обозначать через (г j)n или г A- j, чтобы "не перегружать" нижний индекс.

Для представления задач построения оптимальных расписаний обслуживания требований множества N, рассмотренных в данной работе, мы будем использовать обозначение а\/3\у [121]. Первое поле а описывает обслуживающую систему: Р - параллельные идентичные приборы; Q - параллельные приборы разной производительности; R - параллельные различные приборы; F - flow—shop - каждое требование должно быть обслужено каждым из приборов множества М = {1,., т} в порядке 1,., т. Во втором поле (3 описываются характеристики требований и отношения предшествования между ними: - заданы моменты поступления требований на обслуживание; pj = р - все требования имеют одинаковые продолжительности обслуживания; ргес - между требованиями заданы отношения предшествования. Третье поле 7 описывает критерий задачи, который состоит в отыскании допустимого (относительно графа предшествования) расписания, минимизирующего целевой функционал.

Отметим, что подавляющее большинство исследованных задач теории расписаний являются iVP-трудными. Несмотря на это, практика требует решение таких задач. Для этого существует несколько подходов.

Первым подходом является разработка полиномиальных эвристических алгоритмов. Для многих эвристических алгоритмов были найдены оценки погрешности получаемого решения. Такие алгоритмы называются приближёнными [15, 56]. Существуют приближённые алгоритмы, гарантирующие как относительную погрешность [9, 191], так и абсолютную погрешность [59]. Некоторые iVP-трудные задачи допускают существование так называемой аппроксимациопной схемы. В рамках данной схемы можно найти приближённое решение с относительной погрешностью не более любого заданного значения е > 0 за время, полиномиально зависящее от 1/е и от размера входной информации задачи,— вполне полиномиальная аппроксимационная схема (FPTAS). Для задач теории расписаний такие схемы разработали, например, Ковалёв [И], Алон и др. (Alon et al. [72]), Мастролилли (Mastrolilli [166]), Севастьянов и Вёгингер (Sevastia-nov, Woeginger [192]. Для задач, не имеющих аппроксимациопной схемы, большое значение имеет установление предельного значения е, для которого возможно нахождения ^-приближённого решения за полиномиальное время,— полиномиальная аппроксимационная схема (PTAS).

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

Точным методам решения iVP-сложных задач также уделено немалое внимание в работах по теории расписаний. Наибольшее распространение получили методы сокращённого перебора, также называемые методами ветвей и границ [13, 60, 90, 98, 137]. Для сокращения перебора вычисляются нижние оценки целевой функции (в случае её минимизации) и используются комбинаторные свойства задач. Также для решения задач теории расписаний широко применяется метод динамического программирования [1, 7, 56, 57, 95,133].

Часто задачи теории расписаний могут быть сформулированы как задачи целочисленного линейного программирования. Решению таких задач посвящены, например, работы [69, 70, 182, 198].

В последнее время широкое распространение получил метод программирования в ограничениях (ПвО, в англоязычной литературе - Constraint Programming). Одной из областей его успешного применения является теория расписаний [81].

Некоторые сложные задачи теории расписаний могут быть оптимально решены с помощью алгоритмов, использующих элементы сразу нескольких методов. Одно из их названий — "гибридные алгоритмы" [14, 130]. На данный момент данное направление, на наш взгляд, является одним из перспективных.

Цель работы

Целыо работы является разработка новых алгоритмов, как приближённых, так и точных алгоритмов сокращённого перебора, для решения NP-трудных задач теории расписаний как для одного, так и для нескольких приборов: 1 | rj | Lmax,Cmax; 1 | rj | 1 II E^'i {P,R,Q,F} I prec,rj | {-^max, Cmax}, а также алгоритмов решения классических задач РАЗБИЕНИЕ и РАНЕЦ. Кроме того, важным является введение метрики для задач теории расписаний минимизации максимального временного смещения.

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

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

Научная новизна

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

Предложена новая схема нахождения приближённого решения задач теории расписаний, состоящая из двух этапов. На первом этапе, решая задачу линейного программирования, находится такое изменение исходных параметров примера A (rf,pfi,df\j G N,i G М), чтобы полученный пример В с параметрами требований (rf,pfi,df\j G N,i G М) принадлежал заданному полиномиально/псевдополиномиалыю разрешимому классу примеров исходной iVP-трудной задачи и был на минимальном расстоянии от примера А в метрике р. На втором этапе для решения примера В используется уже известный для данного класса примеров полиномиальный/псевдополиномиальный алгоритм, а затем найденную им оптимальную перестановку требований применим к примеру А. Абсолютная погрешность такого решения не будет превосходить расстояния р(А, В) между примерами. Данный подход позволяет находить эффективные нижние оценки целевой функции, которые можно использовать в методах сокращённого перебора для оптимального решения задачи.

Поставлена и решена задача, в некотором смысле "двойственная" к задаче 1 | Tj | /max при произвольных неубывающих функциях штрафа, трудоёмкость алгоритма 0(п2) операций. Решение данной задачи является оценкой снизу для исходной ./VP-трудной задачи 1 | rj | /тах и может быть использована в алгоритмах сокращённого перебора.

Для ./VP-трудной задачи 1 || ^Tj, когда параметры требований удовлетворяют ограничениям р\ > р2 > . > рп, d\ < d,2 < . < dn, построен псевдополиномиальный алгоритм трудоёмкости 0(n2YlPj) операций.

Предложена графическая реализация метода динамического программирования, на основе которой построены алгоритмы решения задач РАЗБИЕНИЕ и РАНЕЦ, показавшие лучшую экспериментальную эффективность по сравнению с представленными в научной литературе. Алгоритмы позволяют решать примеры с нецелочисленными и отрицательными значениями параметров.

Теоретическая и практическая значимость

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

Структура и обзор результатов диссертации

В разделе 1.1 первой главы рассматриваются постановки задач минимизации максимального временного смещения (Lmax), дан краткий исторический обзор задач, приведены основные результаты, существующие в литературе. В разделе 1.2 вводятся обозначения и определения, которые используются далее в работе. В разделе 1.3 формулируется и доказывается теорема об абсолютной погрешности [28].

Теорема 0.1 Пусть А= {G,(rf,pf,df)\j eN}uB = {G, (rf,pf,df)\ j €

N} (с идентичным графом предшествования G) - два примера NP-трудной задачи Р \ prec, rj | Ьтгх, тогда

LAmax(*B)-L^A)<p(A,B), где 7Г^,7ГВ - оптимальные расписания примеров А и В, р(А, В) = рг(А, В) + pd(A, В) + рр(А, В),

Рг(А, В) = ma xjeN{rf - rf} - minjeN{rf - rf}, Pd{A, В) = maxjeN{df - df} - minjeN{df - df}, pP(AB) = j:jeN\pf-pf\.

Мы можем использовать оптимальное расписание примера В для решения исходного примера А. Если пример В принадлежит некоторому полино-миально/псевдополиномиально разрешимому подмножеству примеров, то необходимо найти такой пример из этого подмножества, до которого расстояние р(А, В) было бы минимальным. Искомое оптимальное значение будет принадлежать интервалу ах(тгл) £ [L^J^8) ~ р(Л, В), LiJjtB)].

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

XR + YP + ZD <Н, где R = (rh.,rn)T, Р = (.ph.,pn)T, D = (dh.,dn)T, и X,Y, Z - матрицы размерности к х п, a, Н = (h\,.,hk)T - fc-мерный вектор (верхний индекс Т обозначает операцию транспонирования). Затем в этом классе примеров находим пример В с минимальным расстоянием р(А, В) до исходного примера А, решая следующую задачу xd - yd + xr - yr) + Y^jeN xPj —> min yd < df -df < xd, j = l,.,n, Уг < rf - rf <xr, j = 1,., n, -rf <pf-pf < rf, j = l,.,n,

XRB + YPB + ZDB < H. Задача линейного программирования с Sn + 4 + п переменными {rf,pf, df,j = l,.,n,u xd, yd, xr, уг, и rf, j = 1,., n) и 7 n + k неравенствами иногда может быть решена за полиномиальное (от п) операций, учитывая специфику ограничений задачи. Для всех известных полиномиаль-но/псевдополиномиально разрешимых случаев задачи Р | prec^rj | Lmax количество ограничений к = 0(п).

Рассмотрим совокупность примеров задачи Р\ргес, Г{\Ьтах с количеством требований п, количеством приборов т и ориентированным графом предшествования G. Данная совокупность примеров образует Зп-мерное линейное пространство (3п параметров: Tj,pj,dj,j = 1,п). Два примера А = {G, (rf,pf,df)\j £ N} и В = {G, (:rf,pf,df)\j G N] будем называть эквивалентными, если существуют константы с? и г, что df = df + d, rf — rf+r,pf = pf, V; E N. Полученное семейство классов эквивалентности является (3п — 2)-мерным линейным пространством, которое обозначим через Сп. Будем говорить, что пример А принадлежит классу Сп, если выполняется условие r\ = d\ = 0. Несложно показать, что у эквивалентных примеров совпадают множества оптимальных расписаний. На пространстве классов эквивалеитности примеров рассмотрим следующий функционал

VA е Сп, <р(А) = maxrf - minrf + max df - min df + V \pf\ > °< v ' jeN 3 jeN 3 jeN J jeN 3 ^ 3 jGiv

Данный функционал удовлетворяет трём свойствам нормы: р(А) = 0 Л = 0] <р(аА) = a<p(A);ip(A + В) < <р(А) + <р(В).

Таким образом, Сп является (3п — 2)-мерным линейным нормированным пространством с нормой ЦАЦ = <р(А).

Теорема 0.2 [28] Функция р(А,В) = \\А — ВЦ удовлетворяет свойствам нормированной метрики в (3п — 2)-мерном линейном пространстве параметров требований {{fj,Pj,dj)\j Е N}.

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

Теорема 0.3 Пусть А = {G, (rf,pf,df)\j tN}uB = {G, {rf,pf,df)\j 6 N} (с идентичным графом предшествования G) два примера, тогда для любого приближённого расписания 7f верно

0 < LiJW) - liaI(nA) < 5B(W) + р(А, В), где 5в(ж) = LBaI(lf) - !&,(**).

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

Во второй главе представлены новые полиномиально и псевдополино-миально разрешимые случаи iVF-трудной в сильном смысле задачи l\rj\Lmax

В разделе 2.1 рассмотрен случай [23, 27, 47], когда параметры требований удовлетворяют следующим ограничениям: di< . <dn; d\ - ri - pi > . > dn - rn - pn.

Данным ограничениям соответствует случай, когда dj = rj + pj + z, j = 1, — , n, где z - константа, т.е. когда все требования имеют одинаковый запас времени до своего директивного срока. Алгоритмом [27] за 0{пъ log п) операций может быть найдено Парето-оптимальное множество (по критериям Lmax и Стах), состоящее не более чем из п расписаний, решение общей двукритериальной задачи l|r,-|L maxi Стпах ■

Теорема 0.4 [46, 4^} Для любого примера А задачи 1 | rj | Lmax, не принадлежащего исследуемому классу, и для любого примера С, наследующего длительности обслуоюивания примера А и принадлежащего данному классу, справедлива оценка расстояния между А и С: р(А, С) > pL(A) = maxmin{df - df, (df - rf - pf) - (df - rf - pf)}. i,j£N J j j j

Оценка достигается на некотором примере С, который может быть найден за время O(nlogn).

Кроме того, был рассмотрен полиномиально разрешимый случай Хоге-вена [126]: maXk£N{dk~rk—Pk} < dj — rj, Vj € N. Оптимальное расписание находится за 0(п2 log п) операций.

Теорема 0.5 Для любого примера А задачи 1|rj\Lmax, не принадлежащего классу Хогевена, и для любого примера С, наследующего длительности обслуживания примера А и принадлежащего классу Хогевена, справедлива оценка расстояния между А и С: р(А, С) > рн(А) = max{j/ - rf - pf - df + rf}. ijGiv

Оценка достигается на некотором примере С, который может быть найден за время 0(п).

Для более сложного iVP-трудного подслучая задачи l\rj\Lmax, когда параметры требований удовлетворяют ограничениям: d\ < с?2 < • ■ • < dn; ri>r2>.>rn]

Tj,pj,dj е 6 N, предлагается псевдополиномиальный алгоритм решения [52, 55] трудоёмкоп сти 0(п2Р+пртахР) операций, где Р = max{rmax, + Е Pj-max{rmin, t}, j=l rmax = maxr,-, rmin = minr,-, pm3X = maxpj, a t- момент времени, с которого jeN jeN jeN прибор готов начать обслуживать требования множества N.

Для получения нижних оценок целевой функции был также использован следующий подход. Рассмотрим общую постановку А^Р-трудной задачи

Д* = min тах4(С^(тг)), ттеп(лг) k=\,п где fjk(Cjk(7г))- произвольные неубывающие функции штрафа. Решим задачу нахождения величины v*\ v* = max min /,v(C7-.(тг)). k=T-H тгепсN)JJkK JkK

Теорема 0.6 [18, 23] Для NP-трудной задачи 1|г;-|/тах с произвольными неубывающими функциями штрафа fj{t),Vj £ N, верно v* < ц* и величина и* может быть найдена за 0(п?) операций.

Третья глава диссертации посвящена алгоритмам оптимального решения задачи 1 | | Ьтгх. В разделе 3.1 рассмотрены существующие подходы к решению задачи, такие как алгоритм Карлье [98] и метод программирования в ограничениях [81] (ПвО). Данный метод близок к методу ветвей и границ. Отличие заключается в том, что для сокращения перебора в ПвО используется пропагация ограничений, которая удаляет несовместимые значения из множеств допустимых значений переменных.

В разделе 3.2 предлагаются два алгоритма оптимального решения задачи 1 | rj | Lmax. Первый алгоритм построен по методу ПвО. На каждом шаге алгоритма для исходной задачи решается задача распознавания с помощью метода ПвО, в котором используется предложенное нами правило ветвления, основанное на следующей теореме.

Теорема 0.7 Пусть построено расписание Шраге [185] па и требования пронумерованы в том порядке, в котором они упорядочены в ка. Пусть Ь £ N - наименьший номер, для которого Ьь(па) = Lmax(i:(T), и а € N -наибольший такой номер, что а <Ь и

СаЮ -Ра - min rj < Lb{7Ta) - UB, a<j<b где UВ < Ьтах(тга), UB - верхняя оценка оптимального решения. Примем S = {а,. ,Ь}, тогда:

• если не существует такого требования с £ S, что dc > db, то не существует расписания с Lmax меньшим, чем UB;

• если с £ S - последнее требование с директивным сроком dc > db, то в любом расписании к', что Lmax(it') < UB, выполняется либо (с -» J)n', либо (J —»■ где J = {с + 1,., Ь}.

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

В разделе 3.3 приводятся результаты экспериментального сравнения точных алгоритмов решения задачи 1 | rj j Lmax, предложенных в работе, и подходов, существующих в литературе.

В разделе 3.4 рассматривается вариант распознавания задачи 1 | ry | Lmax. Назовем расписание 7г допустимым по отношению к константе I/, если Lmax(n) < L'. Множество требований S допустимо по отношению к константе L', если существует допустимое расписание 7Г G П(5), и недопустимо, если не существует такого расписания. В рассматриваемом варианте задачи требуется определить допустимо ли множество требований N по отношению к заданной константе V. Если N допустимо, то необходимо найти допустимое расписание. Если же N недопустимо, то требуется найти как можно меньшее недопустимое подмножество требований из множества N. Для данного варианта задачи предлагается алгоритм, который является эвристическим в том смысле, что он находит некоторое недопустимое подмножество требований S С N, не обязательно минимальное, когда множество требование N недопустимо. В тоже время, алгоритм точно определяет, допустимо ли множество требование N. Правило ветвления алгоритма основано на следующей теореме.

Теорема 0.8 Пусть Ьтах(ка) > L' и требования пронумерованы в том порядке, в котором они упорядочены в 7га, Ь G N — наименьший номер, для которого Ьь(ла) > 11, и а G N - наибольший номер, что а <Ь и

Са(па) - Ра- min Tj < Lbtf) - L', jes где S = {а,. ,b}. Тогда:

• если не существует такого требования с Е S, что dc > db, то множество требований S недопустимо по отношению к L';

• если с G S - последнее требование с директивным сроком dc > db, и существует допустимое расписание тг', то выполняется либо (с —> J)ni, либо (J -> c)ni, где J = {с + 1,., Ь].

Отличительной чертой модифицированного алгоритма Карлье является способ построения недопустимого подмножества требований в случае, если алгоритм не нашёл допустимого расписания. На каждом узле дерева поиска, где не происходит ветвления, согласно теореме 0.8, мы располагаем подмножеством S, недопустимым для задачи с текущими параметрами требований. Данное подмножество "передаётся родительскому" узлу дерева поиска. Способ построения недопустимого подмножества для узла, имеющего "дочерние" узлы, обоснован в теореме.

Теорема 0.9 Пусть при любом допустимом расписании тг' £ n(iV) требование с £ N обслуживается до или после всех требований множества J С N, S' С N - недопустимое множество требований, когда (с —> J a S" С N - недопустимое подмножество, когда (J —> с)ж/. Тогда:

• если с £ S' (с £ S"), то мноэюество S' (S") недопустимо;

• если с € 5' и с G S", то множество S = J U S' U S" недопустимо.

В четвёртой главе диссертации предлагается точный алгоритм решения задачи 1 | rj | Алгоритм построен по "гибридному" методу [14], который представлен в разделе 4.1.

В последующих разделах задача 1 \ rj \ формулируется как задача целочисленного линейного программирования (ЦЛП) и решается методом отсечения и ветвления. Пусть булева переменная Xj принимает значение 1, если требование j £ N обслуживается вовремя и 0 - если требование j £ N запаздывает.

Wj( 1 — Xj) —> min jeN

J Hd{x), disjunctive^), ze{o,i}n.

Ограничение disjunctive^) выполняется тогда и только тогда, когда множество требований J = {j : Xj — 1} может быть обслужено на одном приборе без прерываний и с соблюдением времён поступления и директивных сроков, — релаксация ограничения disjunctive. В разделе 4.4 рассматриваются различные варианты релаксации.

Лемма 0.1 Пусть для двух требований i,j £ N выполняется гг- < dj. Если вектор х удовлетворяет ограничению disjunctive, тогда х также удовлетворяет ограничению1

Pmm[dj - п, (pi - т&х{ац, (3ji})+]xt < dj - rf, leN где an = (rf - п)+ и fyi = (d[ - dj)+.

Раздел 4.5 посвящён вопросу проверки на допустимость решения х задачи ЦЛП, а также вопросу построения отсечений в случае недопустимости х. Алгоритм выполняется для множества требований J = {j : Xj = 1}, и в случае его недопустимости находится недопустимое подмножество S С J, для которого строится ограничение

5> <1*1-1jeS

Следующее утверждение представляет отсечения второго вида.

1 (*)+ = {Zlol; (*)- = {; W = (*)+ + (*)

Лемма 0.2 Пусть заданы такие множество требований О, С N и требование к £ N \ что к может быть обслужено только с момента времени rf, rf > rk, если все требования из Q выполняются вовремя. Положим такэюе afk = (г? - п)+. Тогда вектор х, удовлетворяющий ограничению disjunctive, удовлетворяет неравенству

Е min [dj ~ (Pi ~ max{a$, M)+] xl+ ieN\n\{k} pk - Pjk)+xk < dj - rf + (rf - rk){\ xo), oen для каждого требования j G N\Q, dj > rf.

В работе предлагается алгоритм сложности 0(п3) операций, который проверяет существование отсечения найденного вида. В разделе 4.6 рассматриваются различные варианты предложенного алгоритма отсечения и ветвления. В заключительном разделе 4.7 представлены результаты экспериментального исследования предложенного алгоритма на множестве общедоступных тестовых примеров. Показанно, что разработанный алгоритм для задачи 1 | rj \ является более эффективным, чем лучший алгоритм для данной задачи, существующий в литературе [173].

В пятой главе рассматриваются комбинаторные свойства NP-трудной в обычном смысле [110] задачи минимизации суммарного запаздывания для одного прибора 1 11 ^Tj. Получены свойства оптимальных расписаний, на основе которых построены алгоритмы решения задачи. Построены оценки оптимального значения целевой функции. В разделе 5.1 приводится постановка рассматриваемой задачи, вводятся необходимые понятия и определения.

В разделе 5.2 приводятся алгоритмы решения рассматриваемой задачи, основанные на "декомпозиционных" свойствах задачи. Одно из первых "декомпозиционных" свойств задачи было получено Лоулером, который предложил алгоритм решения задачи трудоёмкости 0(n4J2Pj) операций [145].

Перенумеруем требования множества N в порядке неубывания директивных сроков d\ < . < dn (при этом, если dj = dj+i, то pj < pj+i, j = 1,2,., n — 1). Пусть j* будет требованием с максимальной продолжительностью (если таких требований несколько, то выберем требование с наибольшим номером), т.е. j* = max{j G N : pj = maxpf}. Пусть ieN

Sk = to + к = 1,2,., n, и S = Sn.

Через L(I) обозначим множество индексов к > j*, для которых выполнены неравенства dj +pj < Sk {j = j* + 1,., к) и Sk < dk+i, доопределив dn+1 := +oo. Множество L(I) будем называть миоэюеством подходящих позиций для требования j*.

Теорема 0.10 [25] Для любого примера I множество подходящих позиций L(I) для требования j* не пусто и существует оптимальное расписание 7г* G П*(/), при котором требование j* обслуживается на месте к G L(I). При этом для подходящего места к выполняется

U Л- для j G {1,2, .,&} \ {j*} и (j* для j £ {к + 1,., п}.

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

В разделе 5.3 рассматриваются свойства оптимальных расписаний и предлагается алгоритм решения примеров I в случае, когда при любом расписании тг Е П(/) запаздывает одно и тоже количество требований т (О < т < п). При этом запаздывающие требования упорядочены в конце расписания 7г (т.е. расписание тг можно представить в виде тг — (щ,^), где подрасписание тг2 содержит все m запаздывающих требований). Через D(7r) обозначим множество запаздывающих требований при расписании 7г. В рассматриваемом случае верны следующие утверждения.

Лемма 0.3 При любом оптимальном расписании тг* требования множества D(i{*) обслуживаются в SPT порядке2.

Далее, перенумеруем требования примера I в порядке невозрастания продолжительиостей обслуживания pi > P2 > . > рп, при этом, если Pj = Pj+i (j = 1,.,п-1), то dj> dj+i.

Лемма 0.4 Существует оптимальное расписание 7г* такое, что если для некоторого к £ N выполняется к Е D[it*), то (j —> к)п* для всех требований j € {к + 1,., п}.

2SPT - Shortest Processing Time. Расписание 7Г называется SPT-расписанием, если требования упорядочены при расписании 7Г в порядке неубывания продолжительиостей обслуживания.

Найденные свойства позволяют построить алгоритм нахождения оптимального расписания за 0(п3) операций (алгоритм FA). Построение оптимального расписания алгоритмом FA сводится к обходу дерева, каждая ветка которого соответствует некоторому порядку обслуживания запаздывающих требований.

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

Перенумеруем требования множества N в порядке неубывания продол-жителыюстей обслуживания, т.е. pi < < . < рп. SPT-расписание (1,2,., гг) будем обозначать через 7rspt. Рассмотрим пример задачи / = ({pj,dj}jeN,to) с оптимальным значением целевой функции F*(I). Пусть dmin — minjGj/v dj и dmax = тах;-едг dj. Выберем величины С и 5 такими, что dmin <с < dmax и 5 = max{dmax - С, С - dm-m}. Рассмотрим пример V — ({pj, d'j = Cjj'eiVj ^о)

Теорема 0.11 (первая оценка). Для выбранных значений С и 5 верно неравенство

F\I)~F\I')\<n5 (2-2! + !)+*.

Для формулировки второй оценки рассмотрим функцию п j j=1 i=1

Значение этой функции в точке t равно оптимальному значению суммарного запаздывания для параметрического примера I(t) = ({pj, to), при

3 Относительная погрешность значения суммарного запаздывания при EDD-расписаиии (расписании, требования при котором упорядочены в порядке невозрастания значений директивных сроков) установлена Лоулером в 1977 г. котором директивные сроки всех требований равны t. Функция / является кусочно-линейной, невозрастающей, непрерывной и неотрицательной функцией, принимающей значения 0 для всех t > to + YljeNPj

Теорема 0.12 (вторая оценка) Для любого примера I справедливы неравенства f(dmax) < F*(I) < /(4iin)

Раздел 5.5 посвящён результатам экспериментальных исследований задачи.

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

В шестой главе диссертации рассматривается частный iVP-трудный случай [6] задачи минимизации суммарного запаздывания

Р1>Р2>--->Рп, d\ < d2 < . < dn.

Предлагается подход решения задачи в этом случае, при котором исходное множество требований N разбивается на к таких непересекающихся подмножеств Ml, М2, • • •, Mt, ЧТО iV = Ml U М2 и • • • U «Мк И тах^етИа |d{-dj| < minj£MaPji аг = 1,., к, а затем на основе этого разбиения строится оптимальное расписание.

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

Лемма 0.5 Существует оптимальное расписание к*, при котором выполняется либо (к —> i)^*, либо (j —»• к)п* для любой тройки требований i,j, k Е N, что \d{ — dj\ < min{pi,pj}, к < mm{i,j} и (i -)•

Лемма 0.6 Существует оптимальное расписание 7Г*; при котором выполняется либо (к —» j)t*, либо ((к + 1) к)п* для любой пары требований к, j £ N, к < j.

На первом этапе решения задачи производится разбиение множества требований N па непересекающиеся подмножества М\,М.2, • • • ,-Мк, такие, что разность между максимальным и минимальным директивными сроками требований каждого подмножества не превышает величины минимальной продолжительности требований из этого подмножества4.

Определим параметрический пример Ik(t) = {{pj, dj(t)}je^k, 0), где = {k, k+l,., n} и dj(t) = dj—dn-{-t—tQ. Ik(t) - это пример исследуемой задачи обслуживания требований множества с моментом начала обслуживания равным нулю и директивными сроками dj(t), линейно зависящими от параметра t.

Идея предлагаемого подхода заключается в построении оптимальных расписаний 7для примеров Ih{t), к = тг, п — 1,., 1, для всех целочисленных точек t Е [to] й?п]. Расписания !(£) строятся на основе построенных на предыдущих шагах расписаний I > k,t' Е \tQ\d^[.

Согласно леммам, при построении оптимального расписания для исходного примера I можно исключить из рассмотрения все расписания 7Г, при которых: a) (г Ч- к -> к < min{i,j}, i,j Е Ма, к Е Мр,(3 < а; b) (jк(к + 1)),, к < j.

4 Такое разбиение множества требований может быть выполнено за 0(тг) операций.

В разделе 6.3 рассматривается случай к = 1, когда параметры требований удовлетворяют условиям:

Р\ > Р2 > • • • > Рп\ di < d-2 < . < dn] k dn-di< pn.

В этом случае при построении оптимального расписания тгl(t) с помощью описанного выше подхода для каждой точки t требуется просмотреть только две позиции для требования к: до всех требований множества Nk+1 и после всех требований этого множества. При обслуживании требования к до всех требований множества Nk+1 получаем расписание (k,irl+1(t — рк)), после всех требований - расписание к). Расписание с наименьшим значением суммарного запаздывания среди двух полученных расписаний будет оптимальным расписанием для примера h{t)- Алгоритм, реализующий данный подход к построению расписания в этом случае, мы назвали алгоритмом В-1.

Теорема 0.13 Алгоритм В-1 находит оптимальное расписание для данного NP-трудного случая за 0(nJ2Pj) операций.

В разделе 6.4 рассматривается случай для произвольного значения к. Приводится описание алгоритма В-к нахождения оптимального расписания в случае (6.1), трудоёмкость алгоритма 0(knJ2Pj) операций.

В разделе 6.5 рассматриваются примеры, параметры требований которых удовлетворяют условиям: d\<d2< . <dn-, < dn - di < 1;

Алгоритм C-l находит оптимальное расписание для данного случая за 0(п2) операций. Отметим, что алгоритм можно использовать для решения примеров в случае, когда в условиях второе неравенство заменено на dn — d\ < НОД (pi,. .,рп).

В разделе 6.6 рассматриваются примеры, параметры требований которых удовлетворяют условиям dj ~ dj-1 > Pj, j = 2,3,., п.

Поскольку pj > 0, \/j £ N, то выполняется d\ < . < dn. Отметим, что этот случай является "предельным" подслучаем, когда количество подмножеств к = п, т.е. каждое подмножество Ма, а = 1,., к, состоит ровно из одного требования.

Показано, что для данного случая задачи существует оптимальное расписание 7г* £ П*(/), при котором требование j* обслуживается на первой позиции из множества L(I). Данное свойство позволяет построить алгоритм В-п решения задачи трудоёмкости 0(п2) операций.

В разделе 6.7 построен алгоритм трудоёмкости 0(п3) операций для случая:

Pi < Р2 < - ■ ■ < Рп, k Pi + d\ < Р2 + d2 < . • • < Р2 +

В седьмой главе диссертации исследуются свойства алгоритма В-1, показано, что данный алгоритм может быть использован для нахождения решения следующих iVP-полных задач разбиения: РАЗБИЕНИЕ, ЧЕТНО-НЕЧЁТНОЕ РАЗБИЕНИЕ (ЧНР), ЧЁТНО-НЕЧЁТНОЕ РАЗБИЕНИЕ С ОГРАНИЧЕНИЯМИ (ОЧНР).

Расписание тг назовем расписанием, обладающим свойством В-1, если для всех требований к £ {1,2,., п — 1} при расписании тг выполняется либо (к -4- j)n, либо (j к)ж для всех j £ {к + 1,., п}.

Множество всех расписаний, обладающих свойством В-1 для примера 7, будем обозначать через Ub-i(I)- Пусть = р| П*(/).

Теорема 0.14 Алгоритм В-1 находит оптимальное расписание примера I задачи 1 || ^Tj тогда и только тогда, когда П^.^/) ф 0.

Раздел 7.2 посвящён классической iVP-полной задаче РАЗБИЕНИЕ, рассматривается схема полиномиального сведения примеров этой задачи к примерам задачи теории расписаний 1 11 ^Ту.

В классической задаче РАЗБИЕНИЕ требуется определить, существует ли такое разбиение множества п целых положительных чисел на два подмножества, что суммы чисел в обоих подмножествах равны. Задача ЧНР представляет собой модификацию задачи РАЗБИЕНИЕ, когда на разбиение множества накладывается ограничение, что соседние числа (первое и второе, третье и четвертое и т. д.) должны оказаться в разных подмножествах. Задача ОЧНР представляет собой задачу ЧНР с дополнительными ограничениями на значения чисел исходного множества.

Показано, что любое (в том числе, и оптимальное) расписание канонического вида обладает свойством В-1. Таким образом, мы можем использовать алгоритм В-1 для нахождения решения канонических примеров задачи 1 11 £ Tj и, соответственно, задач РАЗБИЕНИЕ, ЧНР, ОЧНР. С учётом особенностей канонических примеров предложен алгоритм В-1 -канонический, трудоёмкость которого не хуже известного алгоритма из книги Гэри и Джонсона [7] для задачи РАЗБИЕНИЕ.

В разделе 7.3 приводится модификация алгоритма В-1, которая позволяет снизить трудоёмкость решения примеров задачи 1 11 ^Tj. Идея алгоритма В-1-модифицированный заключается в том, что процесс построения оптимального расписания сведён к процессу построения кусочно-линейной функции специального вида. Рассматриваются три операции над функциями: "сдвиг" функции, сложение двух функций и нахождение функции минимума двух функций. Полученные свойства рассматриваемых функций были использованы для построения алгоритма В-1-модифицированный. Преимущество этого алгоритма заключается в том, что при построении решения нет необходимости рассматривать все целочисленные точки интервала t 6 [^0) dri\- Трудоёмкость решения полиномиально зависит от максимального количества точек изменения наклона функций, рассматриваемых в ходе решения. Преимуществом Алгоритма В-1-модифицированный является то, что при масштабировании всех параметров примера, трудоёмкость алгоритма решения не меняется. Также данный алгоритм может быть использован для решения задач 1 11 РАЗБИЕНИЕ, ЧНР и 04-НР с нецелочисленными параметрами.

В восьмой главе рассматривается графическая реализация метода динамического программирования на примерах решения задач РАЗБИЕНИЕ и РАНЕЦ. Проведён сравнительный анализ предлагаемого метода с известными алгоритмами решения этих задач.

Задача РАЗБИЕНИЕ. Задано упорядоченное множество из п положительных целых чисел В = {&i, &2> • • • > К}, > h > ■ •. > Ьп. Требуется разбить множество В, на два подмножества В\ и В2, В\\}В2 = В,В\[\В2 = 0, так, чтобы минимизировать значение:

I ]Сbi ~ S Ь{\ —> min' bjG-Bi he В2

Задача об одномерном РАНЦЕ. f(x) = E"=l °iXi -► тах

Ег=1 aiXi — k Xi € {0,1}, г = 1,. ,n.

Когда С{ = a,i = bi,i = 1,2, .,п, и А = Т0 данные задачи являются эквивалентными.

В разделе 8.1 представлен графический алгоритм для решения задачи РАЗБИЕНИЕ. В алгоритме последовательно на шаге а = 1,2, .,п рассматриваются следующие функции:

2(*) = l Е *}- Е М; bjeB^t-ba) bjeB2{t-ba) т=\ е Е чbjeB^t+ba) bjeB2(t+ba) На каждом шаге а алгоритма B\(t) \JB2(t) = {b\, 62, - - -, ba-i}> Последовательно "добавляется" очередное число Ьа, где а = 1,2,., п, в множество B\{t) или ^(О- В каждой точке t "добавление" числа Ьа выбирается таким образом, чтобы минимизировать значение функции | Yb^B^t) + t ~ Еь^вд bjI- Ha очередном шаге а из функции Fai(t) = | Еь^ВД bj ~ Ylbj<EB2(t) bj|) полученной на предыдущем a — 1 шаге, строится функция min{Fai(* - ba), Fai(f + 6a)} = min^W, F2(*)}, где F0(0 = О, V t. Если F*(t) < F2{t), то B^t) = B^t - ba){J{ba}, иначе B2(t) = ^(i + 6a) (J{6a). Кусочно-линейную функцию Fa(t) можно представить (и хранить) в табличном виде по точкам "излома": ^i", • • •; tma. На промежутке [U — , ^ + fi+12~fi), г = 1,2,., та — 1, кусочно-линейная функция Fa(t) задаётся уравнением Fa(t) = — U\, т.е. график функции пересекает ось t в точке t(. Каждому временному интервалу + '+12 ') соответствует некоторое фиксированное разбиение (Bi; В2), т.е. Bift1) = £i(t2) = Вь Vt1,*2 Е [U - + (аналогично и для Пусть на предыдущем шаге а — 1 получена функция

Fa-i(t), заданная таблично. На шаге а мы рассматриваем две функции Fai(i — ba) и Fa-i(t + ba), заданные двумя таблицами в точках "излома": к — ba, ii — ba, . - U — ba, ., £max — ba и ^o + h + ba, ■ • ■, U + ba, .,

В разделе 8.2 показано сокращение рассматриваемых интервалов. Учитывая, что на шаге п нам требуется вычислить значение целевой функции и найти разбиение лишь в точке t — 0, то на шаге п — 1 нам достаточно рассчитать значения в точках t е [—Ьп,Ьп]. Аналогично на шаге п — 2 достаточно рассмотреть интервал [—bn — 6ni, bn + 6ni] и т.д.

Следовательно, на каждом шаге а достаточно рассматривать интервал [- Л]=а+1 bh Ej=a+1 У > вместо интервала [- bj, EJ= 14

При построении функции Fa(t) рассматриваются только точки t е [-Е? =a+ibj]- Чтобы интервал сокращался максимально быстро необходимо упорядочить bj по невозрастанию. Учитывая, что функция Fa(t),a = 1,2, .,7г, является чётной, поэтому достаточно хранить "половину" таблицы. Кроме того, следует отметить, что при "масштабировании с небольшим изменением параметров" примера, т.е. когда b'j = Kbj + £j, где |£j| <С К, К— некоторая достаточно большая положительная константа, j = 1,2, .,п, трудоёмкость алгоритма, построенном на методе динамического программирования [1], составит 0(Kn^2bj) операций, в то время как у графического алгоритма трудоёмкость не изменится. Для алгоритма Balsub [133] с трудоёмкостью 0(nbmax) операций такое "масштабирование" примера также приведёт к увеличению трудоёмкости в К раз. Таким образом, графический алгоритм находит решение за одно и тоже количество операций для всех точек некоторого конуса в п—мерном пространстве, если представить параметры примера как точку (61,62,. ,6П) в п—мерном пространстве. Причём параметры примера могут быть как отрицательными, так и нецелочисленными.

Существуют классы примеров, для которых трудоёмкость графического алгоритма растёт экспоненциально быстро (от п):

1. В = {6Ь62,. X} = {М, М-1, М-2,., 1,1,., 1}. М- достаточно большое число, сумма единиц в примере равна М(М + 1)/2, т.е. п = М + М(М + 1)/2;

2. класс нецелочисленных примеров В = {Ь\, 62,., Ьп}, если не существует такого набора чисел Aj = ±1,г = 1 что выполняется ХА + Л262 + . + А пЬп = 0.

В разделе 8.3 представлена графическая реализация метода динамического программирования решения задачи РАНЕЦ. Также как и для задачи РАЗБИЕНИЕ в ранец последовательно "добавляются предметы". На шаге (а+1) строится график g2(t) из графика ga(t) смещением "наверх" на са+1 и "вправо" на аа+\. График gl(t) полиостью повторяет график ga{t). Следовательно, чтобы построить да+\(t) = max{gl(t),g2(t)} необходимо рассмотреть не более 2та интервалов, образованных точками из множества ftb h, • - • 1 tma, t0 + аа+1, ti + аа+1, .,tma + аа+1}, которые принадлежат интервалу [0, А]. Количество точек не превосходит А для a; Е Z+, г = 1,., п. Параметры задачи могут быть и отрицательными.

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

Основными результатами диссертации являются следующие:

1. Для iVP-трудных задач {Р, R, Q, F}\prec, rj\{Lmax, Cmax} найдены оценки абсолютной погрешности целевой функции. Для этих классов задач введена метрика. Предложена новая схема нахождения приближённого решения данных задач, состоящая из двух этапов. На первом этапе, решая задачу линейного программирования, находится изменение исходных параметров примера A {rf,pfi, df\j € N,i € М), что полученный пример В с параметрами требований € N,i € М) принадлежал известному полиномиально/псевдополиномиально разрешимому классу примеров исходной iVP-трудной задачи и был на минимальном расстоянии от примера А в метрике р. На втором этапе для решения примера В используется уже известный для данного класса примеров полиномиальный/псевдополиномиальный алгоритм, а затем найденную им оптимальную перестановку требований применим к примеру А. Абсолютная погрешность такого решения не будет превосходить расстояния В) между примерами;

2. Для iVP-трудной задачи 1 | rj | Lmax предложен новый точный алгоритм решения на основе методов ветвей и границ и программирования в ограничениях. Найдены новые эффективные нижние оценки оптимального значения целевой функции. Экспериментальное исследования на множестве тестовых примеров показало преимущество (время работы алгоритма и количество ветвлений в дереве поиска существенно меньше) предложенного алгоритма над существующими алгоритмами;

3. Для iVP-трудной задачи 1 | rj | ^ WjUj предложен точный алгоритм отсечения и ветвления. Преимущество (время работы алгоритма и количество ветвлений в дереве поиска) предложенного алгоритма над наилучшим алгоритмом для данной задачи, представленном в литературе, на множестве общедоступных тестовых примеров подтверждено численными экспериментами;

4. Поставлена и решена задача, в некотором смысле "двойственная" к задаче 1 | rj | /тах, трудоёмкость алгоритма 0(п2) операций. Решение данной задачи является оценкой снизу для исходной NP-трудной задачи 1 j rj | /тах и может быть использована в алгоритмах сокращённого перебора;

5. Для ТУР-трудной задачи 1 || доказаны новые свойства оптимальных расписаний NP-трудного частного случая, когда параметры требований удовлетворяют ограничениям р\ > Р2 > . > Pni di < < . < dn, и предложен алгоритм решения этого случая задачи за 0(n2^pj) операций. Выделен один псевдополииомиалыю разрешимый {0(nY^Pj) операций) и два полиномиально (0(п2) операций) разрешимых подслучая этого случая. Получены необходимое и достаточное условия того, что построенный пседополиномиальный алгоритм находит оптимальное решение.

Показано, что любой алгоритм решения задачи 1 || основанный на "декомпозиционных" правилах [201], при решении канонических примеров будет иметь трудоёмкость не менее 0(п22-1) операций;

6. Построены алгоритмы решения задач РАЗБИЕНИЕ и РАНЕЦ, показавшие лучшую экспериментальную эффективность по сравнению с представленными в научной литературе. Алгоритмы позволяют решать примеры с нецелочисленными и отрицательными значениями параметров.

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

Основные результаты диссертации опубликованы в следующих 56 работах: [2], [3], [6], [16]—[55], [116], [148]—[161], [183], [184], в том числе, 8 в центральной печати (из списка ВАКа), четырёх книгах, а также в материалах и тезисах международных, всесоюзных и всероссийских конференций.

В совместных работах автору принадлежат в: [2] - разработка приближённого алгоритма решения задачи P\prec, rj\Cmax; [3] - доказательство полиномиальной разрешимости задачи 1|р; < pj,pi + di < pj + dj\^2Tf, [6], [155] - построение канонического примера задачи 1|| ^Tj и полиномиальное сведение к задаче ЧЁТНО-НЕЧЁТНОЕ РАЗБИЕНИЕ; [31], [32], [46], [50] - компоновка и редактирование текстов; [33]-[42], [116], [156]-[158] - разработка алгоритмов решения задачи 1|[ E^j и методика проведения экспериментов; [43]-[45], [183]-[184] - доказательство утверждений и разработка алгоритмов решения задачи 1\г^\Ьтах и методика проведения экспериментов; [47], [159] - доказательство теоремы об абсолютной погрешности и разработка схемы приближённого решения задачи 1|rj\Lmax; [48], [49] -получение нижних оценок решения задачи P\rj\Cmax; [51] - оценка абсолютной погрешности целевой функции задачи 1|г;-|£тах при модификации директивных сроков требований; [52]-[55], [160] - разработка алгоритмов решения задачи l|rj|Lmax и выделение полиномиально/псевдополиномиально разрешимых случаев задачи; [115] - графический подход решения задач комбинаторной оптимизации; [161] - получение нижних оценок решения задачи l|rj|

Результаты диссертации докладывались и обсуждались на: 4-ом международном конгрессе по промышленной и прикладной математике (Эдинбург, Шотландия, 1999 г.); международных конференциях по оптимизации (Намур, Бельгия, 1998 г., Монтпелье, Франция, 2000 г.); международных семинарах "Дискретная математика и её приложения" (Москва, МГУ, 2001, 2004, 2007 гг.); Российской конференции "Дискретный анализ и исследование операций" (Новосибирск, 2002, 2004 гг.); международных семинарах по методам и алгоритмам для задач календарного планирования и теории расписаний MAPSP (Сиена, Италия, 2003, 2005 гг., Стамбул, Турция, 2007 г.); 3-ей международной конференции "Математические методы и компьютеры в экономике" (Пенза, 1998 г.); международной школе-семинаре "Методы оптимизации и их применение" ( Байкал 1998 г.); научно-исследовательской конференции "Практика использования мини и микро ЭВМ в ГАП механической обработки" (Казань, 1988 г.); симпозиуме "Программное обеспечение решения задач оптимального планирования" (Нарва, Эстония, 1988 г.); конференции "Проблемы теоретической кибернетики" (Иркутск, 1985 г., Казань 2002 г.); международной конференции по исследованию операций (Карлсруэ, Германия, 2006 г.); международной конференции по комбинаторной оптимизации ЕССО XVIII (Минск, Беларусь, 2005 г.); международной конференции ENC'04 (Колима, Мексика, 2004 г.); IFAC симпозиуме по проблемам контроля в производстве INCOM'2006 (Сент-Этьен, Франция, 2006 г.); международном семинаре по сложности многомерных задач (Гои-Конг, Китай, 1999 г.); VI Международной конференции «Дискретные модели в теории управляющих систем» (Москва, МГУ, 2004 г.); 9-ой Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 1999 г.); международной конференции по теории расписаний MISTA'07 (Париж, Франция, 2007 г.); семинарах кафедр прикладной математики и экономической кибернетики Казанского университета (1980-2002 гг.); семинарах математического департамента CICESE (Энсенада, Мексика, 2004 г.); семинарах профессора П. Брукера (Осна-брюкский университет, Германия, 2002, 2003 гг.); семинарах профессора Ф. Баптиста (Эколь Политекник, Полиазье, Франция, 2007 г.); семинаре отдела "Математических проблем распознавания и методов комбинаторного анализа" Вычислительного центра им. А.А. Дородницына Российской академии наук (Москва, 2007 г.).

Благодарности

Считаю своим долгом выразить благодарность: B.C. Танаеву, Е.Г. Лазаревой, Ю.И. Журавлёву, В.К. Леонтьеву, И.Х. Сигалу, Ю.А. Флёрову, Л.С. Иртышёвой, К.В. Рудакову, В.Н. Буркову, Д.А. Новикову, С.В. Севастьянову, М.Я. Ковалёву, Я.М. Шафранскому, Ю.Н. Сотскову, Н.Н. Кузюрину, В.В. Шкурбе, А.А. Сапоженко, М.Н. Вялому, С.П. Тарасову, P.P. Садыко-ву, А.Г. Кварацхелия, P.P. Сираеву, Е.Р. Гафарову, С.А. Скиндереву, А.Н. Черных, Я.И. Заботину, О.Н. Шульгиной, А.Ф. Кадомцевой, Р.Ф. Хабибул-лину, А.А. Корбуту, П. Брукеру (Германия), Ф. Баптисте (Франция), В.

РОССИЙСКАЯ . 41

ГОСУДАРСТВЕННАЯ БИБЛИОТЕКА/

Шварцу (США) за помощь в работе и обсуждение полученных результатов.

Работа выполнена в рамках научной школы академика Ю.И. Журавлёва (грант НШ-5833.2006.1) при частичной финансовой поддержке фондов: РФФИ (Россия), DAAD (Германия), CNRS (Франция), NSC (США).

Заключение

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

Основными результатами диссертации являются следующие:

1. Для NP-трудных задач {Р, R, Qjjprec, rj\{Lmax, Cmax} найдены оценки абсолютной погрешности целевой функции. Для этих классов задач введена метрика. Предложена новая схема нахождения приближённого решения данных задач, состоящая из двух этапов. На первом этапе, решая задачу линейного программирования, находится изменение исходных параметров примера A {rf,pj-, df\j £ N,i G M), что полученный пример В с параметрами требований {rf,pfi, df\j e N,ie м) принадлежал известному полиномиально/псевдополиномиально разрешимому классу примеров исходной iVP-трудной задачи и был на минимальном расстоянии от примера А в метрике р. На втором этапе для решения примера В используется уже известный для данного класса примеров полиномиальный/псевдополиномиальный алгоритм, а затем найденную им оптимальную перестановку требований применим к примеру А. Абсолютная погрешность такого решения не будет превосходить расстояния р(А, В) между примерами;

2. Для iVP-трудной задачи 1 | гj | Lmax предложен новый точный алгоритм решения на основе методов ветвей и границ и программирования в ограничениях. Найдены новые эффективные нижние оценки оптимального значения целевой функции. Экспериментальное исследования на множестве тестовых примеров показало преимущество (время работы алгоритма и количество ветвлений в дереве поиска существенно меньше) предложенного алгоритма над существующими алгоритмами;

3. Для NP-трудной задачи 1 | rj | WjUj предложен точный алгоритм отсечения и ветвления. Преимущество (время работы алгоритма и количество ветвлений в дереве поиска) предложенного алгоритма над наилучшим алгоритмом для данной задачи, представленном в литературе, на множестве общедоступных тестовых примеров подтверждено численными экспериментами;

4. Поставлена и решена задача, в некотором смысле "двойственная" к задаче 1 | гj | /тах, трудоёмкость алгоритма 0(п2) операций. Решение данной задачи является оценкой снизу для исходной NP-трудной задачи 1 | rj | /тах и может быть использована в алгоритмах сокращённого перебора;

5. Для jVP-трудной задачи 1 || доказаны новые свойства оптимальных расписаний iVP-трудного частного случая, когда параметры требований удовлетворяют ограничениям р\ > р2 > . > рп, d\ < d2 < . < dn, и предложен алгоритм решения этого случая задачи за 0(n2Y,Pj) операций. Выделен один псевдополиномиальпо разрешимый (0(nYPj) операций) и два полиномиально (0(п2) операций) разрешимых подслучая этого случая. Получены необходимое и достаточное условия того, что построенный пседополиномиальный алгоритм находит оптимальное решение.

Показано, что любой алгоритм решения задачи 1 || основанный на "декомпозиционных" правилах, при решении канонических примеров будет иметь трудоёмкость не менее 0(п2?"1) операций;

6. Построены алгоритмы решения задач РАЗБИЕНИЕ и РАНЕЦ, показавшие лучшую экспериментальную эффективность по сравнению с представленными в научной литературе. Алгоритмы позволяют решать примеры с нецелочисленными и отрицательными значениями параметров.

Задача 1 | гj | Ьтах является одной из важных комбинаторных задач теории расписаний. Во-первых, она тесно связана с часто встречающейся задачей теории расписаний состоящей в проверке возможности обслуживания заданного множества требований на одном приборе без прерываний и нарушений времен поступления и директивных сроков требований. Можно вспомнить, например, главу 4 данной работы, где последняя задача играла важную роль.

Во-вторых, как уже было упомянуто, решение задачи 1 | гj | Lmax помогает получить неплохие нижние оценки для многих многоприборных как теоретических так и практических задач.

Смеем надеяться, что данный труд внесет свою лепту в изучение этой важной задачи и предложит новые пути ее исследования. Остановимся теперь на основных результатах.

С помощью теоремы об абсолютной погрешности нами были установлены новые свойства оптимальных расписаний примеров задачи. Было показано, что расписание, оптимальное для одного примера, может быть использовано при приближённом решении с гарантированной погрешностью другого примера задачи. Данное свойство позволило нам предложить целое семейство алгоритмов решения задачи. Следует заметить, что до этого только алгоритм Шраге [185] позволял получить за полиномиальное время решение с гарантированной абсолютной погрешностью (которая равняется максимальному времени обслуживания требования [98]).

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

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

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

Наряду с теоретическими, нами также были получены важные результаты с практической точки зрения. Долгое время считалось, что алгоритм Карлье [98] позволяет справляться со всеми примерами проблемы 1 | rj | Lmax встречающимися на практике. Однако, наше исследование показало, что это не так. Предложенная нами модификация алгоритма Карлье намного более эффективна. Данная модификация заключается в использовании алгоритмов " Edge-Finding "известных в программировании в ограничениях. В отличие от оригинального алгоритма, с помощью его модификации были решены все тестовые примеры.

Несмотря на хорошие результаты, предложенный алгоритм точного решения задачи не всегда работает достаточно быстро (особенно на примерах большой размерности). Обычно задача 1 | т* | Ьтах используется в качестве подзадачи, и поэтому ее требуется решить много раз в течение одного алгоритма. Поэтому, даже если каждый пример решается за считанные секунды, это может быть недостаточно эффективно.

Задача 1 | г j \ YjwjUj интересна как в теоретическом так и в практическом плане. Минимизация запаздывающих требований — один из классических критериев в теории расписаний. Этот факт обусловлен большим количеством задач с данной целевой функцией, встречающихся на практике. Наибольший интерес представляют многоприборные задачи. Однако, вариант с одним прибором, рассмотренные в работе, так же важен, так как идеи и подходы для его решения зачастую могут быть обобщены на задачи с несколькими как идентичными так и неоднородными приборами.

Задача 1 j rj | Y, WjUj может быть переформулирована как нахождение допустимого множества требований максимального суммарного веса. Здесь допустимость множества определяется возможностью обслуживания его требований на одном приборе без прерываний и нарушений времен поступления и директивных сроков. Для оптимального решения данной задачи нами был предложен алгоритм ветвей и отсечений основанный на декомпозиции Бендерса формулировки целочисленного линейного программирования. Декомпозиция разбивает задачу на две подзадачи — выбор множества требований и проверку его допустимости. Первая подзадача решается методами целочисленного линейного программирования, для второй используются специализированные комбинаторные алгоритмы и методы программирования в ограничениях. Связь между двумя подзадачами осуществляется при помощи отсечений, генерируемых второй подзадачей и используемых в первой.

Идея такой декомпозиции задачи теории расписаний не нова, см. например [87,130]. Наш вклад в данный подход состоит в следующем. Во-первых, мы предложили дополнить формулировку первой подзадачи ограничениями, которые существенно сокращают число выбранных недопустимых множеств требований. Это позволило также сократить число генерируемых отсечений и, соответственно, время работы алгоритма. Во-вторых, нами были разработаны новые алгоритмы для генерации отсечений. Стандартный метод состоит в генерации так называемых "no-good" отсечений, которые гарантируют, что все требования недопустимого множества требований не могут быть выбраны одновременно. Наш первый алгоритм основан на идее о том, что, когда некоторое множество требований недопустимо, обычно можно найти недопустимое подмножество требований из данного множества. Отсечение "no-good" для подмножества требований "работает" более эффективно. Одно такое отсечение может заменить много стандартных отсечений "no-good", тем самым значительно уменьшая время работы алгоритма. Наш второй алгоритм для генерации отсечений использует новую технику "Edge-Finding", уже упомянутую выше. Данная техника позволяет находить пары (Q,k), где Q — множество требований, и к — некоторое требование. Если требование из множества Q U {к} обслуживается на одном приборе в допустимом расписании, к может обслуживаться только в определенном интервале, меньшим, чем интервал [гк,с1к]. Использую пары (Q, к), дополнительные ограничения могут быть добавлены в формулировку первой подзадачи. Так как число таких ограничений экспоненциально, они используются как отсечения.

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

При анализе предложенного алгоритма возникает важный вопрос касающийся отсечений "no-good". Возможно ли построить достаточно эффективный на практике алгоритм, который, при заданном недопустимом множестве требований, находил минимально недопустимое подмножество. Такое подмножество требований позволило бы нам сгенерировать наиболее эффективное отсечение "no-good" (т.е. ограничение которое наряду с заданным решением "отсекает"наибольшее число недопустимых решений задачи).

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

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

Важным, на наш взгляд, является то, что для NP-трудного случая задачи 1 11 ^Tj, когда параметры требований удовлетворяют ограничениям:

Pi > Р2 > • • • > Vn\ d\ < d>2 < . < dn, построен псевдополиномиальный алгоритм трудоёмкости 0(n2^2pj) операций. На основе идеи (названный нами В — 1 подход) и метода динамического программирования был построен графический алгоритм решения задач РАЗБИЕНИЕ и РАНЕЦ, позволяющий решать эти задачи не хуже, чем существующие алгоритмы их решения. Одним из преимуществ предложенного алгоритма является то, что параметры задач могут быть как нецелочисленными, так и отрицательными. Мы планируем применить предложенный подход и для других задач комбинаторной оптимизации.

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

2. Беркута О.Н., Лазарев А.А. Алгоритмы сложности 0(п3) решения задачи суммарного запаздывания.// Иссл. по прикл. мат. Выпуск 22. - Казань, 1995. - С. 67-78.

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

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

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

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

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

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

9. Кнут Д. Искусство программирования для ЭВМ. т. 3: Сортировка и поиск.//М.: Мир. 1973. - 348 с.

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

11. Конвей Р.В., Максвелл В.Л., Миллер JI.B. Теория расписаний.// М.: Наука. Гл. ред. физ.-мат. лит., 1975.- 360 с. Англ. вариант книги: Conway R.W., Maxwell W.L., Miller L.W. Theory of Scheduling // Addison-Wesley, Reading, MA. 1967.

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

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

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

15. Лазарев А.А. Эффективный алгоритм для задачи минимизации максимальной задержки.// Теория управления и методы оптимизации-Деп. в ВИНИТИ № 6633-83 С.14-21.

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

17. Лазарев А.А. Двойственная проблема к задаче минимизации максимального штрафа.// Исследования по прикладной математике. Казань, 1984. - Выпуск 10. С. 111-113.

18. Лазарев А. А. Исследование задач теории расписаний с помощью преобразований./ / Исследования по прикладной математике. Казань, 1985. - Выпуск 12. С. 63-74.

19. Лазарев А.А. Алгоритмы решения задачи минимизации суммарного запаздывания для одного прибора.// Теория управления и методы оптимизации.- Деп. в ВИНИТИ № 3795-85 С.21-30.

20. Лазарев А.А. К решению задачи минимизации суммарного запаздывания.// VII конференция "Проблемы теоретической кибернетики", 1985, Тезисы , часть I, Иркутск, С. 114-115.

21. Лазарев А.А. Об одном эффективном алгоритме решения задачи минимизации суммарного запаздывания.// Х-ый симпозиум "Программное обеспечение решения задач оптимального планирования", Нарва, 1988, Тезисы докладов. С.135-136.

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

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

24. Лазарев А.А. Декомпозиционные алгоритмы решения задачи минимизации суммарного запаздывания.// Исследования по прикладной математике, Вып. 21, Казань, 1994. С. 105-110.

25. Лазарев А.А. Минимизация оценки абсолютной погрешности для задач l||Tj и 1||V}.// Исследования по прикладной математике, Вып. 22, Казань, 1995. С. 56-62.

26. Лазарев А.А. Парето-оптималыюе множество NP—трудной задачи минимизации максимального временного смещения// Известия РАН. Теория и системы управления 2006 - N 6.- С. 103 - 110.

27. Лазарев А.А. Решение iVP-трудной задачи теории расписаний минимизации суммарного запаздывания.//Журнал вычислительной математики и математической физики. 2007. - Том 47, К0- 6.1. С. 1087-1099.

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

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

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

31. Лазарев А.А., Кварацхелия А.Г. К исследованию проблемы теории расписаний 1 11 // Материалы Российской конференции «Дискретный анализ и исследование операций», 24-28 июня, 2002 г. Новосибирск, 2002. - С. 218.

32. Лазарев А.А., Садиков P.P. К исследованию проблемы теории расписаний l \ Tj \ Lmax// Материалы российской конференции "Дискретный анализ и исследование операций", 24 июня 28 июня - Новосибирск: Изд-во Ин-та математики, 2002 - С. 219.

33. Лазарев А.А., Садиков P.P. Схема приближённого решения проблемы 1 I rj I -^шах// Материалы российской конференции "Дискретный анализ и исследование операций", 28 июня 2 июля.- Новосибирск: Изд-во Ин-та математики, 2004 - С. 173.

34. Лазарев А.А., Садиков P.P. Теория расписаний. Минимизация максимального временного смещения и суммарного взвешенного числа запаздывающих требований.//М.: Научное издание. Вычислительный центр им. А.А. Дородницына РАН 2007. - 180 с.

35. Лазарев А.А., Садыков P.P., Севастьянов С.В. Схема приближённого решения проблемы 1 | rj | Lmax// Дискретный анализ и исследование операций 2006 - Сер. 2 - Т. 13, N 1.- С. 57 - 76.

36. Лазарев А.А., Сираев P.P. К решению задачи календарного планирования методом ветвей и границ//Материалы 3-ей международной конференции "Математические методы и компьютеры в экономике", май, 26-27, 1998, Часть 1, Пенза, С. 27-28.

37. Лазарев А.А., Сираев P.P. Системы обработки экономической информации. Часть I. Кредитование в банке.// Казань: Издательство Казанского математического общества, 1998. 285 С.

38. Лазарев А.А., Хабибуллин Р.Ф. Эффективные алгоритмы для некоторых задач теории расписаний.// VII конференция "Проблемы теоретической кибернетики", 1985, Тезисы , часть I, Иркутск, С.115-116.

39. Лазарев А.А., Шульгина О.Н. К решению задачи планирования производственно экономической деятельности предприятия// Иссл. по прикл. мат.- Выпуск 21- Казань, 1999 - С. 155 - 169.

40. Лазарев А.А., Шульгина О.Н. Полиномиально разрешимые частные случаи задачи минимизации максимального временного смещения// Ред. Журн. "Изв. Вузов. Математика".- Казан, ун-т.- Казань, 2000 -11 е.- Деп в ВИНИТИ 28.11.00, N 3019-В00.

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

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

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

44. Севастьянов С. В. Геометрические методы и эффективные алгоритмы в теории расписаний// Дис. док. физ.-мат. наук Новосибирск:2000.- 280 с.

45. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование/ / М.: Физматлит, 2002 240 с.

46. Танаев B.C., Шкурба В.В. Введение в теорию расписаний.// М.: Наука. Гл. ред. физ.-мат. лит., 1975.- 256 с.

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

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

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

50. Финкельштейн Ю.Ю. Метод отсечения и ветвления для решения задач целочисленного линейного программирования// Изв. АН СССР. Техн. кибернет- 1971.- N 4 С. 34 - 38.

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

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

53. 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.

54. AlonN., Woeginger G.J., Yadid T. Approximation schemes for scheduling on parallel machines// J. of Scheduling 1998 - V. I - P. 55 - 66.

55. Apt K. Principles of Constraint Programming// Cambridge University Press, 2003.- 420 p.

56. Baker K.R. Introduction to sequencing and scheduling. // Wiley, New York. 1974.

57. 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.

58. Baker K.R., Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G. Preemtive scheduling of a single machine to minimize maximum cost subject to release dates and precedence constraints// Oper. Res -1983.-V. 31, N 2-P. 381 386.

59. 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.

60. Baker K.R., Su Z.-S. Sequencing with due-dates and early start times to minimize maximum tardiness// Naval Res. Logist. Quart 1974 - V. 21-P. 171 - 176.

61. Baptiste Ph. An 0(n4) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs// Oper. Res. Letters -1999-V. 24.- P. 175 180.

62. Baptiste Ph., Jouglet A., Le Pape C., Nuijten W. A constraint-based approach to minimize the weighted number of late jobs on parallel machines// University of Technology of Compiegne, 2000 Research Report N 2000/288.- 45 p.

63. Baptiste Ph., Le Pape C., Nuijten W. Constraint-based scheduling: applying constraint programming to scheduling problems// Kluwer Academic Publishers, 2001- 198 p.

64. Baptiste Ph., Peridy, L., Pinson E. A branch and bound to minimize the number of late jobs on a single machine with release time constraints// European J. of Oper. Res.- 2003. V. 144, N 1. P. 1 11.

65. Baptiste, P. and Brucker, P. and Knust, S. and Timkovsky, V. Ten notes on equal-execution-time scheduling // 40R, Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 2, 2004, P. 111-127.

66. Bellman R. Mathematical aspects of scheduling theory // Journal of the Society of Industrial and Applaid Mathematics. 1956. - Vol. 4. - P. 168-205.

67. Benders J.F. Partitioning procedures for solving mixed-variables programming prolems// Numerische Mathematik 1962 - V. 4.1. P. 238 252.

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

69. Bockmayr A., Pisaruk N. Detecting infeasibility and generating cuts for MIP using CP// Proceedings of the Fifth International Workshop CPAIOR'03, 8-10 may.- Montreal: 2003.- P. 16 30.

70. Bockmayr A., Kasper Th. Branch-and-Infer: A unifying framework for integer and finite domain constraint programming// INFORMS J. Computing.- 1998.- V. 10.- P. 287 300.

71. Bratley P., Florian M., Pobillard P. On sequencing with earliest starts and due dates with application to computing bounds for the (n/rn/G/Fmax) problem// Naval Res. Logist. Quart 1973 - V. 20-P. 57 - 67.

72. Brooks G.N., White C.R. An algorithm for finding optimal or near -optimal solutions to the production scheduling problem// J. Ind. Eng-1965.- V. 16, N 1.- P. 34 40.

73. 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.

74. Brucker, P., Garey, M.R., Johnson, D.S. (1977), Scheduling equal-length tasks under treelike precedence constraints to minimize maximum lateness 11 Math. Oper. Res. 1977. -2(3).- P. 275-284.

75. Brucker, P. and Hurink, J. and Kubiak, W. Scheduling identical jobs with chain precedence constraints on two uniform machines. // Math. Methods Oper. Res., Mathematical Methods of Operations Research. -1999. 49. - 2. - P. 211-219.

76. Brucker, P. and Knust, S. Complexity results for single-machine problems with positive finish-start time-lags, Computing, 1999, 63, P. 299-316.

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

78. Brucker P., Knust S. Complex Scheduling// Springer, 2006.- 284 p.

79. Bruno, J. and Jones, III, J. W. and So, K. Deterministic scheduling with pipelined processors, IEEE Trans. Comput., 29, 1980, 4, P. 308-316.

80. Carlier J. The one-machine sequencing problem// European J. of Oper. Res.- 1982.- V. 11, N 1.- P. 42 47.

81. Carlier J., Pinson E. A practical use of Jackson's preemptive schedulefor solving the job-shop problem// Annals of Oper. Res.- 1990 V. 26-P. 269 - 287.

82. Carlier J., Pinson E. Adjustment of heads and tails for the job-shop problem// European J. of Oper. Res.- 1994 V. 78.- P. 146 - 161.

83. Carroll D. C. Heuristic sequencing of single and multiple components // PhD Thesis, Massachusets Institute of Technology. 1965.

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

85. Chen Z-L., Powell W.B. Solving parallel machine scheduling problems by column generation// INFORMS J. Computing -1999.- V. 11- P. 78 94.

86. Davida, G.I. and Linton, D.J. A new algorithm for the scheduling of tree structured tasks // Proc. Conf. Inform. Sci. and Syst. 1976. -Baltimore, MD. P. 543-548.

87. Dauzere-Peres S., Lasserre J.B. A note on Carlier's algorithm for the one-machine sequencing problem// Toulouse: CNRS, 1990 Rapport LAAS N 90370.- 4 p.

88. Dauzere-Peres S., Sevaux M. Using Lagrangean relaxation to minimize the weighted number of late jobs on a single machine// Naval Res. Logistics.- 2003.- V. 50, N 3.- P. 273 288.

89. Dessouky M.I., Margenthaler C.R. The one-machine sequencing problem with early starts and due dates// AIIE Trans 1972 - V. 4 - P. 214 - 222.

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

91. Du JLeung J.Y.-T., Young G.H. Scheduling chain-structered tasks to minimize makespan and mean flow time. // Inform, and Comput. 1991. - 92(2). - P. 219-236.

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

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

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

95. Gafarov E.R., Lazarev A. A. Graphical approach for solving combinatorial problems.// International Conference on Operations Research, -Karlsruhe, Germany, 6-8 September 2006, P. 59.

96. Gafarov E.R., Lazarev A. A. Algorithms for single machine total tardiness problem 1|| YjTj-// International Conference on Operations Research. -Karlsruhe, Germany, 6-8 September 2006, P. 83

97. Gantt H.L. ASME Transactions, 1903, 24, P. 1322-1336.

98. Garey M.R., Johnson D.S. Scheduling tasks with nonuniform deadlines on two processors // J. Assoc. Comput. Mach. 1976. - 23. - P. 461-467.

99. Garey M.R. and Johnson D.S. Two-processor scheduling with start-times and deadlines // SIAM J. Comput. 1977. - 6. - 3. - P. 416-426.

100. Garey, M.R., Johnson, D.S. "Strong" NP-completeness results: motivation, examples, and implications // J. Assoc. Comput. Mach. -1978. 25, 3 - P. 499-508.

101. Graham R.L., Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G. Optimization and approximation in deterministic sequencing and scheduling: a survey// Ann. Discrete Math.- 1979- V. 5 P. 287 - 326.

102. Gueret C., Prins C., Sevaux M., Heipcke S. Applications of Optimization with XpressMP// Dash Optimization Ltd., 2002 264 p.

103. Hall L.A., Shmoys D.B. Jackson's rule for one-machine schedulings: Making a good heuristic better// Math. Oper. Res 1992 - V. 17.1. P. 22 35.

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

105. 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.

106. Hoogeveen J. A. Minimizing maximum promptness and maximum lateness on a single machine// Math. Oper. Res. 1996. - V. 21.1. P. 100-114.

107. Hooker J.N., Ottosson G. Logic-based Benders decomposition// Math. Prog.- 2003 V. 96.- P. 33 - 60.

108. Ни, T.C. Parallel sequencing and assembly line problems // Oper. Res-1961. 9. - P. 841-848.

109. Jackson J.R. Scheduling a production line to minimize maximum tardiness// Los Angeles, CA: University of California, 1955.- Manag. Sci. Res. Project. Research Report N 43.

110. Jain V., Grossmann I.E. Algorithms for hybrid MILP/CLP models for a class of optimization problems// INFORMS J. Computing.- 2001 -V. 13.- P. 258 276.

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

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

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

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

115. Kise H., Ibaraki Т., Mine H. A solvable case of the one machine scheduling problem with ready and due times// Oper. Res.- 1978 V. 26, N 1.-P. 121 - 126.

116. Kubiak W. Exact and approximate algorithms for scheduling unit time tasks with trre-like precedence constraints. //In Abstracts EURO IX -TIMS XXVIII Paris.- 1988.- P. 195.

117. Lageweg B.J., Lenstra J.K., Rinnooy Kan A.H.G. Minimizing maximum lateness on one machine: computational experience and applications// Statistica Neerlandica 1976 - V. 30.- P. 25-41.

118. Land A.H., Doig A.G. An automatic method for solving discrete programming problems// Econometrica I960 - V. 28 - P. 497 - 520.

119. Lawler E.L. Optimal sequencing of a single machine subject to precedence constraints// Manag. Sci 1973.- V. 19, N 5.- P. 544 - 546.

120. Lawler E.L. A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs// Annals of Oper. Res.- 1990.- V. 26.- P. 125 133.

121. Lawler E.L. Knapsack-like scheduling problems, the Moore-Hodgson algorithm and the "tower od sets" property// Math. Сотр. Modelling-1994.- V. 20, N 2.- P. 91 106.

122. Lawler E.L., Moore J.M. A functional equation and its application to resource allocation and sequencing problems// Manag. Sci 1969.-V. 16.- P. 77 - 84.

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

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

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

126. 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.

127. Lazarev A.A. Scheduling algorithms based on necessary optimality //Journal of Soviet Mathematics, V 44, N 5 (1989), P. 635-642.

128. Lazarev A. A. Analysis of Scheduling Problems Using Transformation.// Journal of Soviet Mathematics, Vol. 45, N 2, April 1989. P. 1029-1036.

129. Lazarev A.A. Scheduling algorithms based on necessary optimality. // Journal of Soviet Mathematics, V 44, N 5, 1989, P. 635-642.

130. Lazarev A. A. Analysis of Scheduling Problems Using Transformation.// Journal of Soviet Mathematics, Vol. 45, N 2, April 1989. P. 1029-1036.

131. Lazarev A. Scheduling to minimize maximum lateness for single machine: new approach of investigation// 9-th Belgian-French-German Conference on Optimization, Namur, September, 7-11, 1998, http://www.fundp.ac.be/ bfgconf9/.

132. Lazarev A.A. Analize of structure of optimal schedule the problem minimizing maximum lateness for single machine// the Fourth International Congress on Industrial and Applied Mathematics, 5-9 July 1999, Edinburgh, Scotland, p 283.

133. Lazarev A.A. Minimum absolute error for NP-hard scheduling problem for single machine minimizing maximum lateness// Workshop on the Complexity of Multivariate Problems, October 4-8, 1999, Hong Kong, China, p. 13.

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

135. 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.

136. Lazarev A., Schul'gina 0. Problem minimizing maximum lateness for single machine: properties, procedures, algorithms// 9-th Belgian-French-German Conference on Optimization, Namur, September 7- 11- Namur, 1998.- P. 45.

137. Lazarev A., Siraev R. Scheduling to minimize total weighted completion time: branch and bound method// 9-th Belgian-French-German Conference on Optimization, Namur, September, 7-11, 1998, http://www.fundp.ac.be/ bfgconf9/.

138. Lenstra J.K., Rinnooy Kan A.H.G., Brucker P. Complexity of machine scheduling problems// Annals of Discrete Math 1977 - V. 1- P. 343 -362.

139. 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.

140. Leung, J.Y.-T. and Vornberger, 0. and Witthoff, J.D. On some variants of the bandwidth minimization problem // SIAM J. Comput., SIAM Journal on Computing. 13 - 1984.- 3. - P. 650-667.

141. Marriott K., Stuckey P.J. Programming with Constraints: An Introduction// The MIT Press, 1998 476 p.

142. Mastrolilli M. Efficient Approximation Schemes for Scheduling Problems with Release Dates and Delivery Times// J. of Scheduling 2003 - V. 6, N 6.- P. 521 - 531.

143. McMahon G., Florian M. On scheduling with ready times and due dates to minimize maximum lateness// Oper. Res.- 1975.- V. 23.- P. 475 482.

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

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

146. Moore J.M. An n job, one machine sequencing algorithm for minimizing the number of late jobs// Manag. Sci 1968.- V. 15, N 1 - P. 102 - 109.

147. Nowicki E., Zdrzalka S. A note on minimizing maximum lateness in a one-machine sequencing problem with release dates// European J. of Oper. Res.- 1986.- V. 23,- P. 266 267.

148. 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.

149. Peridy, L., Pinson E., Rivreau D. Using short-term memory to minimize the weighted number of late jobs on a single machine// European J. Oper. Res.- 2003.- V. 148. P. 591 603.

150. 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.

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

152. 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.

153. 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.

154. 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. - R 405-414.

155. Potts C.N. Analysis of a heuristic for one machine sequencing with release dates and delivery times// Oper. Res 1980 - V. 28. R 1436 - 1441.

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

157. 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.

158. Queyranne M., Schultz A.S. Polyhedral approaches to machine scheduling// Preprint N 408/1994.- Berlin: Technical University of Berlin, Department of Mathematics, 1994.- 61 p.

159. Sadykov R.R., Lazarev A.A. Experimental comparison of branch-and-bound algorithms for the 1 \ rj \ Lmax problem// Proceedings of the Seventh International Workshop MAPSP'05, 6-10 june Siena, Italy: 2005.- P. 239 - 241.

160. Schrage, L. Solving Resource-Constrained Network Problems by Implicit Enumeration: Non Preemptive Case// Oper. Res. 1970. - V. 18.1. P. 263 278.

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

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

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

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

165. 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.1. P. 1-12.

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

167. Sevaux M., Dauzere-Peres S. Genetic algorithms to minimize the weighted number of late jobs on a single machine// European J. of Oper. Res.- 2003.- V. 151 P. 296 - 306.

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

169. Simons B.B. A fast algorithm for single processor scheduling// Proceedings of the 19th IEEE Annual Symposium on Foundations of Computer Science New York: Ann. Arbor. Mich., 1978 - P. 246 - 252.

170. Simons, B. Multiprocessor scheduling of unit-time jobs with arbitrary release times and deadlines // SIAM J. Comput. 12, 1983, 2, P. 294-299.

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

172. Sousa J.P., Wolsey L.A. A time-indexed formulation of non-preemptive single-machine scheduling problems// Math. Prog.- 1992- V. 54-P. 353 367.

173. 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.

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

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

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

177. Szwarc W., Mikhopadhyay S. Decomposition of the single machine total tardiness problem //Oper. Res. Lett. 1996. - V.19. - P. 243-250.

178. Tansel B.C., Sabuncuoglu I. New insights on the single machine total tardiness problem // Operations Research Letters. 1997. - V.48. - P. 82-89.

179. Tansel B.C., Kara B.Y., Sabuncuoglu I. An efficient algorithm for the single machine total tardiness problem j I HE Transactions. 2001. -V.33. - P. 661-674.

180. Timkovsky, V.G. Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity, European J. Oper. Res., 2003, 149, 2, 355-376.

181. Ullman J.D. (1975) NP-complete scheduling problems // J. Comput. System Sci. 1975. - 10. P. 384-393.

182. Wilkerson L.J., Irvine J.D. An improved algorithm for scheduling independent tasks // AIIE Transactions. 1971. - V.3. - P. 239-245.