Методы принятия оптимальных решений на основе анализа эффективности значений функции цели в задачах прямоугольной упаковки
Диссертация
Предложенные методы реализованы на ЭВМ. Результаты экспериментов показали, что существуют классы задач, на которых методы имеют различную результативность. Проведён анализ эффективности методов на различных классах задач и выделена область применимости разработанных методов. Это позволяет априорно сделать выбор лучшей схемы решения по классу рассматриваемых задач. Исследовано качество полученной… Читать ещё >
Список литературы
- L.V. Kantorovich. Mathematical methods of organizing and planning production (translation of the paper of 1939) // Management Science. 1960. 6(4): 366−422.
- P.C. Gilmore, R.E. Gomory. A linear programming approach to the cutting-stock problem // Operations Research. 1961. 9(6): 849−859.
- A.H. Land, A.G. Doig. An automatic method of solving discrete programming problems // Econometrica. 1960. 28(3): 497−520. '
- J.M. Valerio de Carvalho. LP models for bin packing and cutting stock problems // European Journal of Operational Research. 2002. 141: 253−273.
- G. Belov. Problems, models. and algorithms in one- and two-dimensional cutting. PhD thesis. Dresden University of Technology. 2003.
- Jl.В. Канторович, В. А. Залгаллер. Расчет рационального раскроя промышленных материалов. Лениздат. 1951.
- S. Martello, P. Toth. Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc. NY, USA. 1990.
- O. Marcotte. The cutting stock problem and integer rounding // Mathematical Programming. 1985. 33: 82−92.
- O. Marcotte. An instance of the cutting stock problem for which the rounding property does not hold // Operations Research Letters. 1986. 4/5: 239−243.
- J. Rietz, G. Scheithauer. Tighter bounds for the gap and non-irup constructions in the one-dimensional cutting stock problem // Optimization. 2002. 51.6: 927−963.
- G. Scheithauer, J. Terno. The modified integer round-up property of theone-dimensional cutting stock problem // European Journal of Operationalt,
- Research. 1995. 84: 562−571.
- F. Vanderbeck. On dantzig-wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm // Operations Research. 2000. 48: 111−128. •
- P. Vance. Branch-and-price algorithms for the one-dimensional cutting stock problem // Computational Optimization and Applications. 1998. 9(3): 212— 228.
- J.M. Valerio de Carvalho. Exact solution of bin-packing problems using column generation and branch-and-bound // Annals of Operational Research. 1999. 86: 629−659.
- J.F. Shapiro. Dynamic programming algorithms for the integer programming // Operations Research. 1968. 16(1): 103−121.
- R.K. Ahuja, T.L. -Magnanti, J.B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall. 1993.
- G. Wascher, T. Gau. Heuristics for the integer one-dimensional cutting stock problem: a computational study // OR Spektrum. 1996. 18: 131−144.
- F. Vanderbeck, L. Wolsey. An exact algorithm for ip column generation /¦/ Operations Research Letters. 1996. 19(4): 151−159.
- C. Barnhart, E.L. Johnson, G.L. Nemhauser, M.W. Savelsbergh, P.H. Vance. Branch-and-price: Column generation for solving huge integer programs // Operations Research. 1996. 46: 316−329.
- Z. Degraeve, L. Schrage. Optimal integer solution to industrial cutting stock problems // INFORMS Journal on Computing. 1999. 11: 406−419.
- F. Vanderbeck. Computational study of a column generation algorithm for binpacking and cutting stock problems // Mathematical Programming. 1999. 86: 565−594.
- И.В. Романовский, Н. П. Христова. Решение дискретных минимаксных задач методом дихотомии // Журнал Вычислительной Матиматики и Математической Физики. 1973. 13(5): 1200−1209.
- С.В. Карцев. Об одном классе дискретных минимаксных задач // Ки-бирнетика. 1979. 5: 139−141.
- И.В. Романовский. Алгоритмы решения экстремальных задач. М.: Наука. 1977.
- A. Scholl, R. Klein, G. Juergens. Bison: A fast hybrid procedure for exactly solving the one-dimensional bin-packing problem // Computers and Operational Research. 1997. 24(7): 627−645.
- D. Simchi-Levi. New worst case results for the bin-packing problem // Naval Research Logistics. 1994. 41: 579−585.
- Э.Х. Гимади, В. В. Залюбовский. Задача упаковки в контейнеры: асимптотически точный подход // Известия высших учебных заведений. Математика. 1997. 12: 25−33.
- Э.А. Мухачева, А. Ф. Валеева. Метод динамического перебора в задаче двухмерной упаковки // Информационные технологии. 2000. 5: 30−37.
- J.M. Valerio de Carvalho. Using extra dual cuts to accelerate column generation // INFORMS Journal on Computing. 2005. 17(2): 175−182.
- E.A. Mukhachevaj V.A. Zalgaller. Linear programming cutting problems /./1.ternational Journal of Software Engineering and Knowledge Engineering. 1993, 3: 463−476.
- E. Aarts, J. Lenstra. Local search in combinatorial optimization. John Wiley & Sons, Inc. NY, USA. 1997.
- Ю.А. Кочетов. Вероятностные методы локального поиска для задач дискретной оптимизации // Дискретная математика и её приложения: Сборник лекций молодежных и научных школ по дискретной математике и её приложениям. 2000. pages 87−117.
- Е.Е. Bischoff, M.D. Marriott. A comparative evaluation of heuristics for container loading // European Journal of Operational Research. 1990. 44(2): 267−276.
- Батищев Д.Ю. Генетические алгоритмы решения экстремальных задач: Учебное пособие. Воронеж: Воронежский гос. техн. ун-т. 1995.
- Е. Falkenauer. A hybrid grouping genetic algorithm for bin packing // Journal of Heuristics. 1998. 33(1): 5−30.
- F. Glover. Tabu search and adaptive memory programming advances, application and challenges // Interfaces in Computer Science and Operations Research. 1996. pages 1−75.
- Yu. Kochetov, A. Usmanova. Probabilistic tabu search with exponential neighborhood for the bin packing problem. In Proceedings MIC'2001. pages 619−624. 2001. .
- F. Loris. An application of simulated annealing to the cutting stock problem // European Journal of Operational Research. 1999. 144(3): 542−556.
- H. Foerster, G. Wascher. Simulated annealing for order spread minimization in sequencing cutting patterns // European Journal of Operational Research. 1998. 110(2): 272−281.
- П.А. Борисовский. Исследование эволюционных алгоритмов решения некоторых задач дискретной оптимизации. PhD thesis. Омский филиал Института математики им. С. JI. Соболева СО РАН, Омск. 2005.
- А.С. Филиппова. Моделирование эволюционных алгоритмов решения задач прямоугольной упаковки на базе технологий блочных структур / / Информационные технологии. 2006. 6: Приложение (32 страницы).
- П.А. Борисовский, А. В. Еремеев. О сравнении некоторых эволюционных алгоритмов // Автоматика и телемеханика. 2004. 3: 3−9.
- JI.B. Канторович, В. А. Залгаллер. Рациональный раскрой промышленных материалов. Новосибирск: Наука. 1971.
- Р. С. Gilmore, R. E. Gomory. Multistage cutting stock problem of two and more dimensions // Operations Research. 1965. 13(1): 94−120.
- J.E. Beasley. An exact two-dimensional non-guillotine cutting tree search procedure // Operations Research. 1985. 33(1): 49−64.
- J.E. Beasley. Bounds for two-dimensional cutting // Journal of the Operational Research Society.' 1985. 36(1): 71−74.
- M. Padberg. Packing small boxes into a big box // Mathematical Methods of Operations Research. 2000. 52(1): 1−21.
- J. Terno, R. Lindemann, G. Scheithauer. Zuschnittprobleme und ihre praktische Losung. Verlag Harry Deutsch, Thun und Frankfurt/Main- Fachbuchverlag, Leipzig. 1987.
- Ю.Г. Стоян, С. В. Яковлев. Математические модели и оптимизационныечметоды геометрического проектирования. Киев: Наукова думка. 1986.
- Yu. Stoyan, М. Novozhilova. Non-guillotine placement of rectangles into a strip of given width // Pesquisa Operational. 1999. 19(2): 189−211.
- Yu. Stoyan, A. Pankratov. Regular packing of congruent polygons on the rectangular sheet // European Journal of Operational Research. 1999. 113: 653−675.
- А.И. Липовецкий. К оптимизации свободного размещения прямоугольников // Автоматизация проектирования в машиностроении. 1985. pages 80−87.
- В.В. Бухвалова. • Задача прямоугольного раскроя: метод зон и другие алгоритмы. С.Пб.: Государственный университет. 2001.
- М. Kenmochia, Т. Imamichia, К. Nonobeb, М. Yagiurac, Н. Nagamochia. Exact algorithms for the two-dimensional strip packing problem with andwithout rotations // European Journal of Operational Research. 2009. 198(1): 73−83.
- S. Martello, D. Vigo. Exact solution of the two-dimensional finite bin packing problem // Management Science. 1998. 44: 388−399.
- G. Wascher, P. Schwerin. A new lower bound for the bin-packing problem and its integration to MTP // Pesquisa Operational. 1999. 19(2): 111−131.
- M.A. Boschetti. The two-dimensional finite bin packing problem //A Quarterly Journal of Operations Research. 2003. 1(1): 27−42.
- Э.Х. Гимади, В. В. Залюбовский, И. П. Шарыгин. Задача упаковки в полосу: асимптотически точный подход // Известия высших учебных заведений. Математика. 1997. 12(427): 34−44.
- D. Liu, Н. Teng. An improved bl-algorithm for genetic algorithm of the orthogonal packing of rectangles // European Journal of Operational Research. 1999. 112(2): 413−420. •
- A. Bortfeld, H. Gehring. Applying tabu search to container loading problem // Operations Research Proceedings. 1998. pages 533−538.
- Э.А. Мухачева, А. С. Мухачева, A.B. Чиглинцев, M.A. Смагин. Задачи двухмерной упаковки: развитие генетических алгоритмов на базе смешанных процедур локального поиска оптимального решения // Информационные Технологии. 2001. Приложение № 9.
- Э.А. Мухачева, А. С. Мухачева, Д. В. Чиглинцев. Генетический алгоритм блочной структуры в задачах двухмерной упаковки // Информационные технологии. 1999- 11: 13−18.
- И.П. Норснков. Эвристики и их комбинации в генетических методах дискретной оптимизации // Информационные технологии. 1999. 1: 2−7.
- S. Imahori, M. Yagiura, T. Ibaraki. Local search algorithms for the rectangle packing problem with general spatial costs // Mathematical Programming. 2003. pages 543−569.
- P. Chen, Y. Chen, M. Goel, F. Mang. Approximation of two-dimensional rectangle packing. Technical report. 1999.
- E. Hopper, B. Turton. A review of the application of meta-heuristic algorithms to 2D strip packing problems // Artificial Intelligence Review. 2001. 16(4): 257−300.
- D. Pisinger. • Heuristics for the container loading problem // European Journal of Operational Research. 2002. 141(2): 382−392.
- Ю. Кочетов, H. Младенович, П. Хансен. Локальный поиск с чередующимися окрестностями // Дискретный анализ и исследование операций. 2003. 10(1): 11−43.
- М. Monachi. Algorithms for packing and scheduling problems. PhD thesis. University of Bologna. 2001. •
- S. Martello, M. Monachi, D. Vigo. An exact approach to the strip-packing problem // INFORMS Journal on Computing. 2003. 15(3): 310−319.
- S. Fekete, J. van der Veen. Two-dimensional strip packing in reconfigurable computing. In 2nd ESICUP (Euro Special Interest Group on Cutting and Packing) Meeting-, Southampton. 2005.
- Э.А. Мухачева, А. С. Мухачева. Задача прямоугольной упаковки: методы локального поиска оптимума на базе блочных структур // Автоматика и телемеханика. 2004. 2: 10−15.
- F. Clautiaux, A. Jouglet, J. Carlier, A. Moukrim. A new constraint programming approach for the orthogonal packing problem // Computers and Operations Research. 2008. 35(3): 944−959.
- S. Fekete, J. Schepers. New classes of lower bounds for bin packing problems. In Mathematical Programming, pages 257−270. Springer. 1998. •
- S.P. Fekete, J. Schepers. A general framework for bounds for higher-dimensional orthogonal packing problems // Mathematical Methods of Operations Research. 2004. 60(2): 311−329.
- B.M. Картак, М. А. Месягутов, Э. А. Мухачева, А. С. Филиппова. Локальный поиск ортогональных упаковок с использованием нижних границ // Автоматика и телемеханика. 2009. 6: 167−180.
- В.П. Житников, А. С. Филиппова. Задача прямоугольной упаковки в полубесконечную полосу: поиск решения в окрестности локальной нижней границы // Информационные технологии. 2007. 5: 55−62.
- S. Hartmann. Project Scheduling under limited resources. Models, methods and applications. Springer, Berlin. 1999.
- M. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. М.: Мир. 1982.
- G. Belov, G. Scheithauer. A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths // European Journal of Operational Research. 2002. 141(2): 274−294.
- G. Belov, G. Scheithauer, E.A. Mukhacheva. One-dimensional heuristics adapted for two-dimensional rectangular strip packing // The Journal of the Operational Research Society. 2008. 59(6): 823−832.
- Э.А. Мухачева, Д. А. Назаров. Конструирование прямоугольных упаковок: алгоритм перестройки на базе блочных структур // Автоматика и телемеханика. 2008. 2: 97−113.
- Н. Murata, К. Fujiyoshi, S. Nakatake, Y. Kajitani. VLSI module placement based on rectangle-packing by the sequence-pair // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 1996. 15(12): 1518−1524.
- K.S. Booth, G.S. Lueker. Testing for the consecutive ones property, interval graphs, and planarity using p’q-tree algorithms // Journal of Computational Systems Science. 1976. 13: 335−379.
- B.B. Залюбовский. Точные и асимптотически точные алгоритмы для задач упаковки и календарного планирования. PhD thesis. Институт математики им. С. JI. Соболева СО РАН, Новосибирск. 2006.
- A. Bortfeld. A genetic algorithm for the two-dimensional strip packing problem with rectangular prices // European Journal of Operational Reseach. 2006. 172(3): 814−837.
- J.O. Berkey, P.Y. Wang. Two dimensional finite bin packing algorithms // Journal of Operational Research Society. 1987. 38: 423−429.
- R. Baldacci, M. Boschetti. • A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem // European Journal of Operational Research. 2007. 183: 1136−1149.
- S. Fekete, J. Sthepers. A general framework for bounds for higher-dimensional orthogonal packing problems // Mathematical Methods of Operations Research. 2004. 60:'311−329.
- A. Lodi, М. Martello, D. Vigo. Recent advances on two-dimensional bin packing problems // Discrete Applied Mathematics. 2002. 123(1−3): 379−396.
- Э.А. Мухачева, Д. А. Назаров, A.C. Филиппова. Проектирование прямоугольных упаковок с использованием декодеров блочной структуры // Автоматика и телемеханика. 2006. 6: 161−173.
- В.В. Залюбовский. О представлении перестановками допустимых решений одномерной задачи упаковки в контейнеры // Тр. XIII Байкальской международной шк.-семинара. Иркутск. 2005. 1: 461−466.