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

• Романова, Анна Анатольевна
• кандидат физико-математических наук
• 2006

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

Введение

1. Задачи теории расписаний и сложность их решения

1.1. Формулировки задач.

1.2. Алгоритмическая сложность решения задач

2. Построение циклических расписаний для производственной линии

2.1. Сложность и свойства задач с различными критериями

2.2. Задача минимизации времени цикла с ограничением

2.3. Алгоритм для задачи минимизации времени цикла с ограничением

3. Аппроксимационные схемы решения задач

3.1. Основные определения.

3.2. Аппроксимационная схема для задачи минимизации времени цикла с ограничением.

3.3. Аппроксимационная схема для задачи о поставках продукции с одним потребителем.

4. Задача построения расписания для производственной системы открытого типа.

4.1. Исследование структуры оптимальных решений

4.2. Модель целочисленного программирования и ее свойства

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

На многих предприятиях производство представляет собой сложный технологический процесс, для управления которым требуется решать большое число задач эффективного распределения ресурсов и построения расписаний. В связи со сложностью рассматриваемых задач при принятии решений целесообразно использовать модели и методы системного анализа, исследования операций и оптимизации. Изучению таких задач и построению алгоритмов их решения посвящены [4,6,8,14,19,31,32,34,53,58,64] и другие работы.

В последние годы значительное внимание уделяется составлению циклических расписаний [44,56,70], которые часто используются в производственных системах в силу их простоты и удобства применения. Сложность задач построения циклических расписаний исследовалась в [55,56,60,63,65,70]. В силу трудности большинства таких задач основное внимание исследователей уделяется построению приближенных и эвристических алгоритмов. Такие алгоритмы предлагаются в [38,40,44,68]. С другой стороны, в [56,70] разработаны точные алгоритмы решения задач, основанные на методе ветвей и границ.

Исследование задач построения расписаний для классических производственных систем, например, систем открытого типа, также представляет большой научный интерес ввиду их широкой известности и практической важности [29,43].

Среди методов получения оптимальных решений задач построения расписаний следует выделить метод динамического программирования [2], метод ветвей и границ [43,56,70], различные алгоритмы комбинаторного характера [4,31,32,53,59].

При разработке методов решения задач теории расписаний важную роль играют свойства оптимальных решений, на основе которых поиск оптимального решения можно вести на сужении множества допустимых решений. Данный подход применяется к задаче построения расписания в производственной системе открытого типа [37,41].

Другим перспективным направлением является сведение задачи построения расписания к задаче целочисленного линейного программирования (ЦЛП). Этот подход используется, например, в [44,56]. В ряде известных методов решения задач ЦЛП применяется сведение исходной задачи к последовательности задач непрерывной оптимизации. На этом подходе основаны алгоритмы отсечения [3,11,34,35], декомпозиции [39], перебора L-классов [12], методы ветвей и границ [15,34].

Многие задачи теории расписаний относятся к числу iVP-трудных. В связи с этим значительное число исследований посвящено разработке приближенных алгоритмов их решения. Однако, как показывают современные результаты для ряда оптимизационных задач, мы сталкиваемся с некоторым "пределом приближаемости". Для одних задач существуют полиномиальные по времени аппроксимационные схемы (PTAS), когда при любом фиксированном е > 0 удается предложить полиномиальный алгоритм с относительной погрешностью, не превосходящей 1 + е. Для других задач не существует аппроксимационной схемы, но удается построить приближенные алгоритмы с константной оценкой точности. В этом случае имеется "барьер приближаемости", то есть такая константа С, что для любого С' < С задача нахождения С"-приближенного алгоритма является iVP-трудной задачей. Наконец, для задач третьего класса ни при какой константе С невозможно построение полиномиального С'-приближенного алгоритма (при условии Р ф NP). Естественно, важным представляется вопрос о том, к какому классу относится та или иная задача. В настоящее время исследование вопроса построения полиномиальных аппроксимационных схем представляет собой интенсивно развивающееся направление в разработке алгоритмов решения задач дискретной оптимизации [4,5,52,58].

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

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

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

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Романова, Анна Анатольевна

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

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

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

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

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

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

Заключение

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

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

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

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

3. Булатов В.П. Методы погружения в задачах оптимизации. Новосибирск: Наука, 1977. - 161 с.

4. Воегингер Г.Д., Севастьянов С.В. Линейная аппроксимационная схема для многопроцессорной задачи Open Shop // Дискретный анализ и исследование операций 1999. - Серия 1, Т. 6, N 2. - С. 3-22.

5. Гене Г.В., Левнер Е.В.: Эффективные приближенные алгоритмы для комбинаторных задач. Препринт. - ЦЭМИ, Москва, 1981.

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

7. Гимади Э.Х., Глебов Н.И. Дискретные экстремальные задачи принятия решений. Учебное пособие. - Новосибирск: НГУ, 1991.

8. Гимади Э.Х., Глебов Н.И., Перепелица В.А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики. М: Наука, 1975. - Вып. 31. - С. 35-42.

9. Глебов Н.И. Алгоритм составления расписания для двух работ // Управляемые системы. 1968. - Вып. 1. - С. 14-20.

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

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

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

13. Конвей Р.В., Максвелл B.JL, Миллер JI.B. Теория расписаний. -М.: Наука, 1975. 3G0 с.

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

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

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

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

18. Попков В.К. Математические модели связности. В трех частях. ИВМ и МГ СО РАН. Новосибирск, 2000-2002. - 560 с.

19. Романова А.А., Сервах В.В. О структуре оптимальных расписаний в задаче с нефиксированными маршрутами размерности 3x3. Препринт, 2002, Омск: изд-во ОмГУ. - 40 с.

20. Романова А.А. Об одной модели целочисленного программирования для задачи с нефиксированными маршрутами. Материалы конференции "Математическое программирование и приложения", Екатеринбург, 2003, С. 208-209.

21. Романова А.А., Сервах В.В. О структуре оптимальных расписаний задачи с нефиксированными маршрутами // Материалы Международной конференции "Дискретный анализ и исследование операций", Новосибирск, 2002. С. 221.

22. Романова А.А. О структуре оптимальных расписаний в задаче с нефиксированными маршрутами // Материалы XL Международной студенческой конференции "Студент и научно-технический прогресс", Новосибирск, 2002. С. 125-126.

23. Романова А.А., Сервах В.В. О построении циклических расписаний для задачи обработки однотипных деталей // Материалы конференции "Дискретный анализ и исследование операций", Новосибирск, 2004. С. 175.

24. Романова А.А., Сервах В.В. Алгоритмы решения одной задачи построения циклического расписания // Материалы XIII Байкальской международной школы-семинара "Методы оптимизации и их приложения", Иркутск, 2005. С. 557-582.

25. Сервах В.В. О задаче Акерса-Фридмана // Управляемые системы. Новосибирск: ИМ СО АН СССР, 1983, - Вып. 23. - С. 70-82.

26. Сервах В.В. Эффективно разрешимый случай задачи календарного планирования с возобновимыми ресурсами // Дискретный анализ и исследование операций. 2000. - Серия 2, том 7, N 1, -С. 75-82.

27. Севастьянов С.В. Полиномиально разрешимый случай задачи open-shop с произвольным числом машин // Кибернетика и системный анализ. 1992. - N 6. - С. 135-154.

28. Севастьянов С.В. Эффективное построение расписаний в системах открытого типа // Сибирский журнал исследования операций. 1994. - Т. 1, N 2. - С. 67-99.

29. Севастьянов С.В., Черных И.Д. Достаточное условие эффективной разрешимости задачи open shop // Дискретный анализ и исследование операций. 1996. - Т. 3, N 1. - С. 57-74.

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

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

32. Тимковский В.Г. Приближенное решение задачи составления расписания циклической системы // Экономика и математические методы, АН СССР. 1986. - N 1. - С. 171-174.

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

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

35. Akers S.E. A graphical approach to production scheduling problems. // Operations Research. 1956, - Vol. 4, N 2. - P. 244-245.

36. Akers S.B., Friedman J. A non-numerical approach to production scheduling problems. // Oper. Res. 1955, - Vol. 3. - P. 429-442.

37. Aldakhilallah К.A., Ramesh R. Cyclic scheduling heuristics for a reentrant job shop manufacturing environment // International Journal of Production Research. 2001, - Vol. 39(12). - P. 2635-2675.

38. Benders J.F. Partitioning Procedures for Solving of Mixed-Variables Programming Problems// Numer. Math. 1962. - Vol. 4, N 3. - P. 238-252.

39. Boudoukh Т., Penn M., Weiss G. Scheduling jobshops with some identical or similar jobs // Journal of Scheduling. 2001. - Vol. 4. -P. 177-199.

40. Brasel H., Harborth M., Tautenhahn Т., Willenius P. On the set of solutions of an Open Shop problem. Magdeburg, 1997.

41. Brasel H., Kluge D., Werner F. A polynomial algorithm for an open shop problem with unit processing times and tree conatraints // Discrete Appl. Math. 1995. - Vol. 59(1). - P. 11-21.

42. Brucker P., Hurink J., Jurisch В., Wostmann B. A branch & bound algorithm for the open-shop problem // Discrete Appl. Math. 1997. - Vol. 76. - P. 43-59.

43. Brucker P., Kampmeyer T. Tabu search algorithms for cyclic machine scheduling problems. Osnabrueck, Preprint, 2002, - P. 24.

44. Brucker P., Kravchenko S.A., Sotskov Y.N. On the complexity of two machine job-shop scheduling with regular objective functions. OR Spektrum. 1997. - Vol. 19(1). - P. 5-10.

45. Chauhan S.S., Eremeev A.V., Kolokolov A.A., Servakh V.V. Concave cost supply management problem for single manufacturing unit. In: Supply chain optimisation. Ed. by A. Dolgui, J. Soldek, O. Zaikin. Kluwer. Acad. Pbs., 2004. - P. 167-174.

46. Chauhan S.S., Eremeev A.V., Romanova A.A., Servakh V.V., Woeg-inger G. J. Approximation of the supply scheduling problem. // Operations Research Letters. 2005. - Vol. 33. - P. 249-254.

47. Chauhan S.S., J.-M. Proth: The concave cost supply Problem. // European Journal of Operational Research. 2003. - Vol. 148, N. 2, - P. 374-383.

48. Chen В., Potts C.N., Woeginger G.J. A review of machine scheduling: complexity, algorithms and approximability // Handbook of Combinatorial Optimization. Boston, MA: Kluwer Acad. Publ., 1998. V. 3. - P. 21-169.

49. Garey M.R., Johnson D.S. Scheduling tasks with nonuniform deadlines on two processors. SIAM J. Comput., 1977. Vol. 6(3). - P. 416-426.

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

51. Gonzalez Т., Sahni S. Open shop sheduling to minimize finish time// J.Assoc.Comput.Mach. 1976. - Vol.23. - N. 4. - P. 655-679.

52. Gonzalez Т., Sahni S. Flowshop and jobshop schedules: complexity and approximation. Oper. Res., 1978. - Vol. 26, N.l, - P. 36-52.

53. Hall N.G., Lee Т.Е., Posner M.E. The complexity of cyclic shop scheduling problems. //Journal of Scheduling, 2002. - Vol. 5, - P. 307-327.

54. Hanen C. Study of a NP-hard cyclic scheduling problem: The recurrent job-shop // European Journal of Operational Research. 1994.- Vol. 72. P. 82-101.

55. Hardgrave W.W., Nemhauser G.L. A geometric model and a graphical algorithm for a sequencing problem // Operations Research. -1963, Vol. 11, N 6, - P. 889-900.

56. Ibarra O., Kim C.E. Fast approximation algorithms for the knapsack and sum of subset problems.// Journ. of the ACM. 1975.- Vol. 22.- P. 463-468.

57. Johnson S.M. Optimal two-and-three-stage production schedules with set-up times included // Naval Res. Logist. Quart. 1954. -Vol. 1. - P. 61-68.

58. Kamoun H., Sriskandarajah C. The complexity of scheduling jobs in repetitive manufacruring systems // European Journal of Operational Research. 1993. - Vol. 70. - P. 350-364.

59. Karp R.M. Reducibility among combinatorial problems, in R. E. Miller and J. W. Thatcher (eds.), Complexify of Computer Computations, Plenum Press, New York, 1972. P. 85-103.

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

61. Lee Т., Posner M. Performance measure and schedules in periodic job shop // Operations Research. 1997. - Vol. 45. - P. 72-91.

62. Lenstra J.K., Rinnooy Kan A.H.G. Computational complexity of discrete optimization problems // Ann. Discrete Math. 1979. - Vol. 4.- P. 121-140.

63. McCormick S.T., Rao U.S. Some complexity results in cyclic scheduling // Mathematical and Computer Modeling, 1994. - Vol. 20. - P. 107-122.

64. Middendorf M., Timkovsky V.G. Transversal graphs for partially ordered sets: sequencing, merging and scheduling problems // J. Comb. Optim. 1999. - Vol. 3(4). - P. 417-435.

65. Prince C. Competetive genetic algorithms for open-shop sheduling problem // Math Meth Oper Res. 2000. - Vol. 52. - P. 389-411.

66. Rao U., Jackson P. Identical Jobs Cyclic Scheduling: Subproblems, Properties, Complexity and Solution Aproaches (Ithaca, NY: Cornell University Press), 1993.

67. Romanova A.A., Servakh V.V. On some cyclic machine scheduling problem // Abstracts of the XVII European Conference of Combinatorial Optimization (ECCO'2005), Minsk, 2005. P. 58-59.

68. Roundy R. Cyclic schedules for job shops with identical jobs // Mathematics of Operations Research, 1992, - Vol. 17, N 4, - P. 842-865.

69. Servakh V.V. A dynamic programming algorithm for somme project management problems. // Proceedings of the International Workshop "Discrete optimization methods in scheduling and computer-aided design", 2000. P. 90-92.

70. Sevast'janov S.V. Vector summation in Banach space and polynomial algorithms for flow shops and open shops // Math.Oper.Res. 1995.- V.20, N. 1. P. 90-103.

71. Sevastianov S.V., Woeginger G.J. Makespan minimization in open shops: A polynomial time approximation scheme // Math. Programming. 1998. - Vol.82, N 1-2. - P. 191-198.

72. Williamson D.P., Hall L.A., Hoogeveen J.A., Hurkens C.A.J., Lenstra J.K., Sevastianov S.V., Shmoys D.B. Short shop schedules // Opcr. Res. 1997. - Vol. 45, N 2. - P. 288-294.

73. Woeginger G. J. When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)? // INFORMS J. on Computing. 2000. - V. 12, N 1. - P. 57-74.