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

• Гафаров, Евгений Рашидович
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Гафаров, Евгений Рашидович

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4.2 Пример

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

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

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

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

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

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

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

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

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

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

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

3.2.5 Оценка LBlg.

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

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

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

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

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

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

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

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

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

Введение диссертации (часть автореферата) на тему «Алгоритмы решения NP-трудных задач минимизации суммарного запаздывания и минимизации времени выполнения проекта и их применение в комбинаторной оптимизации»

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

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

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

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

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

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

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

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

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

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

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Гафаров, Евгений Рашидович

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

169 — i

Список литературы диссертационного исследования кандидат физико-математических наук Гафаров, Евгений Рашидович, 2008 год

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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