ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЙ В ЗАДАЧАХ РАСКРОЯ МАТЕРИАЛОВ

Andrey Mikhaylovich Subbotin, Vadim Sergeevich Shilov, Vadim Sergeevich Shilov


Аннотация


Задача раскроя материала, как подзадача сложной системы автоматизации производства, относится к классу NP-трудных задач комбинаторной оптимизации. Учитывая тот факт, что скорость работы рассматриваемых алгоритмов невозможно существенно увеличить без критических потерь точности, а так же учитывая особенности архитектуры современных процессоров, а именно – многоядерность и распараллеливание задач, то одним из вариантов увеличения скорости работы является использование параллельных вычислений.

В статье рассматривается такая подзадача раскроя материала как формирование групп деталей. Этот алгоритм производит группировку двух одинаковых деталей, с целью минимизации занимаемой ими площади. Так как формирование группы деталей происходит независимо от других деталей, то имеется возможность распараллелить данный алгоритм. В результате был спроектирован и разработан алгоритм группировки двух одинаковых деталей для программного комплекса Itas Nesting. Было проведено тестирование разработанного модуля, которое показало ускорение работы алгоритма на трех процессорах в 1.87 раза.


Ключевые слова


задача раскроя; параллельные вычисления; карта раскроя; группировка деталей

Литература


Мурзакаев, Р.Т., Шилов, В.С., Буркова, А.В. Основные методы решения задачи фигурной нерегулярной укладки плоских деталей. // Инженерный вестник Дона. – 2013 – No. 4. – URL: ivdon.ru/magazine/archive/n4y2013/204.

Петунин А.А. Методологические и теоретические основы автоматизации проектирования раскроя листовых материалов на машинах с числовым программным управлением: дис. д.т.н.: 05.13.12. Екатеринбург, 2009. - 348 с.

Петунин А. А., Мухачева Э. А., Филиппова А. С. Метод прямоугольной аппроксимации для решения задач нерегулярного фигурного раскроя-упаковки. // Информационные технологии. - №1. – 2008. с. 28-31.

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)

Валиахметова Ю. И. Мультиметодная технология моделирования ортогональной упаковки и размещения прямоугольно-ориентированных заготовок [Текст]. – автореф. к. т. н.: 05.13.18 / Юлия Ильясовна Валиахметова. – Уфа, 2008. – 19 с.

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.

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.

Вальковский, В.А. Распараллеливание алгоритмов и программ. Структурный подход / Вальковский В.А. – М.: Радио и связь, 1989. 176с.

Воеводин, В.В. Параллельные вычисления / Воеводин В.В., Воеводин Вл.В. – СПб.: БХВ-Петербург, 2002. 608 с.

Корнеев В.В.. Параллельные вычислительные системы. – М.: Нолидж, 1999.

Информационно-аналитические материалы по параллельным вычислениям [электронный ресурс]. URL: http://www.parallel.ru (дата обращения: 07.04.2015).

Бекон, Д. Операционные системы / Бекон Д., Харрис Т.; пер. с англ. – Спб.: Питер; Киев: Издательская группа BHV, 2004. 800с.

Quinn M. J. Designing Efficient Algorithms for Parallel Computers. – McGraw-Hill, 1987.

Hans-J. Boehm. Destructors, finalizers, and synchronization – ACM Press, 2003.

Andrews G.R. Foundations of Multithreading, Parallel and Distributed Programming – Addison-Wesley, 2000.

Чертов М.А., Руденский Г.Е., Псахье С.Г., Скворцов А.В. Алгоритм группировки геометрических объектов при автоматическом раскрое листового материала с использованием локальных характеристик формы – Вычислительные технологии. 2006. Т. 11. № 2. С. 93-102.

Мурзакаев Р.Т., Шилов В.С., Брюханова А.А. Программный комплекс фигурного раскроя материала Itas Nesting. – Вестник Пермского национального исследовательского политехнического университета. Электротехника, информационные технологии, системы управления – 2015 – №13 – 125 с.

Крэг Ларман. Применение UML 2.0 и шаблонов проектирования – 3-е изд. – М.: Вильямс, 2006. – 736 с.

Goetz B., Peierls T. Java Concurrency in Practice – Addison Wesley Professional, 2006.

Гергель В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. Издательство Нижегородского государственного университета, 2003.




DOI: https://doi.org/10.12731/wsd-2015-10.2-907-920

Ссылки

  • На текущий момент ссылки отсутствуют.


Bookmark and Share


(c) 2016 В мире научных открытий



ISSN 2658-6649 (print)

ISSN 2658-6657 (online)

HotLog Яндекс цитирования