Помощь в написании студенческих работ
Антистрессовый сервис

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

Диссертация: Алгоритмы решения NP-трудных задач минимизации суммарного запаздывания и минимизации времени выполнения проекта и их применение в комбинаторной оптимизации
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

Принято считать, что исследование задач теории расписаний началось с публикации С. Джонсоном своей работы, в которой рассматривалась задача выбора очередности обслуживания множества деталей, каждая из которых должна пройти последовательную обработку на нескольких станках с целью минимизации момента окончания обслуживания всех деталей. Начиная с первых публикация по теории расписаний выяснилось… Читать ещё >

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

Содержание

  • 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. 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. Нижняя оценка Mingozz
      • 3. 2. 5. Оценка LBlg
    • 3. 3. Отношение оптимальных значений целевой функции для задач с прерываниями и без прерываний
      • 3. 3. 1. Доказательство гипотезы для случая задачи RCPSP с одним ресурсом
    • 3. 4. Задача построения расписания для параллельных машин
    • 3. 5. Частный случай задачи RCPSP с одним кумулятивным ресурсом мощности Q и р3 =
    • 3. 6. Свойства задач построения расписания с ограничениями предшествования
      • 3. 6. 1. Планарность сетевого графика для задач RCPSP и PMS
      • 3. 6. 2. Алгоритм укладки сетевого графика на плоскости
  • — 53.6.3 Решение обратного примера для задач RCPSP и PMS 157 3.7 Метаэвристический алгоритм решения задачи RCPSP
    • 3. 7. 1. Алгоритм АСО в рамках 1С: УСО

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

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

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

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

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

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

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

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

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

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

Список использованных источников

включает 110 наименований.

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

169 — i

Показать весь текст

Список литературы

  1. Р. Динамическое программирование М.: ИЛ, 1960. — 400 с.
  2. В.Я., Шкурба В. В. Теория расписаний. Задачи и методы решений // Кибернетика 1971. — № 1. — С. 89−102.
  3. В.Н., Ловецкий С. Е. Методы решения экстремальных комбинаторных задач (обзор) // Известия АН СССР, Техническая кибернетика. 1968. — № 4. — С. 82−93.
  4. В.Н., Ловецкий С. Е. Методы решения экстремальных задач комбинаторного типа (обзор) // Автоматика и телемеханика. 1968. -№ 11.-С. 68−93.5. под редакцией Буркова В. Н. Математические основы управления проектами М: Высшая школа, 2005, — 432 с.
  5. Е.Р. Гибридный алгоритм решения задачи минимизации суммарного запаздывания для одного прибора // Информационные технологии, 2007, № 1 — С. 30−37.
  6. Е.Р., Лазарев А. А. Доказательство NP-трудности частного случая задачи минимизация суммарного запаздывания для одного прибора // Известия АН: Теория и системы управления. 2006.№.3. С. 120−128
  7. Е.Р. Алгоритмы решения проблемы 1 || Х^Т, — и чётно-нечётного разбиения // Материалы XLIII Международной научной студенческой конференции «Студент и научно-технический прогресс»: Математика. Новосиб. гос. ун-т. Новосибирск, 2005. — С. 201−202
  8. Гафаров Е. Р. Гибридный алгоритм решения проблемы 1 11
  9. Матеррталы XLIV Международной научной студенческой конференции «Студент и научно-технический прогресс»: Математика. Новосиб. гос. ун-т. Новосибирск, 2006. — С. 190−191
  10. Е.Р. Задачи теории расписаний. Алгоритмы и применение. // Труды 49 научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук»: Управление и прикладная математика. Москва-Долгопрудный, 2006. — С. 82−83.
  11. Е.Р. Алгоритмы решения NP-трудных задач теории расписаний и разбиения // Труды всероссийской конференции студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования» Москва, 2006. — С. 120−121.
  12. М., Джонсон Д. Вычислительные машины и труднорешаемые задачи: Пер. с англ. М.: Мир, 1982. — 416 с.
  13. В.А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов М:Наука, 1990, — 384 с.
  14. P.M. Сводимость комбинаторных проблем // Кибернетический сборник. М.: Мир. — 1972. — Вып. 12. — С. 16−38.
  15. А.Г. Методы решения задачи минимизации суммарного запаздывания для одного прибора и задачи Разбиения: Дис. канд. физ.-мат. наук. Москва, 2007. — 126 с.
  16. М.Я. Интервальные е приближенные алгоритмы решения дискретных экстремальных задач: Дис. канд. физ.-мат. наук. — Минск, 1986. — 110 с.
  17. А.А., Сигал И. Х., Финкельштейн Ю. Ю. Методы ветвей и границ. Обзор теорий, алгоритмов, программ и приложений // Operations Forsch. Statist., Ser. Optimiz. — 1977. — V.8, N.2. — P. 253—280.
  18. А.А., Сигал И. Х., Финкельштейн Ю. Ю. Гибридные методы в дискретном программировании j j Изв. АН СССР. Техн. кибернет.- 1988. № 1. — С. 65−77.
  19. А.А., Финкельштейн Ю. Ю. Приближенные методы дискретного программирования // Изв. АН СССР. Техн. кибернет. — 1983. № 1. — С. 165−176.
  20. А.А. Алгоритмы в теории расписаний, основанные на необходимых условиях оптимальности // Исследования по прикладной математике. Казань: Изд-во Казан, гос. ун-та, 1984. -Вып. 10. — С. 102−110.
  21. А.А. Алгоритмы декомпозиционного типа решения задачи минимизации суммарного запаздывания // Исследования по прикладной математике. Казань: Изд-во Казан, гос. ун-та, 1990. -Вып. 17. — С. 71−78.
  22. А.А. Эффективные алгоритмы решения некоторых задач теории расписаний для одного прибора с директивными сроками обслуживания требований: Дис. канд. физ.-мат. наук. Казань, 1989.- 108 с.
  23. А.А., Гафаров Е. Р. Теория расписаний. Минимизациясуммарного запаздывания для одного прибора. М.: Вычислительныйцентр им. А. А. Дороницына РАН, 2006. 134 с. i
  24. А.А., Гафаров Е. Р. Теория расписаний. Исследование задач с отношениями предшествования и ресурсными ограничениями. М.: Вычислительный центр им. А. А. Дороницына РАН, 2007. — 80 с.
  25. А.А. Графический подход к решению задач комбинаторной оптимизации // Атоматика и телемеханика, 2007, № 4 — С. 13−23.
  26. X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985, — 512 с.
  27. М.А., Сигал И. Х., Галимьянова Н. Н. Алгоритмы параллельных вычислений для решения некоторых классов задач дискретной оптимизации. М.: Вычислительный центр им. А. А. Дороницина РАН, 2005. — 44 с.
  28. Современное состояние теории исследования операций Под ред. Н. Н. Моисеева. — М.: Наука, 1979. — 464 с.
  29. И.Х., Иванова А. П. Введение в прикладное дискретное программирование: теория и вычислительные алгоритмы. М.: Физматлит, 2002. — 240 с.
  30. B.C., Шкурба В. В. Введение в теорию расписаний. М.: Наука, 1975.
  31. B.C., Гордон B.C., Шафранский Я. М. Теория расписаний. Одностадийные системы. М.: Наука. Гл. ред. физ.-мат. лит., 1984. -384 с.
  32. B.C., Сотпсков Ю. Н., Струсевич В. А. Теория расписаний. Многостадийные системы. М.: Наука. Гл. ред. физ.-мат. лит., 1989. — 328 с.
  33. B.C., Ковалев М. Я., Шафранский Я. М. Теория расписаний. Групповые технологии. Минск: Институт технической кибернетики НАН Беларуси, 1998. — 290 с.
  34. Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования М.: Наука, 1976.
  35. В.Р., Веселовский В. Е., Злотов А. В. и др. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности М.: Наука. — 2000.
  36. В.В., Подчасова Т. П., Пшичук А. Н., Тур Л.П. Задачи календарного планирования и методы их решения Киев: Наукова думка, 1966. — 154 с.
  37. Alidaee В., Gopalan S. A note of the equivalence of two heuristics to minimize total tardiness // European Journal of Operation Research. -1997. V.96. — P. 514−517.
  38. Baev I.D., Meleis W.M., Eichenberger A. Lower bounds on Precedence-Constrained Scheduling for Parallel Processors //IEEE, 2000.
  39. Baker K.R. Introduction to sequencing and scheduling. Wiley, New York. — 1974.
  40. Baker K.R., Bertrand W.M. A dynamic priority rule for scheduling against due dates // Journal of Operation Management. 1982. — V.3. — P. 37−42.
  41. Baker K.R., Schrage L. Finding am optimal sequence by dynamic programming: an extension to precedence-related tasks // Operations Research. 1978. — V. 26. — P. 111−120.
  42. A. Bauer, B. Bullnheimer, R.F.Hartl, C. Strauss. Minimizing Total Tardiness on a Single Machine Using Ant Colony Optimization. // Proceedings of the 1999 Congress on Evolutionary Computation (CEC99). Washington D. C, 1999. — P. 1445−1450.
  43. Blazewicz J., Ecker K., Pesch E., Schmidt G., Weglarz J. Scheduling Computer and Manufactoring Processes. Springer Berlin. — 1996.
  44. Brucker P. Scheduling Algorithms. Springer-Verlag, 2001. — 365 p.
  45. Brucker P., Lenstra J.K., Rinnoy Kan A.N.G. Complexity of machine scheduling problems // Math. Cent. Afd. Math Beslisk. Amsterdam, 1975. — BW 43. — 29 pp.
  46. Brucker P., Knust S. Complex scheduling Springer-Verlag Berlin, Heidelberg, Germany, 2006
  47. Burkov V.N. Problems of optimum distribution of resources // Control and cibernetics, 1972, vol.1, №½ — P. 27−41.
  48. 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. ,
Заполнить форму текущей работой

Сессия? Спокойно!