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

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

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

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

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

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

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

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

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

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

Сложность решения задач Р-У обусловлена их принадлежностью к классу 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 работ.

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

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

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 для двумерной упаковки был использован для решения задачи трехмерной упаковки и применен для расчета плотного размещения ящиков в трехмерных контейнерах различной емкости с учетом грузоподъемности на ОАО «УралХимМаш».

ЗАКЛЮЧЕНИЕ

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

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

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.