viagra super force

+7(495) 123-XXXX  г. Москва

Выпуски журналов

  • Серия
  • Серия
  • Серия
  • Серия
  • Журнал
  • Журнал
  • Журнал
  • Журнал

А.М. Субботин,  (Пермский национальный исследовательский политехнический университет)

Р.Т. Мурзакаев,  (К.т.н., доцент, Пермский национальный исследовательский политехнический университет)

Серия «Естественные и Технические науки» # ЯНВАРЬ  2017

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

Ключевые слова: Задача раскроя, параллельные вычисления, потоки, алгоритм Всемирного потопа, вычисление холостого хода, островная модель.

 

Задача раскроя материала, как подзадача сложной системы автоматизации производства, относится к классу NP-трудных задач комбинаторной оптимизации [1,2,3,4,16]. Это означает, что алгоритма полиномиальной сложности для её оптимального решения до сих пор не найдено, и точный результат в общем случае может быть получен только за экспоненциальное время. [5,6,7] Приближенные алгоритмы решения данной задачи зачастую использую различные методы сокращения перебора [8,9,10]. Поэтому важным этапом при разработке алгоритма раскроя является его быстродействие, которое позволит перебрать больше вариантов при тех же временных затратах.

Часто для построения холостого хода режущего инструмента используются метаэвристические алгоритмы [11,12,17]. Использование метаэвристик может потребовать больших ресурсов. Оценка особей может длиться достаточно долго: это может быть запуск модели, либо анализ структуры сложного химического соединения. Поэтому параллельные методы являются способом ускорить работу таких алгоритмов [12].

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

Целью данной работы является минимизация длины холостого хода режущего инструмента за счёт распараллеливания алгоритма Всемирного потопа (TheGreatDelugeAlgorithm, GDA) [14, 15].

В [13,15] описан алгоритм построения холостого хода режущего инструмента программного комплекса Itas Nesting. Программе необходимо построить путь перемещения режущего инструмента по листу так, чтобы перемещение инструмента между деталями было минимальным. Режущий инструмент перемещается от одной детали до другой по потенциальным точкам врезки. Точки врезки располагаются в углах деталей. На окружности можно врезаться в любом месте, т.е. на окружности бесконечно много возможных точек врезки. Также учитывается порядок выреза деталей: если есть вложенные детали, то они вырезаются раньше [19].

Представим метод, описанный в [13,15], в виде схемы алгоритма построения холостого хода режущего инструмента (рис. 1). Его недостатком является то, что он выполняется последовательно.

Читать полный текст статьи …


СПИСОК ЛИТЕРАТУРЫ:
1. Мурзакаев, Р.Т., Шилов, В.С., Буркова, А.В. Основные методы решения задачи фигурной нерегулярной укладки плоских деталей. // Инженерный вестник Дона. – 2013 – No. 4. – URL: ivdon.ru/magazine/archive/n4y2013/204.
2. Петунин А.А. Методологические и теоретические основы автоматизации проектирования раскроя листовых материалов на машинах с числовым программным управлением: дис. д.т.н.: 05.13.12. Екатеринбург, 2009. - 348 с.
3. Петунин А. А., Мухачева Э. А., Филиппова А. С. Метод прямоугольной аппроксимации для решения задач нерегулярного фигурного раскроя-упаковки. // Информационные технологии. - №1. – 2008. с. 28-31.
4. Fayzrakhmanov R.A., Murzakaev R.T., Mezentsev A.S., Shilov V.S. Applying the greedy algorithm for reducing the dimensionality of the dynamic programming method in solving the one-dimensional cutting stock problem // Middle-East Journal of Scientific Research. -№ 19 (3). - P.412-416. - 2014 - URL: http://www.idosi.org/mejsr/mejsr19(3)14/14.pdf (дата обращения: 12.03.2014)
5. Валиахметова Ю. И. Мультиметодная технология моделирования ортогональной упаковки и размещения прямоугольно-ориентированных заготовок [Текст]. – автореф. к. т. н.: 05.13.18 / Юлия Ильясовна Валиахметова. – Уфа, 2008. – 19 с.
6. Sykora A.M. Nesting problems: exact and heuristic algorithms. // A Thesis for the degree of Doctor of Philosophy in the University of Valencia, Valencia, 2012– 187 p.
7. Fayzrakhmanov R.A., Murzakaev R.T., Mezentsev A.S., Shilov V.S. Application of the Group Decoder for Solving the Orthogonal Materials Cutting Problem // World Applied Sciences Journal 28 (10): 1361-1365. – 2013. – URL: www.idosi.org/wasj/wasj28(10)13/4.pdf.
8. Вальковский В.А. Распараллеливание алгоритмов и программ. Структурный подход / Вальковский В.А. – М.: Радио и связь, 1989. 176с.
9. Воеводин В.В. Параллельные вычисления / Воеводин В.В., Воеводин Вл.В. – СПб.: БХВ-Петербург, 2002. 608 с.
10. Quinn M. J. Designing Efficient Algorithms for Parallel Computers. - McGraw-Hill, 1987.
11. Щербина О.А. Метаэвристические алгоритмы для задач комбинаторной оптимизации (обзор). Симферополь: Таврический национальный университет, 2014 — 17с.
12. Люк Ш. Основы метаэвристик. 2009 [электронный ресурс]. URL: http://qai.narod.ru/GA/metaheuristics.html (дата обращения: 09.11.2015).
13. Мурзакаев Р.Т., Шилов В.С., Брюханова А.А. Программный комплекс фигурного раскроя материала Itas Nesting. — Вестник ПНИПУ. Электротехника, информационные технологии, системы управления. №13, 2015. — 15-25с.
14. Dueck G. New Optimization Heuristics. The great deluge algorithm and the record-to-rector travel. Journal of Computational Physics 104, 86-92 (1993).
15. Мурзакаев Р.Т., Приступов В.С. Построение маршрута режущего инструмента на основе алгоритма "всемирного потопа". — В мире научных открытий № 10.2(70), Красноярск: Научно-инновационный центр, 2015. — 828-839 с.
16. Субботин А.М., Шилов В.С. Параллельные вычисления в задачах раскроя материалов. — В мире научных открытий № 10.2(70), Красноярск: Научно-инновационный центр, 2015. — 907-920 с.
17. Валиахметова Ю.И., Филиппова А.С. Теория оптимального использования ресурсов Л.В. Канторовича в задачах раскроя-упаковки: обзор и история развития методов решения. - Вестник УГАТУ Т.18, №1(62), 2014. - 186-197 с.
18. McGill Robert, Tukey John W., Larsen Wayne A. Variations of Box Plots. The American Statistician 32 (1): 12–16, 1978.
19. Файзрахманов Р.А., Мурзакаев Р.Т., Бурылов А.В., Приступов В.С. Минимизация общего времени резки с учетом технологий для станков с ЧПУ. — Электротехника №11, 2016. — 7-12 с.
 



© 
А.М. Субботин, Р.Т. Мурзакаев, Журнал "Современная наука: актуальные проблемы теории и практики".
 

 

 

 
SCROLL TO TOP

 Rambler's Top100 @Mail.ru