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

• Кононова, Полина Александровна
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Кононова, Полина Александровна

Введение

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

1.1 Сведение к ограниченной задаче.

1.2 Перестановочные расписания.

1.3 Сложность задачи.

1.3.1 Сложность КАР-задачи.

1.3.2 ЙРР-задача с быстрой/медленной скоростью передачи

1.3.3 Я АР- задача с быстрой / медленной скоростью передачи

2 Нижние и верхние оценки оптимума для цеховых задач потокового типа с активным буфером

2.1 Математическая модель.

2.2 Нижние оценки.

2.2.1 Оценка линейного программирования.

2.2.2 Оценка Джонсона

2.3 Поиск с чередующимися окрестностями.

2.4 Окрестности.

2.5 Численные эксперименты.

3 Нижние и верхние оценки оптимума для цеховых задач потокового типа с пассивным буфером

3.1 Постановка задачи и ее ЦЛП формулировки.

3.2 Окрестности.

3.3 Общая схема метода и ее варианты

3.4 Построение примеров с известным оптимумом.

3.5 Численные эксперименты.

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

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

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

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

Цеховые задачи теории расписаний интенсивно изучаются с середины 50-х годов прошлого столетия. Большинство этих задач трудны как теоретически, то есть являются КР-трудными, так и практически, то есть требуют слишком много времени для нахождения точного решения на примерах малой размерности, 15-20 работ. Все эти свойства характерны для цеховой задачи с цифровым буфером. Поэтому одним из перспективных подходов является построение хороших нижних оценок и разработка методов локального поиска с выбором окрестностей, учитывающих структуру задачи.

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

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

Научная новизна. Оригинальность и научная новизна полученных результатов состоит в следующем.

1. Проведено исследование сложности цеховой задачи на двух машинах с цифровым буфером. Доказано, что в общем случае задача является ОТ-трудной в сильном смысле. Выделены полиномиально разрешимые случаи.

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

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

4. Разработаны итерационные методы локального поиска для решения задачи с активным и пассивным методами загрузки буфера.

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

Апробация работы. Все разделы диссертации прошли апробацию на следующих конференциях в России и за рубежом:

Международный симпозиум по математическому программированию (¡БМР), Германия, Берлин, 2012;

Конференция европейского общества комбинаторной оптимизации (ЕССО), Турция, Анталия, 2012;

Балканская конференция по исследованию операций (Ва1с(Ж), Греция, Салоники, 2011;

Международная конференция по управлению планирования и теории расписаний (PMS), Франция, Тур, 2010;

Международный симпозиум по исследованию операций (OR), Германия, Мюнхен, 2010;

Российская конференция "Дискретная оптимизация и исследование операций", Новосибирск, Алтай, 2010;

Всероссийской конференции "Проблемы оптимизации и экономические приложения", Омск, 2009 и 2012;

Азиатская международная школа-семинар "Проблемы оптимизации сложных систем", Кыргызская Республика, г.Бишкек, 2009;

Научные семинары Института математики им. С,Л. Соболева СО РАН.

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

Публикации. По теме диссертации автором опубликовано 12 работ, в том числе 3 статьи в журналах из списка ВАК.

Объем и структура диссертации. Диссертация состоит из введения, трех глав и списка литературы (46 наименований). Объем диссертации — 106 страниц.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Кононова, Полина Александровна

Заключение

• Для цеховой задачи потокового типа с цифровым буфером введены понятия активного и пассивного буфера. Для обоих вариантов задачи получены новые математические модели в терминах целочисленного линейного программирования. Доказана КР-трудность рассматриваемых задач и некоторых их частных случаев. Выделены полиномиально разрешимые подклассы. Для обратной задачи минимизации буфера при заданном времени выполнения всех работ установлена ЫР-трудность задачи, вычисление минимального размера буфера при заданной последовательности выполнения работ является полиномиально разрешимой задачей.

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

• Разработанные численные методы реализованы в виде комплекса программ. Для проведения вычислительных экспериментов разработан новый класс тестовых примеров с известным значением оптимума. Результаты численных экспериментов на этом и других классах показали высокую эффективность предложенного подхода.

Список литературы диссертационного исследования кандидат физико-математических наук Кононова, Полина Александровна, 2012 год

1. Гончаров Е. Н., Кочетов Ю. А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения // Дискретный анализ и исследование операций. Сер. 2. — 1999. — Т. 6, № 1.- С. 12-32.

2. Кононова П.А. Алгоритм локального поиска для задачи выбора порядка презентаций медиа объектов // Труды ИВМиМГ, Информатика, 9. Новосибирск: Изд. ИВМиМГ СО РАН. — 2009.-С. 177-182.

3. Кононова П.А. Нижние и верхние оценки длины оптимального расписания презентаций медиа-объектов // Дискретный анализ и исследование операций. — 2012. — Том 19, №1. — С. 59-73.

4. Кононова П.А., Кочетов Ю.А. Локальный поиск с чередующимися окрестностями для задачи Джонсона с пассивным буфером // Дискретный анализ и исследование операций. — 2012. — Т. 19, № 5.- С.63-82.

5. Кочетов Ю., Младенович Н., Хансен П. Локальный поиск с чередующимися окрестностями // Дискретный анализ и исследование операций. Серия 2. 2003. - Том 10, № 1. - С. 11-43.

6. Aarts E. H. L., Korst J. H. M., Laarhoven van F. J. M. Simulated annealing // Local search in combinatorial optimization. Chichester: Wiley. 1997. - P. 91-120.

7. Aarts E. H. L., Lenstra J. K. (Eds.) Local Search in Combinatorial Optimization. — Chichester: John Wiley & Sons. 1997.

8. Ahuja R.K., Ergun O., Orlin J.B., Punnen A.P. A survey of very large-scale neighborhood search techniques // Discrete Appl. Math. — 2002.- V. 123, Issue 1-3. P. 75-102.

9. Bent R., Van Hentenryck P. A two stage hybrid local search for the vehicle routing problem with time windows // Transportation science.- 2004. Vol. 38, No. 4. - P. 515-530.

10. Blum C. Roli A. Metaheuristics in combinatorial optimization: Overview and conceptual comparison // ACM Computing Surveys (CSUR). 2003. - V.35, Issue 3. - P. 268-308.

11. Brimberg J., Hansen P., Mladenovic N. Convergence of variable neighborhood search // Les Cahiers du GERAD G-2000-73. Monreal, Canada, 2000.

12. Brimberg J., Mladenovic N. A variable neighborhood algorithm for solving the continuous location-allocation problem // Stud. Locat. Anal. 1996. - V. 10. - P. 1-12.

13. Brucker P., Knust S., Complex Scheduling. Berlin: Springer, 2006.

14. Burke E. K., Causmaecker de P., Petrovic S., Berghe G. V. Variable neighbourhood search for nurse rostering problems // MIC'2001 4th Metaheuristics Intern, conf. Porto, July 16-21. - 2001. - P. 755-760.

15. Burke E.K., Kendall G. (Eds.) Search Methodologies. Introductory Tutorials // Optimization and Decision Support Techniques. — Berlin: Springer, 2005.

16. Davidovic T., Hansen P., Mladenovic N. Variable neighborhood search for multiprocessor scheduling with communication delays // MIC'2001- 4th Metaheuristics Intern, conf. Porto, July 16-21 2001. - P. 737741.

17. Dreo J., Petrowski A., Siarry P., Taillard E., Metaheuristics for Hard Optimization, — Springer, 2006.

18. Falkenauer E. A Hybrid grouping genetic algorithm for bin packing // J. Heuristics-1996. V. 2, N. 1- P. 5 - 30.

19. Festa P., Resende M. G. C., GRASP: An annotated bibliography. In: C. C. Ribeiro, P. Hansen (Eds.) Essays and surveys in metaheuristics.- Kluwer Academic Publishers. 2002. — P. 325-368.

20. Fischetti M., Lodi A. Local branching. // Math. Programming. — 2003.- V. 98, N. 2. P. 23-47.

21. Garey M. R., Johnson D. S., Computer and intractability: a guide to the theory of NP-completness. San Francisco, CA: Freeman, 1979.

22. Glover F. Future paths for integer programming and links to artificial intelligence. // Comp. Oper. Res. 1986. - V. 13. - P. 533-549.

23. Glover F., Laguna M. Tabu Search. — Dordrecht: Kluwer Acad. Publ., 1997.

24. Goldberg D. E. Genetic algorithms in search, optimization, and machine learning. Reading, MA: Addison-Wesley, 1989.

25. Gutin G. Exponential neighborhood local search for the traveling salesman problem // Comput. Oper. Res. — 1999. — V. 26. — P. 313320.

26. Gutin G., Yeo A. Small diameter neighborhood graphs for the traveling salesman problem: four moves from tour to tour // Comput. Oper. Res. 1999. - V. 26. - P. 321-327.

27. Hansen P, Mladenovic N. Variable neighborhood search for the p-median problem //Location Science — 1997. — V. 5. — P. 207-226.

28. Hansen P., Mladenovic N., Perez-Brito D. Variable neighborhood decomposition search //J. Heuristics. — 2001. — V. 7, N. 4. — P. 335-350.

29. Ierapetritou M.G., Floudas C.A. Effective continuous-time formulation for shortterm scheduling: I. multipurpose batch process // Ind. Eng. Chem. Res. 1998. - Vol. 37. - P. 4341 - 4359.

30. Johnson S.M., Optimal two- and three-stage production scheduling with setup time included. Naval Research Logistics Quarterly. — 1954.— V. 1, Issue 1- P. 61-68.

31. Kernighan, B.W., Lin, S.: An efficient heuristic procedure for partitioning graphs. Bell System technical Journal. — 1970. — V. 49.- P. 291-307.

32. Kochetov, Yu., Alekseeva, E., Levanova, T., Loresh, M.: Large neighborhood local search for the p-median problem. Yugoslav Journal of Operations Research. 2005. - V. 15, N 1. - P. 53-63.

33. Kochetov Yu., Kononova P., Paschenko M. Formulation Space Search Approach for the Teacher/Class Timetabling Problem // Yugoslav Journal of Operations Research. 2008, - V. 18, N 1. — P. 1-11.

34. Kononov A., Hong J.-S., Kononova P., Lin F.-C. Quantity-based buffer-constrained two machine flowshop problem: active and passive prefetch models for multimedia applications// Journal of Scheduling. — 2012.- V. 15, N.4. P. 487-497.

35. Kononov A., Kononova P., Hong J.-S. Two-stage multimedia scheduling problem with an active prefetch model // Preprints of the 13th IFAC Symposium on Information Control Problems in Manufacturing (Moscow, Russia, June 3 5, 2009).- P. 1997-2002.

36. Korte B., Vygen J., Combinatorial Optimization: Theory and Algorithms. Algorithms and Combinatorics 21 Springer, Berlin. 2000.

37. Lin F.-C., Hong J.-S., Lin B.M.T. A two-machine flow shop problem with processing time-dependent buffer constraints An application in multimedia problem // Computers and Operations Research.— 2009.— V. 36, N. 4. - P. 1158-1175.

38. Lin F.-C., Lai C.-Y., Hong J.S. Minimize presentation lag by sequencing media objects for auto-assembled presentations from digital libraries // Journal Data & Knowledge Engineering. V. 66, I. 3, 2008, P. 382-401.

39. Mladenovic, N., Plastria, F., Urosevic, D. Reformulation descent applied to circle packing problems. // Computers and Operations Research. 2005. - V. 32, N. 9. - P. 2419-2434.

40. Osman I. H., Laporte G. Metaheuristics: a bibliography // Ann. Oper. Res. 1996. - V. 63. - P. 513-628.

41. Papadimitriou, C. H., Kanellakis, P. C. Flowshop scheduling with limited temporary storage // Journal of the Association for Computing Machinery -1980.- V. 27, N.3. P. 533-549.

42. Salassa F. G. M. Matheuristics for Combinatorial Optimization Problems // Ph.D. Thesis.

43. Verhoeven M. G. A., Severens M. E. M., Aarts E. H. L. Local search for Steiner trees in graphs // Modem search, methods. N. Y.: John Wiley and Sons, Inc. 1996. - P. 117-129.

44. Wilbaut C., Hanafi S., Freville A., Balev S. Tabu search: global intensification using dynamic programming. // Control and Cybernetics. 2006. - V. 35, N. 3. - P. 579-588.

45. CPLEX http://www-142.ibm.com/software/products/ru/ru/ilogcple/.