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

• Уразова, Инна Владимировна
• кандидат физико-математических наук
• 2011

Оглавление диссертации кандидат физико-математических наук Уразова, Инна Владимировна

Введение

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|Стаа;. Проведена аппробация, подтвердившая эффективность разработанных алгоритмов. В процессе аппробации сформирован список тестовых задач высокой размерности с точными решениями.

Заключение

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

Список литературы диссертационного исследования кандидат физико-математических наук Уразова, Инна Владимировна, 2011 год

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.