Помощь в написании студенческих работ
Антистрессовый сервис

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

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

На практике, процесс оптимизации расхода рулонных материалов зависит от оптимальности 1D и 2D карт кроя, составляемых на предприятиях. Кроме того, следует отметить, что данный процесс требует обработки значительных объемов информации (информации о паспортах материалов, требований по оптимальности, организационных особенностей конкретного предприятия и т. п.) — всех тех параметров, которые… Читать ещё >

Разработка автоматизированных средств оптимизации одномерного раскроя (реферат, курсовая, диплом, контрольная)

Содержание

  • Глава I. Обзор предметной области
    • 1. 1. Описание технологического процесса расчета куска 9 1.1.1. Разбраковка и промер кусков материалов
      • 1. 2. 1. Расчет кусков
      • 1. 2. 2. Подготовка к расчету
      • 1. 2. 3. Расчет
      • 1. 2. 4. Оформление карты кроя
      • 1. 2. 5. Настилание
    • 1. 2. Специфика задачи одномерного раскроя
    • 1. 3. Классические модели 1D-CSP
      • 1. 3. 1. Формулировка Гил мори, Гомори
      • 1. 3. 2. Задачи с несколькими типами заготовок
      • 1. 3. 3. Задача минимизации типов карт кроя
    • 1. 4. Алгоритмы
      • 1. 4. 1. Метод секущих плоскостей
      • 1. 4. 2. Метод ветвей и границ
      • 1. 4. 3. Эвристически методы
  • Глава II. Методология проведения исследований
    • 2. 1. Постановка задачи и разработка концептуальной модели
    • 2. 2. Формализация задачи
    • 2. 3. Выбор метода и алгоритма решения
    • 2. 4. Проверка адекватности и корректировка модели
    • 2. 5. Поиск решения на модели
    • 2. 6. Реализация найденного решения на практике
  • Глава III. Этапы построения информационной среды и алгоритмов решения задачи 1D-CSP
    • 3. 1. Анализ информационной модели производственного цикла
    • 3. 2. Разработка алгоритмов 45 3.2.1. Расчет карт кроя для параллельного метода раскроя 47 3.2.2 Расчет карты кроя для последовательного метода раскроя 62 3.2.3. Расчет для метода «красных» полотен
    • 3. 3. Тестирование
  • Глава IV. Практическая реализация
    • 4. 1. Общая архитектура
    • 4. 2. Хранилище данных
    • 4. 3. Модуль управления виртуальным складом
    • 4. 4. Модуль оптимального расчета
    • 4. 5. Применение

Подготовительно-раскройное производство относится к классу материалоемких производств. Именно поэтому, во многом экономические показатели предприятий, на которых выполняются операции раскроя, напрямую связаны с задачей оптимального расхода материалов [1].

На практике, процесс оптимизации расхода рулонных материалов зависит от оптимальности 1D и 2D карт кроя, составляемых на предприятиях. Кроме того, следует отметить, что данный процесс требует обработки значительных объемов информации (информации о паспортах материалов, требований по оптимальности, организационных особенностей конкретного предприятия и т. п.) — всех тех параметров, которые используются при выполнении расчета. В настоящее же время решение данной задачи основывается на опыте и интуиции квалифицированных работников данной сферы. Выполнение подобной работы без привлечения вычислительных средств, естественно приводит к завышенным затратам временных и материальных ресурсов. Поэтому требуется разработка современных вычислительных средств (программ), позволяющих формировать решения с большей степенью оптимальности и научной обоснованностью. Это особенно актуально в условиях все возрастающей конкуренции на рынке в условиях перехода России к рыночным отношениям.

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

Кроме того, актуальным является и рассмотрение другого аспектаглобальной системной интеграции производства [2], то есть объединение единой информационной средой связанных между собой технологических операций, что приводит к естественной необходимости проведения системного анализа рассматриваемой сферы деятельности, а именноподготовительно-раскройного производства.

На большинстве предприятий выполнение операций, входящих в комплекс работ подготовительно-раскройного производства, выполняется без привлечения современных вычислительных средств. Как уже говорилось, это приводит к повышенным временным, а также кадровым затратам, и как следствие, снижению экономических показателей предприятия. Тем не менее, интенсивное развитие информационных технологий в последнее десятилетие позволяет создавать автоматизированные средства для выполнения все большего спектра задач [3−6], которые предъявляют новые требования к организации работы предприятий. В настоящее время все более актуальными становятся вопросы автоматизации производства в полном объеме с целью возможного перехода к созданию на предприятии единой информационной среды, позволяющей гибкое интегрирование современных средств проектирования, производства, управления (Computer Aided Design, Computer Aided Manufacturing, Product Data Managment систем) и т. д., которые позволяют эффективно решать задачи оперативного планирования производства. Поэтому в таких условиях особенно важным становится поиск новых подходов, обеспечивающий целесообразную перестройку системы оптимального расчета карт кроя с учетом жизненных реалий, в частности вопросы создания САМ средств для рассматриваемой в работе задачи одномерного раскроя материала. Уровень развитие вычислительной техники в последние десятилетия позволяет успешно решать поставленные задачи в необходимом для практики объеме, а также качестве [7].

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

Методы исследования. В работе использованы методы исследования операция, включающие в себя математическое моделирование, численные методы, проведение экспертных оценок.

Научная новизна исследования заключается в том, что в ходе работы были решены следующие задачи:

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

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

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

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

Положения, выносимые на защиту.

1. Формулировки задачи одномерного раскроя подготовительно-раскройного производства: a. Методом параллельного настилания материалов b. Методом последовательного настилания материалов с. Методом «красных» полотен.

2. Алгоритмы решения сформулированных задач на основе разработанных эвристических подходов.

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

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

Структура диссертационной работы.

В главе I проведен анализ существующей в условиях реального подготовительно-раскройного производства (на примере швейных предприятий) системы формирования оптимальных одномерных карт кроя. Описаны основные стадии, средства, а также методы, использующиеся в рамках подготовительно-раскройного производства. Сделан обзор алгоритмов, являющихся базовыми для исследований, проводимых в области решения задач одномерного раскроя (ID Cutting Stock Problem).

В главе II описываются основные этапы, при решении задач исследования операций, к которым относится и исследование задачи одномерного раскроя.

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

В главе IV обсуждаются аспекты, связанные с процессами внедрения разработанных алгоритмов, в виде автоматизированных вычислительных средств, интегрируемых в информационную среду конечного предприятия. Также описываются подходы реализации конечных САМ средств, соответствующих современным требованиям, которые предъявляются к высокоуровневым средствам автоматизации. Описано практическое применение и экономическая выгода системы.

В заключении подводятся итоги диссертационной работы.

Заключение

.

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

1. Процесс является многопоточным, многостадийным.

2. Требуется тщательное изучение информационных потоков с целью выявления основных объектов изучения.

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

1. В настоящее время исследование задач раскроя (упаковки) проводится в большей степени на теоретическом уровне.

2. Предлагаемые модели CSP задач описывают весьма ограниченный круг практически интересных задач, что значительно снижает их практическую применимость.

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

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

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

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

  1. Организация рационального использования материалов в швейной промышленности / И. Н. Град, Е. Г. Авсеев, В. Ф. Петроченко. М.: Легпромбытиздат, 1986. С. 168.
  2. Основные направления автоматизации процессов подготовительно-раскройного производства в швейной промышленности / Т. В. Бабар, Т. В. Бурова, В. Н. Соколов // Оборудование для швейной промышленности: Обзорн. Информ. ЦНИИТЭИлегром. М., 1986. Вып. 3. С. 56
  3. Автоматизированный настилочно-раскройный комплекс отечественного производства / Ю. А. Балкастов, Б. П. Старков, С. Т. Ильина // Швейная промышленность. 1992. № 2. С. 18−19.
  4. Автоматизированная промерочно-браковочная машина / А. С. Железняков, В. А. Александров, К. А. Беличенко, Ю. В. Елтышев // Швейная промышленность. 1991. № 5. С. 19−21.
  5. Автоматизированная система регистрации пороков и формирования массива отрезов куска ткани / А. С. Железняков, В. А. Александров, К. А. Беличенко, Ю. В. Елтышев // Швейная промышленность. 1991. № 3. С.15−17.
  6. .Р. Модернизация и расширение САПР Investmark DS // Швейная промышленность. 1995. № 6. С. 24.
  7. Armbruster М. A solution procedure for a pattern sequencing problem as part of a one-dimensional cutting stock problem in the steel industry. European Journal of Operational Research 141 (2002) 328−340
  8. A.C., Смирнова Г. П. Оперативно-производственное планирование и диспетчеризация // Швейная промышленность. 1987. № 1. С. 21−23.
  9. В.И. Автоматизированный комплекс рационального использования материалов на швейном предприятии. М.: Легпромбытиздат, 1987. С. 152.
  10. Ю. Д. Современные средства автоматизации процесса подготовки раскроя швейных изделий // Швейная промышленность. 1994. № 2. С. 13−15.
  11. Справочник по подготовке и раскрою материалов при производстве одежды / Под ред. И. И. Галынкера. М.: Легкая индустрия, 1980, С. 272.
  12. И.И. Подготовка и настилание тканей. М.: Легкая индустрия, 1969. С. 346
  13. Е.С. Исследование операций: задачи, принципы, методология. Учеб. для вузов. М.: Дрофа. 2004. С. 206.
  14. А. Таха. Введение в исследование операций. Шестое издание, Вильяме, 2001. С. 912.
  15. О.Г. Комплексное применение методов дискретной оптимизации. М.: Наука, 1981.
  16. Н.Н., Иванилов Ю. П., Столярова Е. М. Методы оптимизации. М.: Наука, 1978.
  17. X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985. С. 512.
  18. С.А. Линейное программирование. М.: Наука, 1981.
  19. М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. М.: Наука, 1981.
  20. Э. Севидж. Сложность вычислений. М.: Факториал, 1998. С. 368.
  21. Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ.
  22. Garey M.R., Johnson D.S., Stockmeyer L.J. Some simplified NP-completethproblems // Proc. 6 Annual ACM Symp. on Theory of Computing. Seattle, 1974. P. 47−63.
  23. Л.В., Залгаллер В. А. Рациональный раскрой промышленных материалов. Новосибирск:. Наука, 1971. С. 299.
  24. Gilmore P. and Gomory R. A linear programming approach to the cutting stock problem: Part 2 // Operations Research. 1963. V. l 1. P. 863−888.
  25. Gilmore P.C. and Gomory R.E. A linear programming approach to the cutting-stock problem. // Operations Research. 1961. V.9. P. 849−859.
  26. Vanderbeck F., Wolsey A.L. An exact algorithm for IP column generation. Operation Research Letters 19(1996) P. 151−159.
  27. Vanderbeck F. Computational study of a column generation algorithm for bin packing and cutting stock problems. Digital Object Identifier (DOI) 10.1007/s 101 079 900 096. Published online July 19, 1999
  28. Belov G. Problems, models and algorithms in one- and two-dimensional cutting. //Dissertation. 2003
  29. Scheithauer G., Terno J., Muller A., Belov G. Solving one-dimensional cutting stock problems exactly with a cutting plane algorithm. Dresden University, Institute of Numerical Mathematics, June, 1999
  30. Aboudia R. and Barciab P. Determining cutting stock patterns when defects are present. Annals of Operations Research 82(1998) P. 343−354.
  31. Holthaus O. Decomposition approaches for solving the integer one-dimensional cutting stock problem with different types of standard lengths. European Journal of Operational Research 141 (2002) P. 295−312.
  32. Э.А., Мухачева A.C., Белов Г. Н. Методы последовательного уточнения оценок: алгоритм для задачи одномерного раскроя // Информационные технологии. 2000. № 2. С. 11−17.
  33. F. Vanderbeck, Exact algorithm for minimising the number of setups in the one-dimensional cutting stock problem, Operations Research 48 (2000) 915−926.
  34. Umetani S., Yagiura M., Ibaraki T. One-dimensional cutting stock problem to minimize the number of different patterns. European Journal of Operational Research 146 (2003) P. 388−402.
  35. Belov G. and Weismantel R. A Class of Subpattern Formulations for One-Dimensional Stock Cutting. Dresden University, Institute of Numerical Mathematics, October, 2003
  36. Belov G., Scheithauer G. Solving the general one-dimensional cutting stock problem with a cutting plane approach. Dresden University, Institute of Numerical Mathematics, June, 2000
  37. И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации. // Информационные технологии. 1999. № 1. С. 2−7.
  38. А.А., Сигал И. Х., Финкелыитейн Ю. Ю. Метод ветвей и границ. Обзор теории, алгоритмов, программ и приложений // Math Operation Forsch. Statist. Ser. Optimization. 1977. V. 8. № 2. P. 253−280.
  39. Э. Численные методы оптимизации. М.: Мир, 1974.
  40. .Т. Введение в оптимизацию. М.: Наука, 1983.
  41. И.В. Математические модели и методы решения задач дискретной оптимизации. Киев: Наукова думка, 1985.
  42. И.В., Каспшицкая М. Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации. Киев: Наукова думка, 1981.
  43. И.Х. Параметризация и исследование некоторых задач дискретного программирования большой размерности // Известия РАН. Теория и системы управления. 2001. № 2. С. 83−92.
  44. А. Теория линейного и целочисленного программирования. Т. 2. М.: Мир, 1991.
  45. Vance P. Branch-and-Price Algorithms for the One-Dimensional Cutting Stock Problem. Computational Optimization and Applications, 9(1998) P. 211−228.
  46. Valerio J.M. de Carvalho. Exact solution of bin-packing problems using column generation and branch-and-bound. Annals of Operations Research 86(1999) P. 629−659.
  47. Valerio J.M. de Carvalho. A Note on branch-and-price algorithms for the one-dimensional cutting stock problems. Computational Optimization and Applications, 21(2002) P. 339−340.
  48. Savelsbergh M. A Branch-and-Price Algorithm for the Generalized Assignment Problem. Georgia Institute of Technology. July 1995
  49. Land A.H., Doig A.G. An automatic method of solving discrete programming problems. // Econometrica. V.28(1960). № 3. P. 497−520.
  50. Boon J.Y., Ken V.R. Establishing the optimality of sequencing heuristics for cutting stock problems. European Journal of Operational Research 84(1995) P. 590−598.
  51. Martello S., Toth P., Knapsack Problems: Algorithms and Computer Implementations // Operation Research. V.32(1990)
  52. К.Г., Ннкитов C.A. Оптимизация использования сырья в задаче линейного раскроя // Информационные технологии. 2003. № 11.
  53. . А. Вероятностные жадные эвристики для задачи упаковки в контейнеры//Санкт-Петербург: ОПТИМ. 2001. С. 141−146.
  54. Ю., Уманова А. Вероятностный поиск с запретами для задачи упаковки в контейнеры // XII Байкальская международная конференция. Иркутск. 2001. С. 22−27.
  55. Vahrenkamp R. Random search in the one-dimensional cutting stock problem. European Journal of Operational Research 95(1996) P. 191−200.
  56. Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования. М.: Наука, 1976.
  57. В.Р. Аппроксимационно-комбинаторный метод и некоторые его приложения // ЖВМиМФ. 1974. Т.14, № 6. С.1464−1487.
  58. А.Ф., Гареев И. Р., Мухачева Э. А. Задача одномерной упаковки: рандомизированный метод динамического перебора и метод перебора с усечением. // Приложение к «Информационные технологии». 2003. № 2.
  59. С.Д., Гурвич Ф. Г. Математико-статистические методы экспертных оценок. Москва, 1980. С. 262
  60. Донецкий государственный университет управления, http://dsum.edu.ua.
  61. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности / В. Р. Хачатуров и др. М.: Наука, 2000.
  62. MySQL: The World’s Most Popular Open Source Database, http://www.mysql.org
  63. Д.Н. Малышев, Г. Г. Андреев. Теория и практика решения задач 1D-CSP задач на предприятиях легкой промышленности. // Процессы и методы обработки информации: Сб.ст. / Моск.физ.-тех. ин-т. М., 2006. С. 199−207.
  64. А. А. Сигал И.Х., Финкельштейн Ю. Ю. Об эффективности комбинаторных методов в дискретном программировании // Современное состояние теории исследования операций. М.: Наука, 1979. С.283−310.
  65. К.Г. Андреева, Д. Н. Малышев, С. А. Никитов, A.M. Павлов. Задача рационального использования сырья в рамках САМ-системы предприятия легкой промышленности. // Автоматизация в промышленности. Декабрь 2004. С. 14−17.
  66. Mixed Integer Programming (MIP) solver, http://lpsolve.sourceforge.net.
  67. E.C. Теория вероятностей: Учеб. для вузов. М.: Высшая школа. 2001. С. 575.
  68. Д.Н. Малышев, Г. Г. Андреев. Исследование и разработка средств для решения 1D-CSP задачи в информационной среде предприятий. // Тезисы 5-й международной конференции CAD/CAM/PDM. Под ред. Е. И. Артомонова. / М.: ИПУ РАН. 2005, С. 84−85.
  69. Д.Н. Малышев, Г. Г. Андреев. Реализация САМ средств для решения одномерной задачи раскроя. //Современные проблемы фундаментальных и прикладных наук. Часть V: Труды XLVIII научной конференции /Моск. физ. тех. ин-т. — М. — Долгопрудный, 2005. — С. 117.
  70. Д.Н. Малышев. Экспериментальная среда для эффективного проведения исследований задачи одномерного раскроя на предприятиях швейной промышленности. // Процессы и методы обработки информации: Сб.ст. / Моск.физ.-тех. ин-т. -М., 2006. С. 193−198.
  71. Zak E.J. Row and column generation technique for a multistage cutting stock problem. Computers & Operations Research 29 (2002) P. 1143−1156.
  72. Benchmarks for optimization software, http://plato.la.asu.edu/bench.html
  73. XML Extensible Markup Language 1.1, W3C Recommendation 04 February 2004 http ://www.w3 .org/TR/2004/REC-xml 11 -20 040 204/
  74. XML Path Language (XPath) 1.0, W3C Recommendation 16 November 1999 http://www.w3 .org/TR/xpath
  75. XSL trasformations (XSLT) 1.0, W3C Recommendation 16 November 1999 http://www.w3 .org/TR/xslt
  76. Зачем штриховой код? / Ю. А. Доможиров, В. В. Лемчиков, Т. Т. Рябинская //Швейная промышленность. 1997. № 2. С. 15−16.
  77. Устройства для маркировки и отметки пороков: Пат. 3 436 231 Германия.
Заполнить форму текущей работой

Сессия? Спокойно!