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

  • Гареев, Ильгиз Рифгатович
  • кандидат технических науккандидат технических наук
  • 2002, Уфа
  • Специальность ВАК РФ05.13.12
  • Количество страниц 139
Гареев, Ильгиз Рифгатович. Методы рандомизированного перебора для расчета прямолинейного раскроя-упаковки в системах автоматизированного проектирования: дис. кандидат технических наук: 05.13.12 - Системы автоматизации проектирования (по отраслям). Уфа. 2002. 139 с.

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

ГЛАВА 1. ЗАДАЧИ РАСКРОЯ-УПАКОВКИ.

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

1.2 Основные этапы развития задач раскроя-упаковки.

1.3 Классификация задач раскроя-упаковки.

1.4 Методы решения задачи одномерной упаковки.

1.5 Методы решения задачи двумерной упаковки.

Рекомендованный список диссертаций по специальности «Системы автоматизации проектирования (по отраслям)», 05.13.12 шифр ВАК

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

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

Актуальность темы исследования. Определяющими факторами успеха в промышленном производстве являются уменьшение времени выхода продукции на рынок, снижение стоимости и повышение качества. Темпы морального старения промышленных изделий таковы, что поставленные на конвейер новые образцы часто уже не соответствуют современным требованиям. Только значительное сокращение цикла проектирования и подготовки производства, подразумевающее внедрение систем автоматизации проектирования (САПР) и автоматизированных систем технологической подготовки производства (АСТПП), может способствовать созданию конкурентоспособной продукции и своевременному выходу ее на рынок.

Важной составной частью технологической подготовки производства являются задачи раскроя-упаковки (Р-У). Задачи Р-У представляют собой важный раздел задач дискретной оптимизации и исследования операций.

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

Цель работы. Разработка методов рандомизированного перебора для проектирования плотной упаковки прямолинейных деталей в заданных областях размещения; создание на этой базе программного обеспечения, входящего в состав автоматизированного рабочего места технолога раскройно-заготовительного производства.

Для ее достижения были поставлены следующие задачи:

1. Исследовать метод динамического перебора для задачи прямоугольной упаковки; разработать метод на базе динамического перебора с использованием рандомизации для различных задач прямолинейной упаковки.

2. Исследовать трудные задачи одномерной упаковки контейнеров одинаковой емкости; для решения этих задач разработать метод на основе перебора вариантов упаковки с использованием рандомизированного обмена предметов между контейнерами.

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

4. Исследовать эффективность предложенных методов на базе численного эксперимента с использованием разработанного программного обеспечения.

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

На защиту выносятся:

1. Результаты исследования метода динамического перебора для прямоугольной упаковки; рандомизированный метод динамического перебора для следующих задач прямолинейной упаковки: одномерной упаковки контейнеров одинаковой и различной емкости, двумерной упаковки полубесконечной полосы и по листам.

2. Метод на основе перебора вариантов упаковки с использованием рандомизированного обмена предметов между контейнерами.

3. Программное обеспечение на базе предложенных методов в составе автоматизированного рабочего места технолога раскройно-заготовительного производства.

4. Результаты численного эксперимента на базе разработанного программного обеспечения.

Научная новизна работы:

• исследован метод динамического перебора для прямоугольной упаковки; его рандомизированный вариант впервые применен для задач прямолинейной упаковки, что позволило существенно повысить коэффициент раскроя;

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

Практическая значимость работы:

• разработанное программное обеспечение, включенное в состав автоматизированного рабочего места технолога раскройно-заготовительного производства, позволило повысить коэффициент использования материала и сократить время проектирования;

• метод на базе рандомизированного динамического перебора является универсальным для задач прямолинейной упаковки, что позволило применить его для расчета плотного размещения ящиков в трехмерных контейнерах различной емкости с учетом грузоподъемности.

Работа выполнялась на основании грантов Российского Фонда Фундаментальных Исследований (РФФИ), Москва, проекты 99-01-000937 и 0101-000510; технического задания бюро нормирования материала ГУП УАП «Гидравлика», Уфа; научно-технического сотрудничества с ОАО «УралХимМаш», Екатеринбург.

Апробация работы. Результаты работы и отдельные ее разделы докладывались и обсуждались на

Конференции «Математическое программирование и приложения» (1999, Екатеринбург, УрО РАН);

Международной молодежной научной конференции «XXV Гагаринские чтения» (1999, Москва);

Республиканской научно-технической конференции «Интеллектуальное управление в сложных системах - 99» (1999, Уфа);

Международной научной конференции «Моделирование, вычисления, проектирование в условиях неопределенности - 2000» (2000, Уфа);

Первой всероссийской научно-практической конференции по вопросам решения оптимизационных задач в промышленности «Ресурсосберегающие технологии: математическое обеспечение оптимизационных задач в системах автоматизированного проектирования» (2001, С-Петербург);

3-й международной научной конференции CSIT2001 (2001, Уфа);

Российской научной конференции «Дискретный анализ и исследование операций» (2001, 2002, Новосибирск);

The Sixteenth Conference of the International Federation in Operational Research (2002, Edinburg, UK); семинарах кафедры вычислительной математики и кибернетики Уфимского государственного авиационного технического университета.

Публикации. По теме диссертации опубликовано 16 работ.

Структура работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы.

Похожие диссертационные работы по специальности «Системы автоматизации проектирования (по отраслям)», 05.13.12 шифр ВАК

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

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

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

2. Разработан метод перебора с усечением ST, который позволил получать рациональные решения задачи одномерной упаковки контейнеров одинаковой емкости с минимальными затратами времени.

3. Разработано программное обеспечение на базе предложенных методов, позволяющее решать за приемлемое время трудные задачи прямолинейной упаковки; сложность данных задач определяется большой размерностью (до 1000 предметов), наличием безотходного решения и способом генерации; для программной реализации метода DSR предложена структура данных для множества кортежей, позволяющая уменьшить использование оперативной памяти в несколько раз.

4. Проведены численные эксперименты для анализа методов, которые позволили выбрать значения параметров для различных классов задач; были сравнены разработанные методы с некоторыми известными алгоритмами для задач упаковки с использованием известных методик тестирования и трудных задач из интернет-библиотеки; в результате показано, что метод ST решает оптимально практически все трудные задачи одномерной упаковки и превосходит некоторые другие методы, в том числе и точные, по времени вычислений, а метод DSR превосходит некоторые другие алгоритмы для двумерной упаковки на наборах «средние предметы» и «малые предметы» (коэффициент раскроя от 96.04% до 99.40%, от 1 до 4 минут работы); также продемонстрировано, что коэффициент раскроя метода DSR на трудных задачах двумерной упаковки составляет от 96.54% до 100% (от 1.5 до 8 минут работы).

5. Разработанное программное обеспечение включено в состав автоматизированного рабочего места технолога раскройно-заготовительного производства и внедрено на предприятии ГУП УАП «Гидравлика» для решения задачи «Использование отходов производства по цехам»; метод

132

DSR для двумерной упаковки был использован для решения задачи трехмерной упаковки и применен для расчета плотного размещения ящиков в трехмерных контейнерах различной емкости с учетом грузоподъемности на ОАО «УралХимМаш».

ЗАКЛЮЧЕНИЕ

Ускорение выпуска изделий производства, а также необходимость сокращения материальных затрат на изготовление изделий обусловливают жесткие требования к качеству и гибкости производства. Осуществление этих требований стало возможным на основе широкого применения средств вычислительной техники на всех этапах производства. Для промышленного производства системы автоматизированного проектирования и технологической подготовки производства приобретают все большее значение. В связи с большой номенклатурой деталей при производстве заготовок возникают сложности по организации технологического проектирования раскройных заготовительных операций в целом. Поэтому понятны и оправданы усилия специалистов по созданию и внедрению САПР ТП в раскройно-заготовительное производство.

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

Список литературы диссертационного исследования кандидат технических наук Гареев, Ильгиз Рифгатович, 2002 год

1. Шпур Г., Краузе Ф.-J1. Автоматизированное проектирование в машиностроении. - М. Машиностроение, 1988.-648с.

2. Горанский Т.К., Бендерева Э.И. Технологическое проектирование в комплексных автоматизированных системах подготовки производства. -М.Машиностроение, 1981.-455 с.

3. Мухачева Э.А., Белякова Л.Б. Задачи планирования рационального раскроя и их комплексное решение // Принятие решений в условиях неопределенности.-Уфа:УАИ, 1990.- С.99-108.

4. Чебышев П.Л. О кройке одежды. Журн. Успехи матем.наук,1946,1,2.С.27.

5. Федоров Е.С. Симметрия и структура кристаллов. -М.:Изд-во АН СССР, 1949.-411с.

6. Канторович Л.В., Залгаллер В. А. Рациональный раскрой промышленных материалов. Новосибирск: Наука, 1971.-298 с.

7. Модели и методы расчета раскроя упаковки геометрических объектов / Э.А. Мухачева, М.А. Верхотуров, В.В. Мартынов. - Уфа: УГАТУ, 1998. -217с.

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

9. Martello S., Toth P. Knapsack problems: Algorithms and Computer Implementation. // Operation Research. 1990. V32.

10. Coffman E., Garey M.R., Johnson D.S. Approximation algorithms for bin-packing-an updated survey. // Algorithm Design for Computer System Design (Ausiello G., Lusertini M., Serafini P. eds). Berlin etal. 1984.

11. Garey M.R., Johnson D.S. Computers and Intractability: A guide to Theory of NP-Completeness // San-Francisco. Freemau. 1979.

12. Scholl A., Klein R., Juergens C. BISON: A fast hybrid procedure for exactly solving the one-dimensional Bin-Packing Problem. // Computers and Operational Research, 1997. Vol. 24, No 7, p. 627-645.

13. Романовский И.В. Алгоритмы решения экстремальных задач. -М.: Наука, 1977.-3 51с.

14. Мухачева Э.А., Рубинштейн Г.С. Математическое программирование. -Новосибирск: Наука, 1977. -319с.

15. Terno J., Lindeman R., Schaithauer G. Zuschnitprobleme und ihre prakti-sche Losung.- Leiprig, 1987, P.207.

16. Вайнштейн А.Д. Задачи об упаковке прямоугольников в полосу (Обзор). В кн.: Дискретные задачи оптимизации. Управляемые системы, Новосибирск, 1984, №25, с. 17-37.

17. Усманова А. Вероятностные жадные эвристики для задачи упаковки в контейнеры //С.Петербург: ОПТИМ-2001. С.141-146.

18. Кочетов Ю., Усманова А. Вероятностный поиск с запретами для задачи упаковки в контейнеры // XII Байкальская международная конференция. Иркутск. 2001. С. 22-27.

19. Glover F. Tabu search.- Part I. ORSA Journal on Computing, No 1, 1989.-pp.190-206.

20. Liu D., Teng H. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles. EJOR, Vol. 112, 1999.-pp.413-420.

21. Foerster H., Wascher G. Simulated Annealing for order spread minimization in sequencing cutting patterns. EJOR, Vol. 110, 1998.-pp.272-281.

22. Brucker P., Hurink J., Werner F. Improving local search heuristics for some scheduling problems Part I. Discrete Applied Mathematics, Vol.65,1996.-pp.97-122.

23. Мухачева Э.А., Валеева А.Ф., Мухачева A.C. Методы локального поиска в задачах оптимального распределения ресурса: Учебное пособие. -Уфа,: УГАТУ, 2001, с.75.

24. Липовецкий А.И. Алгоритмы негильотинного прямоугольного раскроя //Математическое обеспечение рационального раскроя в САПР: материалы всесоюзной конференции: -Уфа, 1988, -С.72-79.

25. Стоян Ю.Г, Гиль Н.И. Методы и алгоритмы размещения плоских геометрических объектов. -Киев: Наукова думка, 1976. -247с.

26. Липовецкий А.И. Алгоритмы негильотинного прямоугольного раскроя

27. Математическое обеспечение рационального раскроя в САПР: материалы всесоюзной конференции: -Уфа, 1988, -С.72-79.

28. Липовецкий А.И. К оптимизации свободного размещения прямоугольников //Автоматизация проектирования в машиностроении. -Минск: ИТК АН БССР, 1985. -С.80-87.

29. Липовецкий А.И. Свойства прямоугольных укладок и алгоритмы оптимального раскроя: Препринт. -Свердловск: Уро АН СССР, 1988. -50с.

30. Липовецкий А.И. Сокращение перебора при автоматизированном проектировании прямоугольного раскроя //Автоматизация технологической подготовки производства: Межвузовский сборник. -Свердловск: изд.УПИ им.Кирова, 1986. -С.77-86.

31. Аккуратов Г .В, Березнев В.А, Брежнева 0:А. О методе решения уравнения с булевыми переменными //Принятие решений в условиях неопределенности: межвуз. научный сб. -Уфа, 1990. -С. 145-146.

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

33. Батищев Д.И. Генетические алгоритмы решения экстремальных задач. -Воронеж: ВГТУ, 1995.

34. Golberg D. Genetic Algorithms in Search, Optimization, and Machine Learning // Adison-Wesley Publ.,1989.

35. Мухачева Э.А, Мухачева A.C, Чиглинцев A.B. Генетический алгоритм блочной структуры в задачах двумерной упаковки //Информационные технологии, 1999, №11, с. 13-18.

36. Мухачева А.С, Чиглинцев А.В, Смагин М.А, Мухачева Э.А. Задачи двумерной упаковки: развитие генетических алгоритмов на базе смешанныхпроцедур локального поиска оптимального решения // Информационные технологии. Приложение. 2001. №9, с.7-10.

37. Bellman R. Е. Dynamic programming. Princeton: Princeton University Press. 1957. C.342.

38. Мухачева Э.А., Мухачева A.C., Белов Г.Н. Метод последовательного уточнения оценок: алгоритм и численный эксперимент для задачи одномерного раскроя // Информационные технологии. 2000. №2. С. 11-17.

39. А.Ф. Валеева, И.Р.Гареев, В.А.Габитов. Метод динамического перебора для решения задачи одномерной упаковки // Международная научная конференция. Уфа. 2000. С.369-373.

40. Валеева А.Ф., Гареев И.Р. Метод динамического перебора для решения задачи одномерной упаковки: вычислительный эксперимент // Дискретный анализ и исследование операций: Тр. рос. конф. Новосибирск, 2001. С.132.

41. I.R. Gareev, R.R. Shirgasin, M.Yu. Surnachev, S.N. Sobko. Heurisms for One-Dimensional Bin-Packing Problems // Proceedings of the 3rd International Workshop CSIT2001. Ufa. 2001. P.141-150.

42. Гареев И.Р. О разработке пакета прикладных программ для решения задачи прямоугольной упаковки // Технология и оборудование современного машиностроения: Тр. конф. Уфа, УГАТУ, 1998. С.28.

43. Мухачева Э.А., Валеева А.Ф., Гареев И.Р. Задача прямоугольной упаковки: метод динамического перебора с элементами генетики // Математическое программирование и приложения: Инф. бюл. №8 конф. Екатеринбург, УрО РАН, 1999. С.207-208.

44. Валеева А.Ф., Гареев И.Р. Стохастический метод динамического перебора для задач раскроя-упаковки // Дискретный анализ и исследование операций: Тр. рос. конф. Новосибирск, 2002. С.226.

45. Гареев И.Р. Метод динамического перебора для решения задачи негильотинного прямоугольного раскроя // XXV Гагаринские чтения: Тр. междунар. молодежи, науч. конф. М. 1999. т.2. С.856-857.

46. Гареев И.Р. Метод усеченного перебора для решения задачи одномерной упаковки // Математическое моделирование в решении научных и технических задач. Выпуск 2. Уфа. 2001. С.61-65.

47. Scheithauer G., Terno I. The modified integer round-up property of the one-dimensional cutting stock problem // European Journal of Operational Research. 1995. Vol.84. P. 563-571.

48. Гареев И.Р. «Метод перебора с усечением для задачи одномерной упаковки» // Дискретный анализ и исследование операций: Тр. рос. конф. Новосибирск, 2002. С.227.

49. Schwerin P. and Wascher G. (1997) The Bin-Packing Problem: A problem Generator and Some Numerical Experiments with FFD Packing and MTP. International Transactions in Operational Research. № 5/6.

50. E.Falkenauer A Hybrid Grouping Genetic Algorithm for Bin Packing //Journal of Heuristics. 1998. №1. P.5-30.

51. Hopper An Empirical Investigation of Meta-heuristic and Heuristic Algorithms for a 2D Packing Problem. European Journal of Operations Research. № 6. 1999.

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

53. Усманова А. Р. Анализ составляющих метода поиска с запретами для задачи упаковки в контейнеры. Дисс. физ.-мат. наук. Уфа, 2002. - 85с.

54. Гареев И.Р. Задача одномерной упаковки: метод перебора с усечением и вычислительный эксперимент // Принятие решений в условиях неопределенности: Межвуз. науч. сб. Уфа, 2002. С.175-181.

55. Валеева А.Ф, Гареев И.Р. Задача одномерной упаковки: вычислительный эксперимент с методом динамического перебора // Принятие решений в условиях неопределенности: Межвуз. науч. сб. Уфа, 2000. С.74-79.

56. Valeyeva A.F, Gareyev I.R. Method ST and method DSS1 for bin packing problem // The Sixteenth Conf. of the Int. Federation in Operational Research. Edinburg, UK: Univ. of Edinburg. 2002. P.50.

57. Автоматизация технологической подготовки заготовительного производства / под общей ред. Г.П.Гырдымова. Ленинград: Машиностроение, 1990. - 350с.

58. Автоматизация проектно-конструкторских работ и технологической подготовки производства в машиностроении, Т1, Т2/под ред.О.И.Семенкова.-Минск: Высшая школа, 1977. 312с.

59. Гамберг В .Я, Липовецкий А.И, Петунин А.А. Автоматизация проектирования раскройных карт в условиях индивидуального производства//Кузнечно-штамповочное производство, 1982.-N3-C.26-27.

60. Свидетельство об официальной регистрации программы для ЭВМ №2001610311. Прямоугольная упаковка / И.Р .Гареев. М.: Российское агентство по патентам и товарным знакам (Роспатент). 24.01.2001.

61. Бабаев Ф. В. Оптимизация раскроя материалов: Обзор. М.: НИИМАШ, 1978.-72 с.139

62. Бабаев Ф. В. Оптимальный раскрой материалов с помощью ЭВМ. М.: Машиностроение, 1982. - 168 с.

63. A.F. Valeyeva and I.E. Totskov. Developed of Three-Dimensional Methods Decision Making under Conditions of Uncertainty (Cutting-Packing Problems). Ufa, 1998.-P. 198-206.

64. Valeyeva A.F., Gareyev I.R. Method of dynamic sorting for 3-D for bin packing problem // The Sixteenth Conf. of the Int. Federation in Operational Research. Edinburg, UK: Univ. ofEdinburg. 2002. P. 14.

65. Валеева А.Ф., Тоцков И.Е., Гареев И.Р. Методы решения задачи прямоугольной упаковки // Интеллектуальное управление в сложных системах 99: Тр. респ. науч.-техн. конф. Уфа, 1999. С.36-38.

Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.