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

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

Уразова Инна Владимировна

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

ПРИБОРАМИ

01.01.09 — Дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

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

2 6 МАЙ 2011

4848150

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

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

доцент Р. Ю. Симанчев

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

профессор В. К. Попков

кандидат физико-математических наук, И. Д. Черных

Ведущая организация: Нижегородский государственный университет

им. Н. И. Лобачевского, Нижний Новгород

Защита состоится 15 июня 2011 года в 16 час. 00 мин. на заседании диссертационного совета Д.003.015.01 при Учреждении Российской Академии наук Институте математики им. С.Л. Соболева СО РАН по адресу: 630090, г. Новосибирск, пр. Академика Коптюга, 4.

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

Автореферат разослан «•? » уЫ-СиХ. 2011 г.

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

диссертационного совета Д.003.015.01, доктор физико-математических наук Ю.В. Шамардин

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

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

Свое развитие теория расписаний получила в середине прошлого века. Глебов Н.И., Михалевич B.C., Танаев B.C., Шкурба В.В., Беллман Р., Брук-кер П., Джонсон Д., Джонсон С. и другие превратили теорию расписаний в отдельное направлениие в области оптимизации. В настоящее время теория расписаний активно развивается в работах Гимади Э.Х., Гордона B.C., Ковалева М.Я., Кононова A.B., Лазарева A.A., Севастьянова C.B., Серваха В.В. и многих других российских и зарубежных ученых.

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

Одним из направлений является сведение задач комбинаторной оптимизации и, в частности, теории расписаний, к задачам целочисленного линейного программирования (ЦЛП). В ряде известных методов решения задач ЦЛП исходная задача приводится к последовательности задач непрерывной оптимизации. На этом основаны алгоритмы отсечения, ветвей и границ, перебора ¿-классов и др.

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

программирования, целочисленного программирования. Исследование полиэдральных свойств комбинаторных задач, а именно: описание целочисленного многогранника (выпуклой оболочки), сответствующего задаче, построение оценок числа его вершин, анализ смежности вершин, построение правильных, опорных и фасетных неравенств, разработка эффективных алгоритмов решения исследуемых задач, основанных на полиэдральных свойствах этих задач - все эти методы активно развиваются в работах Шевченко В.Н., Симанчева Р.Ю., Васильева И.Л., Pulleyblank W.R., Reinert К. и др. Количество работ, связанных с применением полиэдрального подхода к задачам теории расписаний невелико. Следует отметить работы Balas Е., Mokotof Е., Shulz A.S., Queyranne М. [1-4], в которых исследуются полиэдральные свойства некоторых задач теории расписаний.

Задача построения расписания для параллельных машин PMS (Parallel Machine Scheduling) является NP - трудной в сильном смысле. В 1978г. Lenstra J.K. и Rinnooy Кап [5] показали, что для этой задачи невозможно построить приближенный полиномиальный алгоритм решения, относительная погрешность которого будет меньше

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

В обозначениях, принятых в теории расписаний, эта задача имеет вид Pm\prec] jij — l|Cmai. Для случая, когда число параллельных приборов m больше трех данная задача является открытой в смысле теории сложности. В работе [6] предложен точный полиномиальный алгоритм для частного случая задачи Pm\tree;pj = 1|Стах, когда граф предшествования - дерево. В работах [7,8] аналогичная задача для двух машин решена за полиномиальное время.

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

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

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

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

Научная новизна результатов. Построена модель целочисленного линейного программирования для задачи Рт\ргес\ р3 = 1\Стах. Получены достаточные условия на общее время обслуживания требований, гарантирующие существование расписаний. Построены три класса неравенств, правильных относительно выпуклой оболочки векторов инциденций расписаний, найдены достаточные условия их опорности. Проведено сравнение неравенств внутри каждого класса, приведены примеры случаев их "несравнимости". Предложены полиномиальные алгоритмы решения задачи идентификации для двух из построенных классов, для третьего - эвристическая процедура. В терминах частичного порядка получены нижние и верхние оценки на минимальное время обслуживания единичных требований, позволяющие существенно ограничить размерность задачи. На основе построенных правильных неравенств разработаны два алгоритма отсечения для решения задачи Рт\ргес;р^ = \\Стах и анализа выпуклой оболочки расписаний.

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

Апробация работы. Основные результаты работы докладывались на XIV Байкальской международной школе-семинаре "Методы оптимизации и их приложения" (Северобайкальск, 2008), IV Всероссийской конференции

"Проблемы оптимизации и экономические приложения" (Омск, 2009), Российской конференции "Дискретная оптимизация и исследование операций" (Новосибирск, 2010), на XIV Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 2011), на XXXI научно-исследовательском семинаре по дискретной математике в Южном научном центре НАН Украины (Одесса, 2009), а также на семинарах в Институте математики им. С.Л. Соболева СОРАН и его Омском филиале, Омском государственном университете им. Ф.М. Достоевского, Нижегородском государственном университете им. Н.И. Лобачевского.

Публикации. По теме диссертации опубликовано 8 работ, три из них в рецензируемых изданиях из списка ВАК.

Структура и объем работы. Работа состоит из введения, трех глав, заключения, списка литературы из 131 наименования. Общий объем работы - 101 страница, включая 9 рисунков и 13 таблиц.

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

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

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

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

Множество расписаний, рассматриваемых в диссертации, имеют следую-

щую содержательную постановку. Требования множества У, |V| — п, обслуживаются т параллельными идентичными приборами. Все требования поступают в очередь на обслуживание одновременно (в момент времени к — 0) и имеют одинаковые (равные 1) длительности обслуживания. Запрещены прерывания в обслуживании требований. На множестве V задано отношение частичного порядка <, определяющее условия предшествования в обслуживании требований. Всякий порядок обслуживания требований на множестве V, допустимый относительно частичного порядка <, называется допустимым расписанием или, просто, расписанием. Мы рассматриваем расписания, в которых все работы должны быть завершены к моменту времени d. При этом очевидно, что если d будет слишком мало, то множество определенных выше расписаний может оказаться пустым.

Это множество расписаний допускает следующую формализацию. Расписанием называется функция а : V —» D = {1,2,... d}, такая, что

• соотношение i < j влечет неравенство <г(г) < a(j);

• для любого к £ D имеется не более тп требований г £ V, таких, что (т (г) = к.

Множество расписаний, определенных данными условиями, обозначим через Заметим, что если d < d', то Е^ С Е^ (при этом полагаем, что пустое множество является подмножеством любого множества). Задача заключается в минимизации общего времени обслуживания всех требований, то есть

maxa(i) min. (1)

iev у aeZi

В параграфе 1.2 построена полиэдральная релаксация M,j с Rmi многогранника М^, соответствующего множеству Ej.

Пусть G = (У; E(G)) - ациклический орграф, задающий порядок предшествования на множестве требований V.

Расписанию a £ сопоставим его вектор инциденций х" = (х"к, г 6 V. к £ D) £ Rnd по правилу:

Для каждой вершины г € V определим две константы: Рг = тах{|Р*| +1, +1]}, где - максимальный путь из вершинной базы графа б в вершину г, Щ - множество всех предков вершины г; дг = тах{|<54| 4- где Qi - максимальный путь из вершины г в

вершинную антибазу графа (?, УЦ - множество всех потомков вершины г. Определим множества Д = {¡Н, Р> + 1, рг + 2, ..(I — Ц{} для каждой г £ V и Ук = ^ У\к е Д} для каждого к € О. Зададим полиэдр М^ С как множество решений системы линейных уравнений и неравенств:

5>* = М€У; (3)

кСй,

^хц. <т, к £ Б; (4)

¿еП

< XI ял, (и) е Е{С1), к б А; (5)

О < ха < 1, г 6 V, к € Д; (6)

= 0, г е V, к е Ю \ Д. (7)

Ограничения (3) означают, что каждое требование обслуживается ровно одним прибором. Ограничения (4) гарантируют, что одновременно могут обслуживаться не более т требований. Выполнение условий предшествования обеспечивается ограничениями (5). Ограничения (7) отбрасывают заведомо недопустимую область обслуживания требования i.

Теорема 1.1. Целочисленные точки полиэдра (3)-(7) и только они являются расписаниями в смысле соотношения (2).

Таким образом,

Мг = сопу{х"\а € £<¿1 = сопу{ШЛ П Ъы).

Важным свойством релаксации М,г является то, что она не содержит "лишних" целочисленных точек, не являющихся векторами инциденций расписаний или, что то же, множество векторов инциденций расписаний явля-

ется множеством целочисленных решений системы (3)-(7).

В параграфе 1.3 задача (1) рассматривается как задача целочисленного линейного программирования на полиэдре М^ с целевой функцией вида

л

при этом, А1 <с Л2 Л^.

Условия на А*, при которых оптимальное решение задачи (8) соответствует оптимальному решению задачи (1) (возможно, неоднозначно), определяются теоремами 1.2 и 1.3.

Теорема 1.2. Пусть т^Г, А; < \к+1, к = 1,2, ...,(1 — 1, ащ е Х^ - оп-

ы\

тимальное решение задачи (1), а £ Е^. Тогда, если к(ха) < к{ха'), то тахст(г) = тах£г„(г)-

Теорема 1.3. Пусть т^ < А^+ь к = 1,2, ...,с2— 1, ха• е М^

1=1

- оптимальное решение задачи (8). Тогда для любого х" € М^ имеем

таха(г) > тахст»(г).

¿еУ

Теорема 1.3 позволяет искать решения задачи (1) методами целочисленного линейного программирования. Однако, в силу теоремы 1.2, решение рассматриваемой задачи в постановке (8) может оказаться более трудоемким, чем в постановке (1).

В параграфе 1.4 получено достаточное условие непустоты множества Е,;.

Теорема 1.4.Пусть В\, В2,-.., - разбиение мноэ/сества вершин

орграфа С па базы. Если , то мноокество Е^ не пусто.

р=1

Кроме того, в параграфе 1.4 рассматривается следующая задача: найти такие вещественные неотрицательные функции <р{С, т) и 'ф(С, тп), что <р(С!,т) < (¿тт < 1р(С, т). Наличие этих оценок позволяет сократить перебор при использовании метода дихотомии (см. далее параграф 3.2). Наличие верхней оценки, позволяет понизить размерность задачи в смысле

к

¿ек

к

постановки (8). Определим для орграфа б следующие характеристики: | Втах | - мощность максимальной базы орграфа С; I -^шах] ~ длина максимального по числу дуг пути в орграфе С;

Рт — Г^ггТ ~ плотность орграфа относительно т (т-плотность орграфа 8=1

С).

Утверждение 1.1.

a) Если |Бтах| < т, то ¿т-т = |Ртах| + 1.

b) Если |Бшах| > т, то |Ртах| + 1 < < рт.

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

Во второй главе строятся классы неравенств, правильных относительно многогранника М^ и исследуются их свойства. В параграфе 2.1 дано описание трех классов неравенств и доказательство их правильности. Неравенства этих классов, вообще говоря, усиливают ограничения полиэдра Ма в том смысле, что в М^ существуют точки, "отсекаемые" этими неравенствами.

Следующая теорема описывает класс правильных относительно М^ неравенств, который обозначим через I.

Теорема 2.1. Пусть Р С б - путь, {¿1,12, • • • ,ц} С У(Р) и к € О. Тогда неравенство

г

5>.* ^1 (9)

«=1

является правильным к многограннику М^.

Второй класс правильных неравенств, описанный в теореме 2.2, обозначим

Теорема 2.2. Пусть Р С б - путь, к е И, 1 < к < (I, г е У(Р) -вершина, предшествующая всем остальным вершинам пути Р, г £ У(Р)

- последняя вершина о пути Р. Тогда неравенство

к-1 <1

£ £ .Г„<1 (10)

(=1 ]$У{Р) 1=к+1

является правильным относительно многограппикаЪ&% ■

Для описания третьего класса неравенств, правильных относительно многогранника М/, введем необходимые определения и обозначения. Орграф Я называется ¿-дольным, если существует такое разбиение множества его вершин на < вершинно-непересекающихся подмножеств Ц, Ц,.. 14, что для любого е {1,2,..., £ — 1} множество и индуцирует в Н двудольный орграф с началами дуг в V] и концами в 1^+1. Если в данном определении для любого е {1,2,..., £ — 1} множество Ц и индуцирует полный двудольный орграф, то граф Я называется полным ¿-дольным. Через Я(Ц, -.., Ц; Е(Н)) будем обозначать полный ¿-дольный орграф. Следующая теорема описывает третий класс правильных относительно Шг неравенств.

Теорема 2.3. Пусть Я(Ц, ..., Ц; Е{Н)) - полный 1-долъный ациклический орграф в С, к £ О. Тогда неравенство

й 1-1 к £ Еха+£ £х*+Е Е*« ^ ч^ш) (и)

является правильным относительно М^.

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

В параграфе 2.2 получены достаточные условия, при которых построенные неравенства являются опорными к многограннику М^, то есть существуют вершины в М^, на которых неравенства выполняются как равенства.

В параграфе 2.3 в каждом из построенных классов выделен подкласс наиболее "сильных" неравенств.

Будем говорить, что неравенство ах < ао не сильнее неравенства Ьх < относительно М^, если {х 6 М^ | ах > ао} С {х € М<г | Ьх > 6о}.

Утверждение 2.1. Пусть РиРг С й - пути и У(Рх) С У{Р2). Тогда для любого к £ И неравенство ^ х^ < 1 не сильнее неравенства

зеУ(Р1)

Е хзк < 1-

зеУ(р2)

Утверждение 2.2. Пусть Р С С - путь, к 6 Б. Неравенство хзк ^ 1 не сильнее неравенств

З^У(Р)

■ Л

a) Е х]к + Е хи — г ^ - начальная вершина пути Р; ^еУ(Р) 1=Ш

в.

b) Е х]к + Е Хг1 — 2 е У(Р) - последняя вершина пути Р. }£У(Р) ¡=1

Утверждение 2.3. Пусть Р С (? - путь, к € О. Неравенство <1 в, Е хзк + Е хи — 1 и неравенство ■ £2 + Е1«/' — 1 не силь-]&У(Р) Ык+1 :еУ{Р) 1=1

к-1 <г

«ее неравенства х21+ Е + Е £¿1 < 1, где г € - начальная

1=1 ¿€У(Г) /=*+1

вершина пути Р, г £ У(Р) - последняя вершина пути Р.

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

Утверждение 2.4. Пусть Р С О - путь с начальной вершиной г и конечной вершиной г, к £ О.

Если к < р{, то полиэдр М<г целиком лежит в пересечении гиперплоскостей

к-\

¡=1 ;=Н1

Если к > <1 — дг, то полиэдр М(; целиком лежит в пересечении гипер-

плоскостей

k-1 d

1=1 l=k+1

Утверждение 2.5. Пусть P С G - путь с начальной вершиной i и конечной вершиной z, d — < к < рг. Тогда неравенства

к-1 d ^Xd + xik + Xil - 1 i=l jeV(P)

■u

j£V(P)

эквивалентны относительно M<j.

В параграфе 2.5 второй главы предложены алгоритмы решения задачи идентификации (Separation problem), которая заключается в следующем: в данном классе неравенств найти такое, которое отделяет заданную точку х € Mj \ Mz от Мz, либо доказать, что такого неравенства нет. Для первых двух классов неравенств разработаны полиномиальные алгоритмы решения задачи идентификации трудоемкости 0(п3) (теоремы 2.6 и 2.7), для третьего - предложена эвристическая процедура.

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

В параграфе 3.1 описаны точные алгоритмы IPI и SHP решения исследуемой задачи, основанные на процедуре отсечения. В качестве отсечений используются правильные неравенства, построенные в главе 2. Каждый из алгоритмов включает в себя процедуру идентификации неравенств.

В параграфе 3.2 предложен алгоритм DMN поиска минимального d из множества таких, что Е^ непусто. В основе этого алгоритма лежат метод дихотомии и включение Ej с Ed при ä < d. Алгоритм представляет собой гибрид метода дихотомии и метода отсечений.

Параграф 3.3 посвящен анализу целевой функции для задачи Pm\prec\pj = 1|Стах, построенной в параграфе 1.3. Дело в том, что

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

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

1) Сравнение алгоритмов отсечения, использующих построенные классы неравенств, с пакетом CPLEX по количеству отсечений и времени работы. Оказалось, что пакет CPLEX уступает алгоритму SHP по количеству отсечений и времени работы на всех рассмотренных задачах. Таким образом, разработанный в диссертации алгоритм SHP учитывает специфику и полиэдральную структуру множества расписаний обслуживания единичных требований с предшествованиями параллельными приборами и предпочтителен для использования при решении соответствующих оптимизационных задач.

2) Сравнение разработанных алгоритмов между собой; выделение характеристик задач, влияющих на время работы и количество построенных алгоритмами отсечений. Самыми легкими для обоих алгоритмов оказались серии задач, в которых граф предшествования между требованиями представляет собой несвязные пути или несвязные орграфы. На этих задачах алгоритму IPI понадобилось меньше времени для решения задачи. Дольше всех решались задачи, орграфы которых содержали полный двудольный подграф. На таких задачах алгоритм IPI значительно уступает алгоритму SHP по количеству отсечений и времени решения. На сериях задач с орграфами вида "входящее дерево", "выходящее дерево" и "дерево" также быстрее оказался алгоритм SHP.

3) Разработка' рекомендаций по выбору коэффициентов целевой функции для задачи Pm\prec;pj = 1|Стах, предложенной в параграфе 1.3.

Наряду с целевой функцией h(x), удовлетворяющей условиям

к

mY,>*<bk+i,k = l,2,~-,d-l, (12)

¡=1

были рассмотрены функции вида (8) с коэффициентами построенными по законам

к = fiin{k) = пк,

Ак = fsq{k) = пк2.

Введем следующие обозначения:

4, dsq, dim - оптимальные: значения целевых функций с коэффициентами Л^ вида (12), fsq{k) и /цп(к) соответственно; dmm - значение, найденное алгоритмом DMN.

Точные решения задач, необходимые для анализа зависимостей /¡гп и fgq, были найдены с помощью дихотомии (алгоритм DMN, параграф 3.2). При этом в силу утверждения 1.1 в качестве начальных границ отрезка разбиения были взяты А = \Ртах\ + 1иВ = рт. Оптимальные значения целевых функций с зависимостями (3.3), /;,„ и fsq были найдены алгоритмом SHP. Во всех рассмотренных примерах dmin и dsq совпадают. Значение ¿цп совпало с dmin лишь до п < 20. Более того, при п > 90 значение <4 не было найдено, в то время как dsq = dmin. Таким образом, на задачах большой размерности для коэффициентов А* функции h(x) целесообразно использовать Ajt = пк1, при t > 2.

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

РЕЗУЛЬТАТЫ, ВЫНОСИМЫЕ НА ЗАЩИТУ

1. Построена модель целочисленного линейного программирования для задачи Pm\preqpj = 1|Стах. Получены достаточные условия на общее время обслуживания требований, гарантирующие существование расписаний. В терминах частичного порядка получены нижние и верхние оценки на минимальное время обслуживания единичных требований, позволяющие существенно ограничить размерность задачи.

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

3. На основе построенных правильных неравенств разработаны два алгоритма отсечения для анализа полиэдральной структуры и решения задачи Рт\ргес-,р] — 1 [С'тах- Проведена апробация, подтвердившая эффективность разработанных алгоритмов. В процессе апробации сформирован список тестовых задач высокой размерности с точными решениями.

Литература

[1] Balas Е. On the facial structure of sheduling polyhedra // Mathematical Programming Study, 1985. N 24. - P. 179-218.

[2] Mokotoff E. An exact algorithm for the identical parallel machine scheduling problem // Europ. J. of Oper. Res., 2004. - V. 152. - P. 758-769.

[3] Queyranne M., Wang Y. A cutting plane procedure for precedence-constraned single machine scheduling. Working paper. Faculty of Commerce. University of British Columbia. Vancouver. Canada, 1991.

[4] Schulz A.S., Queyranne M. Polyhedral Approaches to Machine Scheduling. Berlin, 1994.

[5] Lenstra J.K., Rinnooy Kan. Complexity of scheduling under precedence constraints // Oper. Res., 1978. N 26. - P. 22-35.

[6] Ни T.C. Parallel sequencing and assembly line problems // Operation Research, 1961. N 9. - P. 841-848.

[7] Coffman E.G., Jr, Graham R.L. Optimal scheduling of two processor systems. Acfa Informal., 1972. N 1. - P. 200-213.

[8] Pujn M-, T. Kasami, K. Ninimiya. Optimal sequencing of two equivalent processors // SLAM J. Appl. Math., 1969. N 17. - P. 784-789.

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

¡1] Симанчев Р.Ю., Уразова И.В. Целочисленная модель задачи минимизации общего времени обслуживания параллельными приборами единичных требований с предшествованиями // Автоматика и телемеханика, 2010. N 10. - С. 100-106.

[2] Симанчев Р.Ю., Уразова И.В. Многогранник расписаний обслуживания идентичных требований параллельными приборами // Дискретный анализ и исследование операций, 2011. N1.-0. 87-92.

[3] Уразова И.В. Класс правильных неравенств для задачи упаковки вершин ациклического орграфа в полосу заданной ширины // Вестник Омского университета, 2011. N2(60). - С. 48 52.

[4] Симанчев Р.Ю., Уразова И.В. Класс опорных неравенств для многогранника расписаний обслуживания единичных требований параллельными процессорами // Математическое программирование. Труды XIV Байкальской международной школы-семинара "Методы оптимизации и их приложения 2008. - Т. 1. - С. 530-536.

[5] Уразова И.В. Результаты вычислительного эксперимента для одной задачи теории расписаний //IV Всероссийская конференция "Проблемы оптимизации и экономические приложения". Омск, 2009. - С. 169.

[6] Симанчев Р.Ю., Уразова И.В. О задаче упаковки вершин ациклического орграфа в полосу фиксированной ширины // ДОСДМ, 2010. N9.-0. 56-59.

[7] Уразова И.В. Варьирование директивного срока в одной задаче теории расписаний // Материалы Российской конференции "Дискретная оптимизация и исследование операций". Новосибирск, 2010. - С. 149.

[8] Уразова И.В. Новый класс правильных неравенств для задачи Рт\ргес;р^ = 1\Стах // Информационный бюллетень АМП, N 12 (Тез. докл. Всеросс. конф. МпиП). Екатеринбург, Уро РАН, 2011. - С. 211-213.

Уразова Инна Владимировна

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

ПРИБОРАМИ

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

кибернетика

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

Подписано в печать 4.05.2011 г. Формат бумаги 60 х 84 1/16. Печ. л. 1,0. Тираж 100 экз. Заказ 177.

Издательство ОмГУ 644077, Омск-77, пр. Мира, 55а Отпечатано на полиграфической базе ОмГУ 644077, Омск-77, пр. Мира, 55а

Введение

1. Построение ЦЛП-модели для задачи обслуживания единичных требований параллельными приборами

1.1. Полиэдральная теория.

1.2. Полиэдральная релаксация многогранника расписаний.

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

1.4. Условия существования расписаний.

2. Классы правильных неравенств для многогранника расписаний

2.1. Построение правильных неравенств.

2.2. Некоторые условия опорности

2.3. Сравнение построенных неравенств

2.4. Полиэдральные свойства неравенств.

2.5. Решение задачи идентификации.

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

3.1. Алгоритмы отсечения.

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

3.3. Выбор коэффициентов целевой функции.

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

Свое развитие теория расписаний получила в середине прошлого века. Глебов Н.И., Михалевич B.C., Танаев B.C., Шкурба В.В., Беллман Р., Бруккер П., Джонсон Д., Джонсон С. и другие превратили теорию расписаний в отдельное направлениие в области оптимизации [1, 24, 48, 51, 68, 76, 78, 84, 90, 101]. В настоящее время теория расписаний активно развивается в работах Гимади Э.Х., Гордона B.C., Ковалева М.Я., Кононова A.B., Лазарева A.A., Севастьянова C.B., Серваха В.В. и многих других российских и зарубежных ученых [3, 4, 15, 26, 31, 33, 46, 49, 50, 108].

Помимо прикладного значения, задачи теории расписаний представляют значительный теоретический интерес. Проблематика теории расписаний охватывает исследование вычислительной сложности задач, разработку точных, приближенных и эвристических алгоритмов их решения [22, 34, 70, 75, 109] и др. При этом подавляющее количество работ посвящено развитию комбинаторных подходов. Однако, как показывает практика, возможности комбинаторных алгоритмов существенно ограничены размерностью решаемых задач. Это вполне согласуется с результатами теории комбинаторной сложности - большинство задач, возникающих в теории расписаний, являются ТУР-трудными [5]. В связи с этим большое количество исследований в теории расписаний посвящено разработке приближенных и эвристических алгоритмов.

Приближенные алгоритмы находят приближенное решение задачи за полиномиальное время и позволяют оценить погрешность полученного решения [9,15, 31,108]. Эвристические алгоритмы также находят приближенное решение задачи за приемлемое время, но не дают оценок погрешности полученного решения [28, 106]. Здесь следует заметить, что для некоторых задач существуют неулучшаемые приближенные решения, что сильно снижает актуальность приближенных методов.

Одним из направлений является сведение задач комбинаторной оптимизации и, в частности, теории расписаний, к задачам целочисленного линейного программирования (ЦЛП). Данный подход используется, например, в [3, 115, 130]. В ряде известных методов решения задач ЦЛП исходная задача приводится к последовательности задач непрерывной оптимизации. На этом основаны алгоритмы отсечения [11, 16, 91], Ленд и Дойг [21, 27], перебора Ь-классов [18, 19] и др.

В последнее время одним из перспективных подходов в комбинаторной оптимизации является анализ полиэдральной структуры задач и, как следствие, применение для их решения аппарата выпуклого анализа, выпуклого программирования, целочисленного программирования. Известно большое количество теоретических и практических результатов для задач комбинаторной оптимизации, полученных с помощью полиэдрального подхода. Наиболее яркие примеры - задача коммивояжера [73, 74, 83, 94], задачи размещения [12, 81, 87, 88] и ряд других широко известных оптимизационных задач [72, 77, 95-97, 99, 113, 116]. Количество работ, связанных с применением полиэдрального подхода к задачам теории расписаний невелико. Следует отметить работы Mokotof Е. [112] и Shulz A. S. [125, 126], Balas Е. [71] и другие [112, 117-119], в которых исследуются полиэдральные свойства некоторых задач теории расписаний.

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

Исследование полиэдральных свойств комбинаторных задач, а именно: описание целочисленного многогранника (выпуклой оболочки), сответству-ющего задаче, построение оценок числа его вершин, анализ смежности вершин, построение правильных, опорных и фасетных неравенств, разработка эффективных алгоритмов решения исследуемых задач, основанных на полиэдральных свойствах этих задач - все эти методы активно развиваются в работах Шевченко В.Н., Симанчева Р.Ю., Васильева И.Л., Pulleyblank W.R., Reinert К. и других [2, 42-45, 47, 64-67, 90, 91, 115, 120, 127].

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

Задача построения расписания для параллельных машин PMS (Parallel Machine Scheduling) является NP - трудной в сильном смысле [110].

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

В обозначениях, принятых в теории расписаний, эта задача имеет вид Pm\prec]pj = 1|Стах. Для случая, когда число параллельных приборов т больше трех данная задача является открытой в смысле теории сложности [5, 131]. В [111] показано, что для рассматриваемой задачи невозможно построить полиномиальный алгоритм решения, относительная погрешность которого будет меньше В [101] предложен точный полиномиальный алгоритм для частного случая задачи Ртп\Ьтев] pj = 1|СтаХ: когда граф предшествования - дерево. Кроме того, известен точный полиномиальный алгоритм решения для частного случая задачи, а именно, когда граф отношений предшествования состоит из двух несвязных деревьев - входящего (in-tree) и выходящего (out-tree) [48, 110]. В работах [84, 89] аналогичная задача для двух машин решена за полиномиальное время. Когда машин более двух, задача Pm\prec;pj = 1|Стах остается открытой [5, 131].

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

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

Диссертация состоит из введения, трех глав и заключения.

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

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

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

3. На основе построенных правильных неравенств разработаны два алгоритма отсечения для анализа полиэдральной структуры и решения задачи Рт\ргес;р^ = 1|Стаа;. Проведена аппробация, подтвердившая эффективность разработанных алгоритмов. В процессе аппробации сформирован список тестовых задач высокой размерности с точными решениями.

Заключение

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

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

2. Веселое С.И., Чирков А.Ю. Оценки числа вершин целых полиэдров // ДАИО, 2007. N2, серия 2. Т.14. С. 14-31.

3. Гимади Э.Х. О некоторых математических моделях и методах планирования крупномасштабных проектов // Модели и методы оптимизации. Новосибирск: Наука, 1988. С. 89-115.

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

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

6. Дергунова Т.В., Симанчев Р.Ю.Задача о связном k-факторе: идентификация клиповых фасет и алгоритм отсечения // Фунд. и прикл. математика. Омск: ОмГУ, 1994. С. 71-80.

7. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М.: Наука, 1981. 344с.

8. Емеличев В.А., Ковалев М.М. Полиэдральные аспекты дискретной оптимизации // Кибирнетика, 1982. N 6. С. 54-62.

9. Еремеев A.B., Романова A.A., Сервах В.В., Чаухан С.С. Приближенное решение одной задачи управления поставками // Дискретный анализ и исследование операций, Сер.2, 2006. Т.13, N.1. - С.27-39.

10. Еремин И.И., Астафьев H.H. Введение в теорию линейного и выпуклого программирования. М.: Наука, 1976.

11. Заблоцкая O.A., Колоколов A.A. Вполне регулярные отсечения в булевом программировании // Управляемые системы. Новосибирск: ИМ СО АН СССР, 1983. Вып. 23. С. 55-63.

12. Забудский Г.Н. Некоторые свойства многогранника задачи о р-медиане // Вестник Омского университета, 1996. N 4. С. 11-13.

13. Карп P.M. Сводимость комбинаторных задач // Киберн. сб., 1975. Вып. 12. С. 123-148.

14. Ковалев М.М. Дискретная оптимизация (целочисленное программирование). Минск: БГУ, 1977. 192 с.

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

16. Колоколов A.A. Методы дискретной оптимизации // Учебное пособие. Омск: ОмГУ, 1984. 75 с.

17. Колоколов A.A. Регулярные разбиения и отсечения в целочисленном программировании // Сиб. журн. исслед. операций. Новосибирск, 1994. Т. 1, N 2. С. 18-39.

18. Колоколов A.A., Девятерикова М.В. Анализ устойчивости некоторых алгоритмов дискретной оптимизации // Автоматика и телемеханика. 2004. N 3. С. 48-54.

19. Колоколов A.A., Заозерская JT.A. О среднем числе итераций некоторых алгоритмов для решения задачи об упаковке множества // Материалы XIV Байкальской международной школы-семинара "Методы оптимизации и их приложения". Иркутск, 2008. Т.1. С. 388-395.

20. Конвей Р.В., Максвелл B.JL, Миллер Л.В. Теория расписаний. М.: Наука, 1975. 360 с.

21. Корбут A.A., Финкелыитейн Ю.Ю. Дискретное программирование. М.: Наука, 1969. 368 с.

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

23. Кочетов Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации // Дискретная математика и ее приложения. Сборник лекций молодежных и научных школ по дискретной математике и ее приложениям, М: МГУ, 2001. С. 87-117.

24. Кристофидес Н. Теория графов. Алгоритмический подход. М: Мир, 1978. 420 с.

25. Кук С.А. Сложность процедур вывода теорем // Киберн. сб. Новая серия, 1975. Вып. 12. - С. 5-15.

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

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

28. Подчасова Т.П., Португал В.М., Татаров В.А., Шкурба В.В. Эвристические методы календарного планирования. Киев: Техника, 1980.

29. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. М.: Мир, 1989. 478 с.

30. Рейногольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. Пер.с англ. М.: Мир, 1980. 476 е.,ил.

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

32. Сервах В.В. Календарное планирование с работами единичной длительности // Материалы межреспубликанского семинара по дискретной оптимизации. Киев, 1990. С. 66

33. Сервах В.В. Алгоритм решения задачи календарного планирования с единичными длительностями работ // В кн. Дискретная оптимизация и анализеложных систем, ВЦСО АН СССР. Новосибирск, 1989. -С. 99-107

34. Сервах B.B. Эффективные алгоритмы для некоторых задач календарного планирования // В кн. Методы решения и анализа задач дискретной оптимизации. Сб.научных трудов под ред. A.A. Колоколова, Омск, ОмГУ, 1992. С. 94-106.

35. Симанчев Р.Ю., Уразова И.В. О смео/сности вершин многогранника гамилътоновых циклов // Информационный бюллетень Ассоциации матем. программирования. Научн. изд. Екатеринбург: УРО РАН, 2003. N 10. С. 208.

36. Симанчев Р.Ю., Уразова И.В. Алгоритм проверки фасетности опорных неравенств //IV Всероссийская конференция "Проблемы оптимизации и экономические приложения Омск. 2009. С. 164.

37. Симанчев Р.Ю., Уразова И.В. Оценки числа целочисленных вершин, смежных с дробной в симметричной задаче коммивояжера // Пятая азиатская международная школа-семинар "Проблемы оптимизации сложных систем". Новосибирск, 2009. С. 210-214.

38. Симанчев Р.Ю., Уразова И.В. О задаче упаковки вершин ациклического орграфа в полосу фиксированной ширины // ДОСДМ, 2010. N 9. С. 56-59.

39. Симанчев Р.Ю., Уразова И.В. Целочисленная модель задачи минимизации общего времени обслуживания параллельными приборами единичных требований с предшествованиями // Автоматика и телемеханика, 2010. N 10. С. 100-106.

40. Симанчев Р.Ю., Уразова И.В. Многогранник расписаний обслуживания идентичных требований параллельными приборами // Дискретный анализ и исследование операций, 2011. N 1. С. 87-92.

41. Симанчев Р.Ю. О ранговых неравенствах, порождающих фасеты многогранника связных к-факторов // Дискретный анализ и исследование операций, 1996. Т.З. С. 84-110.

42. Симанчев Р.Ю. Смежность вершин многогранника к-факторов // Математические структуры и моделирование, 1998. Вып. 2. - С. 3950.

43. Симанчев Р.Ю. Структура нецелочисленных вершин релаксации многогранника к-факторов // Математические структуры и моделирование, 1998. Вып. 1. - С. 20-26.

44. Симанчев Р.Ю. Выпуклые многогранники и фасетные неравенства // Учебно-методическое пособие, ОмГУ, 1999. 39 с.

45. Сотсков Ю.Н. Оптимальное обслуживание двух требований при регулярном критерии // Автоматизация процессов проектирования, Минск:ИТК АН БССР, 1985. С.52-62.

46. Схрейвер А. Теория линейного и целочисленного программирования. М.: Мир, 1991. Т.2. - 342 с.

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

48. Танаев B.C., Гордон B.C., Шафранский В.В. Теория расписаний. Одностадийные системы. М.: Наука, 1987. 384 с.

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

50. Теория расписаний и вычислительные машины /под ред. Э.Г. Кофф-мана. М.: Наука, 1984.

51. Уразова И.В. О смежности дробных и целочисленных вершин многогранника задачи коммивояжера // Математические структуры и моделирование. Сб. научн. тр. ОмГУ, 2004. Вып. . С. 137-143.

52. Уразова И.В. L-структура Лагранжевых релаксаций блочно-диагональной задачи об упаковке // III Всероссийская конференция "Проблемы оптимизации и экономические приложения". Омск, 2006. С. 128-132.

53. Уразова И.В. Результаты вычислительного эксперимента для одной задачи теории расписаний //IV Всероссийская конференция "Проблемы оптимизации и экономические приложения". Омск, 2009. С. 169.

54. Уразова И.В. Варьирование директивного срока в одной задаче теории расписаний // Материалы Российской конференции "Дискретная оптимизация и исследование операций". Новосибирск, 2010. С. 149.

55. Уразова И.В. Класс правильных неравенств для задачи упаковки вершин ациклического орграфа в полосу заданной ширины // Вестник Омского университета, 2011. N2(60). С. 48 52.

56. Уразова И.В. Новый класс правильных неравенств для задачи Рт\ргес\р^ = 1|Стах // Информационный бюллетень АМП, N 12 (Тез. докл. Всеросс. конф. МпиП). Екатеринбург, Уро РАН, 2011. С. 211213.

57. Финкелыитейн Ю.Ю. Теоретическая оценка максимального числа итераций для полностью целочисленного алгоритма Гомори // Проблемы кибернетики. М.: Наука, 1973. Вып. 26. - С. 315-326.

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

59. Хачиян Л.Г. Полиномиальные алгоритмы в линейном программировании // ДАН СССР, 1979. Т.244. С.1093-1096.

60. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974. 520 с.

61. Шевченко В.Н. Задача составления оптимального расписания работы на п станках 11 Проблемы кибернетики. М.: Наука, 1967. Вып. 18. - С. 129-146.

62. Шевченко В.Н. Построение правильных отсечений в целочисленном линейном программировании // Тр. 5-й Зимней школы-симпозиума по мат. программированию и смежным вопросам. М., 1973. Вып. 2. С. 266-272.

63. Шевченко В.Н. Линейное программирование и теория линейных неравенств. Горький: Изд-во Горьк. ун-та, 1977.

64. Шевченко В.Н. Выпкулые многогранные конусы, системы сравнений и правильные отсечения в целочисленном программировании // Комбинаторно-алгебраические методы в прикладной математике. Горький: Изд-во Горьк. ун-та, 1979. С. 109-119.

65. Шевченко В.Н. Качественные вопросы целочисленного программирования. М.: Физматлит, 1995. 190 с.

66. Шкурба В.В. Задача трех станков. М:Наука, 1976. 96 стр.

67. Akers S.B. A graphical approach to production scheduling problems 11 Oper.Res., 1956. Vol.4, N 2. - P.244-245.

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

69. Balas E. On the facial structure of sheduling polyhedra // Mathematical Programming Study, 1985. N 24. P. 179-218.

70. Balas E. On the convex hull of the union of certain polyhedra // Oper. Res. Let., 1988. N 7. P. 279-283.

71. Balas E. The asymmetric assignment problem and some new facets of the travelling salesman polytope on directed graph // SIAM Journal on Discrete Math., 1989. N 3. P. 425-451.

72. Balas E., Fischelti M. A lifting procedure for the asymmetric travelling salesman polytope and a large new class of facets // Math. Prog., 1995. N 68. P. 241-265.

73. Blazewicz J., Lenstra J.K., and Rinnoy Kan A.H.G. Scheduling subject to resource constraints: Classfication and complexity // Discrete Applied Mathematics, 1983. V.5, N.l. - P.ll-24.

74. Bolotashvily G., Kovalev M., Girlich E. New facets of the Linear Ordering Polytope // SIAM Journal on Discrete Mathematics, 1999. V. 12. N 3.

75. Brucker P. Scheduling algorithms. Springer-Verlag Berlin Heidelberg, 1998.

76. Brucker P., Drexl A., Mohring R., Neumann K. and Pesch E. Resource-constrained project scheduling: Notation, classification, models, and methods // European Journal of Operational Research, 1999. V.112. - P. 3-41.

77. Brucker P., Knust S. Complex Scheduling. Springer, 2006.

78. Canovas L., Landete M., Marrin A. On the facets of the simple plant location packing polytope // Discrete Applied Mathematics, 2002. V. 124, N 1-3. P. 27-53.

79. Chvatal V. On certain polytopes assotiated with graph // Jornal of Combinatorial Theory (B), 1975. N 18. P. 138-154.

80. Chopra S., Rinaldi G. The graphical asymmetric travelling salesman polyhedron: Symmetric inequalities // SIAM Journal on Discrete Mathematics, 1996. V. 9. N 4. P. 602-624.

81. Coffman E.G., Jr, Graham R.L. Optimal scheduling of two processor systems. Acfa Informat., 1972. N 1. P. 200-213.

82. Conway R.W., Maxwell W.L. and Miller L.W. Theory of Sheduling. Addison-Wesley, 1967.

83. Crowder H., Jonson E.L. and Padberg M.W.Solving large-scale zero-one linear programming problems // Oper. Res., 1983. N 31. P. 803-834.

84. Cho D.C., Johnson E.L., Padberg M., Rao M.R. On the uncapacitated plant location problem I: valid inequalities and facets // Mathematics of Operations Research, 1983. V. 8. P. 579-589.

85. Cho D.C., Padberg M., Rao M.R. On the uncapacitated plant location problem II: facets and lifting theorems // Mathematics of Operations Research, 1983. V. 8. P. 590-612.

86. Fujn M., T. Kasami, K. Ninimiya. Optimal sequencing of two equivalent processors // SIAM J. Appl. Math., 1969. N 17. P. 784-789.

87. Garey M.R., Johnson D.S. Strong NP-completeness results: Motivation, examples, and implications. // Journal of the ACM, 1978. V. 25. - P.499-508.

88. Gomory R.E. Integer faces of polyhedron // Proc. Nat. Acad. Sci. USA, 1967. V. 57. N 1. - P. 16-18.

89. Gomory R.E. Some polyhedra related to combinatorial problems //J. Linear Algebra and Its Applications, 1969. V. 2. N 4. - P. 451-558.

90. Gordon V.S., Potts C.N., Strusevich V.A., Whitehead J.D. Single machine scheduling models with deterioration and learning: handling precedence constraints via priority generation // Journal of Scheduling,2008. V.ll, N.5. - P.357-370.

91. Grotschel M., Holland O. Solution of large-scale symmetric travelling salesman problems // Math. Program., 1991. N 51. P. 141-202.

92. Grotschel M., Lovasz L., Schrijver A. The ellipsoid method and its consequences in combinatorial optimization // Combinatorica, 1981. V. 1. N 2. - P. 169-197.

93. Grotschel M., Junger M. and Reinelt G. Facets of the linear ordering polytope // Mathematical Programming, 1985. N 33. P. 43-60.

94. Grotschel M., Padberg M.W. Polyhedral computations // The Travelling Salesman Problem. Ed. by E.L. Lawler etc., 1985. John Wiley and Sons Ltd.

95. Grotschel M., Junger M., Reinelt G. A cutting plane algorithm for the linear ordering problem // Oper. Res., 1984. V. 32. P. 1195-1220.

96. Grotschel M., Pulleyblank W.R. Clique tree inequalities and the symmetric travelling salesman problem // Mathematics of Oper. Res., 1986. V. 11. N 4. P. 537-569.

97. Hammer P., Johnson E., Peled U. Facets of regular 0-1-polytopes // Math. Prog., 1975. N 8. P. 179-206.

98. Hu T.C. Parallel sequencing and assembly line problems // Operation Research, 1961. N 9. P. 841-848.

99. Herroelen W., Demeulemeester E., Bert De Reyckyl classification scheme for project scheduling // Project schedling: recent models, algorithms, and applications (edited by Jan Weglarz,) USA, 1999 P.l-26.

100. Jeroslow R. Cutting-plane theory: algebraic method [ Discrete Math., 1978. V. 23. N 2. - P. 121-150.

101. Hausmann D. Adjacency on Polytopes in Combinatorial Optimization Oelschlager, Cambridge, MA, 1979.

102. Kolish R., Padman R. An Integrated Survey of Project Sheduling // 1997. 1959.

103. Kolish R., Sprecher A. PSPLIB A project scheduling problem librory // Manuscripte aus den Instituten fur Betriebswirtschaftshehre, 1996. N 396, Kiel, Germany.

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

105. Kovalyov M. Improving the complexities of approximation algorithm for optimization problems. // Operations Research Letters, 1995.- V.17. -P.85-87.

106. Lawner E.L., Lenstra J.K., Rinnooy Kan A.H.G., Shmoys D.B. Sequencing and scheduling: Algorithms and complexity. // Handbook in Operations Research and Management Science (Graves S.C., Rinnooy Kan A.H.G., Zipkin P., Eds.) NorthHolland, 1993. V. 4.

107. Lenstra J.K., Rinnooy Kan. Complexity of scheduling under precedence constraints // Oper. Res., 1978. N 26. P. 22-35.

108. Mokotoff E. An exact algorithm for the identical parallel machine scheduling problem // Europ. J. of Oper. Res., 2004. V. 152. - P. 758-769.

109. Nemhauser G.L., Trotter L. Properties of vertex packing and independence system polyhedra [ Math. Prog., 1993. N 6. P. 48-61.

110. Project scheduling: recent model, algorithm and applications // edt. by-Jan Weglarz. Kluwer Academic Publishers, 1999. 552 p.

111. Pulleyblank W.R. Polyhedral combinatorics. North-Holland, 1989. V. 1.

112. Pulleyblank W.R. Facet generating techniques. Thomas J. Watson Research Center, IBM Corporation P.O. Box218. Yorktown Heights, New York, 1993.

113. Queyranne M., Wang Y. A cutting plane procedure for precedence-constraned single machine scheduling. Working paper. Faculty of Commerce. University of British Columbia. Vancouver. Canada, 1991.

114. Queyranne M., Wang Y. Single-machine scheduling polyhedra with precedence constraints // Mathematics of Oper. Res., 1991. N 16. P. 1-20.

115. Queyranne M. Structure of simple scheduling polyhedron // Mathematical Programming., 1993. N 58. P. 263-285.

116. Reinert K. A polyhedral Approach to Sequence Aligment Problems // PhD thesis. Germany, 1999.

117. Servakh V.V. Dynamic programming algorithms for some scheduling problems // ECCO VIII, Conf. of European Chapter of Combinatorial Optimization, Poznan, May 1995: Abstracts. Poznan,1995. P.80.

118. Schrijver A. On cutting planes. Annals of Discrete of Mathematics, 1980. N 9. P. 291-296.

119. Schrijver A. Combinatorial optimization. Springer-Verlag Berlin Heidelberg, 2003. V. A,B,C.

120. Schulz A.S., Queyranne M. Polyhedral Approaches to Machine Scheduling. Berlin, 1994.

121. Schulz A.S. Polytopes and Scheduling. Berling, 1996.

122. Schulz A.S., Philips C.A., Shmoys D.B., Stein C., Wein J. Improved Bounds on Relaxations of a Parallel Machine Scheduling Problem // Journal of Combinatorial Optimization, 1998. N 1. P. 413-426.

123. Simanchev R.Yu. The Support inequalities and facets of combinatorial polytops // Intern, conf. "Optimal Discrete Structures and Algorithms Rostock, 1997. P. 62.

124. Ullman J.D. Complexity of sequencing problems // Coffman, 1976. P.

125. Wagner H.M. An integer programming model for machine scheduling // Naval Research Logistics Quarterly, 1959. N 6. P. 131-140.131. http://www.mathematik.uni-osnabrueck.de/reseach/OR/class139.164.