Проектирование гильотинного раскроя листового и рулонного материала с использованием послойных алгоритмов
Диссертация
Диссертация состоит из введения, 4 глав, выводов, списка литературы, и приложений, включающих табличные результаты численных экспериментов, функциональную и информационную модели, акты внедрения результатов работы. Работа изложена на 139 страницах машинописного текста, кроме того, содержит 25 рисунков и 24 таблиц. Библиографический список включает 98 наименования и занимает 10 страниц… Читать ещё >
Содержание
- 1. Обзор моделей и методов решения задач раскроя
- 1. 1. Автоматизация проектирования и технологической подготовки производства
- 1. 2. Классификация задач раскроя
- 1. 3. Постановка задачи гильотинного раскроя
- 1. 4. Математическая модель задачи гильотинного раскроя
- 1. 5. Обзор методов решения задачи раскроя
- 1. 5. 1. Точные методы решения задач раскроя
- 1. 5. 2. Приближенные и эвристические методы
- 1. 5. 3. Вероятностные методы локального поиска оптимума
- 1. 5. 4. Применение методов решения задач раскроя-упаковки в автоматизированных системах раскроя-упаковки
- 1. 6. Выводы
- 2. Эвристические методы решения задачи гильотинного раскроя
- 2. 1. Уровневые алгоритмы
- 2. 2. Послойная технология расчета гильотинного раскроя
- 2. 3. Использование послойной технологии для разработки новых детерминированных методов решения задачи гильотинного раскроя
- 2. 3. 1. Рекурсивный метод
- 2. 3. 2. Метод поиска пустых корзин
- 2. 4. Выводы
- 3. Автоматизированная система двумерного прямоугольного раскроя CETAMI-CUT
- 3. 1. Современное состояние раскройно-заготовительного производства
- 3. 2. Структура САПР раскроя-упаковки
- 3. 3. Применение разработанного программного обеспечения в САПР раскроя-упаковки.Error! Bookmark not defined
- 3. 4. Программа-оболочка CETAMI-CUT, ее взаимодействие с расчетными модулями
- 3. 5. Детерминированные эвристические алгоритмы решения задачи гильотинного раскроя, реализованные в системе CETAMI-CUT
- 3. 5. 1. Рекурсивный алгоритм в рамках системы CETAMI-CUT
- 3. 5. 2. Алгоритм поиска пустых корзин в рамках системы CETAMI-CUT
- 3. 6. Автоматизированный выбор метода расчета раскроя
- 3. 7. Выводы
- 4. Численные эксперименты
- 4. 1. Независимое использование рекурсивного метода и метода поиска пустых корзин
- 4. 1. 1. Определение значений параметров рекурсивного метода для его эффективной работы
- 4. 1. 2. Определение значений параметров метода поиска пустых корзин для его эффективной работы
- 4. 1. 3. Сравнение разработанных эвристик с послойным алгоритмом и между собой
- 4. 2. Использование рекурсивного метода в составе метаэвристик
- 4. 3. Использование метода поиска пустых корзин в составе метаэвристик
- 4. 4. Использование процедуры автоматизированного выбора метода решения задачи
- 4. 5. Выводы
- 4. 1. Независимое использование рекурсивного метода и метода поиска пустых корзин
Список литературы
- Аккуратов Г. В., Березнев В. А., Брежнева О. А. О методе решения уравнения с булевыми переменными // Принятие решений в условиях неопределенности. Межвузовский научный сборник. Уфа: УАИ. 1990. С. 145 154.
- Бабаев Ф.В. Оптимизация раскроя материалов: Обзор. М.: НИИМАШ, 1978.- С. 72.
- Бабаев Ф.В. Оптимальный раскрой материалов с помощью ЭВМ. -М.: Машиностроение. 1982.
- Бабкова Е.В. Задача оценки сложности раскроя в условиях автоматизированного управления производством // Принятие решений в условиях неопределенности: Межвуз. науч. сб. -Уфа: УГАТУ, 2000. -С. 136−141.
- Бабкова Е.В. Модель сменной загрузки раскройного оборудования // Принятие решений в условиях неопределенности: Межвуз. науч. сб. Уфа: УГАТУ, 2002. — С.184−190.
- Булавский В.А., Яковлева М. А. О решении задач оптимального раскроя линейных материалов на ЭВМ // Математические методы в технико-экономических расчетах: Материалы научного совещания, т. IV. М.: АН СССР. 1961. С. 83−87.
- Бухвалова В.В. Задача прямоугольного раскроя: метод зон и другие алгоритмы // С. Петербург: Государственный университет. 2001.
- Верхотуров М.А. Задача нерегулярного раскроя плоских геометрических объектов: моделирование и расчет рационального раскроя // Информационные технологии. 2000. № 5. С.37−42.
- Гамберг В.Я., Липовецкий А. И., Петунин А. А. Автоматизация проектирования раскройных карт в условиях индивидуального производства // Кузнечно-штамповочное производство, 1982.-N3 С.26−27.
- Гери М., Джонсон Д. Вычислительные машины и трудноразрешимые задачи // М. Мир. 416с.
- Гимади Э.Х., Залюбовский В. В. Задача упаковки в контейнеры: асимптотически точный подход // Известия вузов. Математика. 1997. № 12. С. 25−33. Работа поддержана РФФИ: проекты 96−01−1 591 и 97−01−890.
- Гончаров Е.Н., Кочетов Ю. А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения .// Дискретный анализ и исследование операций. 1999. Серия 2. 6. № 1. С. 12−32. Работа поддержана РФФИ: проекты 99−01−601, 98−07−90 259.
- Горанский Г. К., Бендерева Э. И. Технологическое проектирование в комплексных автоматизированных системах подготовки производства. -М.Машиностроение, 1981.-455 с.
- Долгопольский Б.С., Бритарев К. Ф. Арцишевский Ю.Ю. Система автоматизированного проектирования на ЭВМ процессов холодной листовой штамповки. -М.: Кузнечно-штамповочное производство. 1979. № 6. С. 13−14.
- Жукова Т.Ю. Применение метода «Моделирование отжига» для решения задачи раскроя // Уфа: Принятие решений в условиях неопределенности. 2003. С. 230−235. Работа поддержана РФФИ, проект 01−100 510.
- Канторович Л.В., Залгаллер В. А. Рациональный раскрой промышленных материалов // Новосибирск: Наука СО. 1971. 299с.
- Канторович Л.В., Заллгаллер В. А. Расчет рационального раскроя материалов// Лениздат. 1951.
- Кацев С.В. Об одном классе дискретных минимаксных задач: Кибернетика, 1979, № 5, с. 139−141.
- Коробцева Н.А. САПР одежды: исторический экскурс и обзор существующих систем // Текстильная промышленность. 2003. № 5. С.61−62. № 6. С. 63−65.
- Кочетов Ю., Усманова А. Вероятностный поиск с запретами для задачи упаковки в контейнеры // Иркутск: XII Байкальская международная конференция. 2001. С.22−27. Работа поддержана РФФИ: проект 01−01−510.
- Липовецкий А.И. К оптимизации свободного размещения прямоугольников // Автоматизация проектирования в машиностроении. Минск. 1985. С. 80−87.
- Макеев Б.А., Батозский В. И. и др. Автоматизация раскроя тонколистового проката. -М.: Кузнечно-штамповочное производство. 1978. № 6. С. 30−33.
- Мартынов В.В. Информационная система раскроя плоских геометрических объектов сложной формы: основные проблемы и подходы к их решению // Вестник УГАТУ. -Уфа, Изд. УГАТУ, 2001. С. 105−113.
- Мухачева А.С., Куреленков С. Х., Смагин М. А., Ширгазин P.P. Методы локального поиска оптимума прямоугольной упаковки с использованием двойственной схемы // Информационные технологии. 2002. № 10. С. 26−31. Работа поддержана РФФИ, проект 01−01−510.
- Мухачева Э. А. Валеева А.Ф. Метод динамического перебора в задаче двумерной упаковки // Информационные технологии. 2000. № 5. С. 30−37. Работа поддержана РФФИ: проект 99−01−947.
- Мухачева Э.А. Методы условной оптимизации в задаче рационального раскроя листового проката // Оптимизация: Сб. науч. трудов СО АН СССР. 1978. Вып. 22. С. 83−93.
- Мухачева Э.А. Рациональный раскрой промышленных материалов. Применение в АСУ. -М. Машиностроение. 1984. 176с.
- Мухачева Э.А. Рациональный раскрой прямоугольных листов на прямоугольные заготовки // Оптимальное планирование: Сб. научных трудов СО АН СССР. 1966. Вып. 6. С. 43−115.
- Мухачева Э.А., Верхотуров М. А., Мартынов В. В. Модели и методы расчета раскроя-упаковки геометрических объектов // Уфа. УГАТУ. 1998. 216 с.
- Мухачева Э.А., Ермаченко А. И., Сиразетдинов Т. М., Усманова А. Р. Метод поиска минимума с запретами в задачах двумерного гильотинного раскроя // Информационные технологии. 2001. № 6. С. 25−31. Работа поддержана РФФИ: проект 99−01−947, 01−01−510.
- Мухачева Э.А., Картак В. М. Модифицированный метод ветвей и границ: алгоритм и численный эксперимент для задачи одномерного раскроя // Информационные технологии. 2000. № 9. С. 15−22. Работа поддержана РФФИ: проект 99−01−947.
- Мухачева Э.А., Мухачева А. С. Метод перестройки для решения задачи прямоугольной упаковки // Информационные технологии. 2000 № 4. С. 30−36. Работа поддержана РФФИ, проект 99−01−947.
- Мухачева Э.А., Мухачева А. С., Белов Г. Н. Метод последовательного уточнения оценок: алгоритм и численный эксперимент для задачи одномерного раскроя Информационные технологии. 2000 № 2. С. 11−17. Работа поддержана РФФИ: проект 99−01−947.
- Мухачева Э.А., Рубинштейн Г. Ш. Математическое программирование // Новосибирск. Наука СО. 1987. 272 с.
- Норенков И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации. // Информационные технологии. 1999. № 1. С. 2−7.
- Петунин А.А. Интегрированная САПР «Сириус» для автоматизации раскройно-заготовительного производства // С. Петербург: ОПТИМ-2001. С.123−126.
- Романовский И.В. Алгоритмы решения экстремальных задач // М.: Наука. 1977.
- Романовский И.В. Решение задачи гильотинного раскроя методом переработки списка состояний // Кибернетика. 1969. № 1. С. 102−104.
- Романовский И.В., Христова Н. П. Решение дискретных минимаксных задач методом дихотомии // ЖВМ и МФ. 1973. 13(5). С. 12 001 209.
- Усманова А. Вероятностные жадные эвристики для задачи упаковки в контейнеры // С. Петербург: ОПТИМ-2001. С. 141−146. Работа поддержана РФФИ: проекты 99−01−947, 01−01−510.
- Фроловский В. Моделирование и оценка качества проектных решений в системах сквозного проектирования корпусных изделий из листового материала//Информационные технологии. 2000. № 5. С. 18−25.
- Фроловский В.Д. Целочисленная аппроксимация и оптимальное группирование геометрических объектов в задачах размещения // Научный вестник НГТУ. № 1(8). 2000. С. 37−46.
- Шпур Г., Краузе Ф.-Л. Автоматизированное проектирование в машиностроении. -М.Машиностроение, 1988.-648с.
- Aurts Е., Lenstra J., edit. Local Search in Combinatorial Optimization/ // John Wiley&Sons. 1996.
- Adamovicn A., Albano A. Nesting two-dimensional shapes in rectangular Modules // Comput. Aeded Design. 1976. 8(1). P.27−33.
- Baesley J.E. http://mscmga.ms.ic.ac.-uk/info.html.
- Bischoff E., Wascher G., edit. Special issue: Cutting and Packing // European Journal of Operational Research. 1995. 84.
- Blazewicz J., Hawryluk P., Walkowiak R. Using a tabu search approach for solving the two-dimensional irregular cutting problem // Annals of OR. 1993. 41(4). P.313−325.
- Coffman E., Garey M., Jchonson D. Approximation algorithms for bin-packing-an updated survey // Algorithm Design for Computer System Design (Ausiello G., Lucertini M., Serafini P. eds) Berlin etal. 1984.
- Dorigo M., Di Caro G., Gambardella L.M. Ant Algorithms for Discrete Optimization // Artificial Life. 1999. Vol.5. No.3. pp. 137−172.
- Dyckhoff H., Scheithauer G., Terno J. Cutting and Packing // Annotated Bibliographies in Combinatorial Optimization, edited by M. Dell'Amico, F. Maffioli and S.Martello. John Wiley&Sons. 1997. P.393−412.
- Dykhoff H. A typology of cutting and packing problems // Evropean Journal of Operational research. 1990. Vol. 44. P. 145−159.
- Dykhoff H., Wascher G., edit. Special issue: Cutting and Packing // European Journal of Operational Research. 1990. 44(2).
- Folkenauer E. Tapping the full power of genetic algorithm through suitable representation and local optimization: Application to bin packing // Evolutionary Algorithms in Management Applications. Berlin. 1995. P. 167−182.
- Folkenauer E. A hybrid Grouping Genetic Algorithm for Bin Packing // Journal of Heuristics. 1998. 2(1). P. 5−30.
- Forster H., Wascher G. (1997) Simulated annealing for order spread minimization sequencing cutting patterns // European Journal of Operational Research. 1998. 110. P. 272−281.
- Garey M. R, Johnson D.S. Computers and Intractability: A guide to the Theory of NP-Completeness // San-Francisco, Freemau. 1979.
- Gehring H., Bortfeld A. A Genetic Algorithm for Solving the Container Loading Problem // International transactions in operational research. 1997, V.4, № 5/6. P.401−418.
- Gilmore P., Gomory R. Multistage cutting stock problem of two and more dimensions//OperatRes. 1965. 13(1). P.94−120.
- Gilmore P., Gomory R. The theory and computation of knapsack functions. // Oper. Res. 1966. V.14. P. 1045−1075.
- Gilmore P.C. and Gomory R.E. A Linear Programming Approach to the Cutting-stock Problem, Operations Research 9(1961), pp. 849−859.
- Glover F. Tabu search and adaptive memory programming advances, applications and challenges // Interfaces in Computer Science and Operations Research. 1996. P. 1−75.
- Hopper E., Turton B. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem. // EJOR 128. 2001. P. 34−57.
- Jhonson D.S., Demers A., Ullman J.D., Garey M.R., Graham R.L. Worst-case performance bounds for simple one-dimensional packing algorithms // SIAM J. Comput. V. 3. N4. 1974. P.299−325.
- Kochetov Yu., Usmanova A. Probabilistic Tabu Search with Exponential Neighborhood for Bin Packing Problem // Proceedings MIC'2001, Porto, 2001. P. 619−624. Работа поддержана РФФИ: проект 01−01−510.
- Lirov Y., edit. Special issue: Geometric Resource Allocation // Mathematical and Computer Modelling. 1995. 16(1).
- Liu D., Teng H. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles. // European Journal of Operation Research. 1999. 112. P. 413−420.
- Lodi A., Martello S., Vigo D. Recent advances on two-dimensional bin packing problems. //Discrete Applied Mathematics 123. 2002. P. 379 -396.
- Loris Faina. An application of simulated annealing to the cutting stock problem // European Journal of Operational Research. 1999. 114. P. 532−556.
- Martello S., edit. Special issue: Knapsack, Packing and Cutting, Part I: One Dimensional Knapsack Problem. // INFOR. 1994. 32(3).
- Martello S., edit. Special issue: Knapsack, Packing and Cutting, Part II: Multidimensional Knapsack and Cutting Stock Problems // INFOR. 1994. 32(4).
- Martello S., Toth P. Knapsack problems: Algorithms and Computer Implementations. // YOHN WILEY&SONS. Chichester. 1990.
- Martynov V. Geometrical objects regular placement onto a stock sheet or strip // Pesquisa Operacional, Vol. 19, No.2. SP — BRAZIL, Instituto Nacional de Pesquisas Espaciais, dezembro de 1999. P.211−222.
- Morabito M. Arenales M. Staged and constrained two-dimensional guillotine cutting problems: an and/or-graph approach. // European Journal of Operational Research. 1996. 94. P.548−560.
- Morabito R., Arenales M. An AND/OR graph approach to the container loading problem // International Transactions in Operational Research 1 (1994) 5973.
- Mukhacheva E., edit. Special issue: Decasion Making under Conditions of Uncertainty (Cutting-Packing Problems)/ The International Scientific Collection. 1997. Ufa. Russia.
- Mukhacheva Е.А., Zalgaller V.A. Linear Programming Cutting Problems // International Journal of Software Engineering and Knowledge Engineering. 1993. V. 3. N4. P. 463−476.
- Murata H., Fujiyoshi K., Nakatane S. and Kajitani Y. Rectangle-Packing-Based Module Placement // Proc. IEEE/ACM International Conf. on Computer-Aided Design. 1995. P.472−479.
- Scheithauer G. and Terno J. About the gap between the optimal values of the integer and continuous relaxation one-dimensional cutting stock problem. Oper. Res. Proc. 1991, Springer-Verlag, Berlin Heidelberg, 439−444.
- Scheithauer G., Terno Y. Muller A., Belov G. Solveng one-dimensional cutting stock problems exactly with a cutting plane algorithm. // Journal of the Operational Research Society. 2001. 52. H. 1390−1401.
- Schwerin P., Wascher G. The Bin-Packing Problem: a Problem Generator and Some Numerical Experiments with FFD Packing and MTP // International Transactions in Operational Research. 1997. 4. P.337−389.
- Sergeyeva O.Y., Scheithauer G. and Terno J. The value correction method for packing of irregular shapes // Decision making under conditions of uncertainty (cutting-packing problems). The International Scientific Collection. Ufa 1997. P. 261−270.
- Stutzle Т., Hoos H.H. MAX-MIN Ant System // Preprint submitted to Elsiever Science, 1999.
- Terno J., Lindeman R., Scheithauer G. Zuschnitprobleme und ihre praktische Losung. Leipzig. 1987.
- Valeyeva A.F., Agliullin M.N. Ant Colony Algorithm for the 2-D Bin-Packing Problem: Numerical Study // Proceedings of the 5th International Workshop on Computer Science and Information Technologies, 2003. P. 110−114.
- Verhoturov M.A., Sergeyeva O.Y. The sequential value correction method for the two-dimensional irregular cutting stock problem // Pesquisa Operacional. 2000. Y. 20. N2. P. 233−247. Работа поддержана РФФИ, проект 99−01−947.
- Wang P., Yalenzeva L. Data set generation for rectangular placement problems // European Journal of Operational Research. 2001. 134(2). P.378−391.
- Wang P., Wascher G., edit, {it Special issue: Cutting Packing Problems} Europen Journal of Operational research. 141 (2002).
- Yanasse H., edit. Special issue: Cutting and Packing Problems// Pesquisa Operacional. 1999. 19(2).