Помощь в учёбе, очень быстро...
Работаем вместе до победы

Разработка точных и приближенных алгоритмов построения расписаний для производственных систем

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

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

Содержание

  • 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-приближенный полиномиальный алго ритм для указанной задачи с вогнутой целевой функцией.

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

Заключение

.

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

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

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

  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.
Заполнить форму текущей работой

Пора сдавать?