Содержание к диссертации
Введение
Глава 1. Обзор работ по теме исследования 10
1.1. Постановка задачи размещения геометрических объектов и методы ее решения 10
1.2. Обзор алгоритмов и программ прямоугольно раскроя в единичном производстве 18
1.3. Обзор алгоритмов и программ фигурного раскроя в единичном производстве 23
1.4. Постановка задачи 27
Глава 2. Алгоритмы проектирования раскройных карт 31
2.1. Различные подходы к размещению геометрических объектов произвольной формы 31
2.2. Алгоритмы заливки заданной области 46
2.3. Заполнение отверстий заготовок при укладке 53
Глава 3. Алгоритмы оптимизации раскройных карт 58
3.1. Оптимизация последовательности укладки 58
3.2. Оптимизация раскроя за счет использования блоков деталей 65
3.3. Комбинирование различных алгоритмов укладки плоских геометрических объектов 69
Глава 4. Особенности программной реализации Nest Class Library 81
4.1. Структура современных алгоритмов автоматического раскроя 81
4.2. Создание приложений ориентированных на работу в многопроцессорных системах 97
4.3. Интеграция NCL с другими CAD системами 101
4.4. Подсистема формирования отчетности NCL 105
4.5. Возможности расширения и модификации NCL 106
4.6. Внедрение результатов работы 107
Заключение 112
Приложение 115
Список использованной литературы 117
- Обзор алгоритмов и программ прямоугольно раскроя в единичном производстве
- Различные подходы к размещению геометрических объектов произвольной формы
- Комбинирование различных алгоритмов укладки плоских геометрических объектов
- Создание приложений ориентированных на работу в многопроцессорных системах
Введение к работе
Построение оптимальных карт раскроя материала является одной из самых трудоемких задач заготовительного производства. В тоже время это одна из самых важных задач в ресурсосберегающих технологиях, поскольку напрямую ведет к экономии материала и снижению отходов. В настоящее время для решения этой задачи активно используются все возрастающие возможности современных ЭВМ, что позволило значительно ускорить и упростить процесс генерации раскройных карт по сравнению с неавтоматизированными методами [1]. Начало теоретическим исследованиям в области методов рационального раскроя положили труды академика Канторовича Л. В. [2, 3], в которых он показал возможность эффективного решения оптимизационных задач с помощью ЭВМ.
Еще одним преимуществом при использовании ЭВМ для получения раскройных карт является возможность интеграции процесса подготовки раскроя с процессом генерации управляющей программы для станков термической резки, что позволяет значительно снизить трудоемкость и уменьшить время процесса подготовки управляющих программ. Следует также отметить, что максимальная эффективность может быть достигнута только в случае полной автоматизации процессов раскроя и подготовки управляющих программ. Большую роль в построении интегрированной программно-аппаратной системы играет наличие ЛВС, что позволяет передавать данные из одной подсистемы в другую без промежуточных носителей даже на большом удалении. Благодаря стремительному развитию компьютерных сетей, в том числе и Internet, в последние несколько лет широкое распространение получили системы позволяющие управлять процессом производства практически из любой точки Земли через web-интерфейс. Это позволило специалистам выполнять точную настройку оборудования и контролировать режимы его работы дистанционно, не
выезжая на предприятие, что конечно положительно сказывается на качестве выпускаемой продукции.
Следует отметить, что на большинстве машиностроительных предприятий задача заготовительного производства, а, следовательно, и задача раскроя относятся к единичным задачам. Как следствие, задача построения оптимального раскроя на этих предприятиях стоит наиболее остро и к ней предъявляется больше требований по сравнению с той же задачей на предприятиях ориентированных на выпуск серийной продукции. Например, если на предприятиях выпускающих серийную продукцию в основном используют нормативные и технологические методы раскроя материалов, которые основаны на определенных правилах построения раскройных карт, не требующих получения оптимального раскроя, то при единичном производстве напротив главным становится получение наиболее оптимальной раскройной карты, за минимально возможное время.
Исходя из особенностей единичного производства, оптимальным вариантом следует признать полностью автоматический подход к формированию раскройных карт и управляющих программ для станков с ЧПУ, только в этом случае будет достигнута производительность, удовлетворяющая условиям единичного производства.
В задаче раскроя можно выделить небольшую подзадачу, которая характерна именно для единичного производства и позволяет продемонстрировать всю математическую сложность задачи раскроя.
Требуется разместить п известных (в общем случае различных) плоских геометрических объектов (заготовок) в полубесконечной полосе, шириной а, обеспечив наибольший коэффициент заполнения занятой части полосы.
K = YS'/
где Sj — площадь і-го объекта; L - длина занятой части полосы.
Как нетрудно видеть, наибольший коэффициент достигается при наименьшем значении длины L, которая обычно выбирается в качестве минимизируемой функции цели.
Дальнейшее исследование этой математической модели со строгим аналитическим описанием [4] позволило показать отсутствие общих математических способов решения этой задачи. Применение ЭВМ с ее возможностями и разработка специализированных алгоритмов, способов и приемов для проектирования раскройных карт позволило показать эффективность использования компьютеров для решения задач раскроя. На протяжении последних 50 лет исследованиям в области раскроя и разработки новых алгоритмов укладки плоских заготовок было посвящено множество отечественных и зарубежных работ. Обзор этих работ приведен в главе 1.
Разработка автоматизированных методов проектирования
рационального раскроя особо остро стоит для единичного производства. Последние исследования в этой области позволяют сделать оптимистичный вывод, что в ближайшем будущем возможно появление методов, обладающих достаточным быстродействием и генерирующим раскройные карты с высоким коэффициентом использования материала. На сегодняшний же день следует признать, что существующие методы построение рациональных раскройных карт могут соперничать с раскройными картами, построенными человеком, только для специализированных задач раскроя. Например, исследования последних лет позволили достичь высоких результатов в области линейного и прямоугольного раскроя [4, 5, 6]. Современные алгоритмы, работающие с данной номенклатурой заготовок,
уже давно успешно применяются в производстве. Совершенно иначе обстоит дело с алгоритмами укладки заготовок произвольной формы. Большинство существующих разработок в этом направлении решают небольшие подзадачи, возникающие в глобальной задаче оптимального раскроя, и не способны эффективно работать на любой предложенной номенклатуре заготовок, что составляет неотъемлемую часть единичного производства. В данной работе делается попытка объединения сильных сторон каждого отдельно взятого алгоритма под управление одного, который в автоматическом режиме по определенным параметрам выбирает один или несколько специализированных алгоритмов наиболее подходящих для предложенных заготовок. На практике это означает возможность полного отказа от ручного труда на этапе подготовки раскройных карт.
Работа проводилась в рамках разработки САПР "СИРИУС", но построена таким образом, что может легко интегрироваться в любую из современных систем (AutoCAD, T-Flex и т.д.) обладающую возможностью подключать пользовательские модули для расширения базовых возможностей.
Проектирование раскроя на ЭМВ в самой простой ее постановки включает в себя два этапа. На первом этапе строится множество раскройных карт, удовлетворяющим заданным критериям, на втором — в этом множестве ищется лучшая карта. Согласно этому в процессе раскроя можно выделить два основных класса задач. Первая класс задач - это задачи геометрического моделирования на ЭВМ, в процессе которого решается вопрос о размещении заготовок на листе и получении раскройной карты, второй - это чисто оптимизационные задачи. Как показывают исследования и практические наработки второй класс задач можно свести к задачам переборного характера, например, к задаче минимизации некоторого функционала,
заданного на множестве перестановок из конечного числа символов [9] или использовать детерминированный метод динамического перебора [11].
Хотя применение оптимизационных алгоритмов и повышает вероятность построения рациональной раскройной карты, но их эффективность сильно зависит от методов получения раскройных карт. Именно от эффективности методов, работающих на этапе генерации раскройных карт, зависит результативность оптимизационных алгоритмов. Применение различных методов для укладки заготовок позволяет наиболее полно использовать мощь оптимизационных алгоритмов. Вторая глава данной диссертационной работы посвящена методам генерации допустимых раскройных карт. Исследованы различные специализированные алгоритмы построения раскройных карт, как для случая прямоугольных объектов, так и для объектов произвольной формы. Описаны способы укладки геометрических объектов произвольной формы и способы повышения быстродействия и качества алгоритмов работающих с произвольной геометрией заготовок. Разобраны основные приемы и алгоритмы, используемые при растровом подходе к проектированию раскройных карт.
В третьей главе обсуждаются вопросы, связанные с оптимизационными методами. Разобраны несколько методов позволяющих вести оптимизационную работу уже при небольшом количестве исходных данных. Это требование является критичным при использовании методов оптимизации в алгоритмах, работающих с заготовками сложной формы, так как в таких алгоритмах генерация раскройной карты занимает значительное время даже при использовании современной вычислительной техники. Также разобрана стратегия выбора наилучшего набора алгоритмов для построения раскройных карт на заданном наборе заготовок и комбинирование различных алгоритмов при построении одной раскройной карты.
Возможность оперировать с различными специализированными алгоритмами укладки заготовок, мощный аналитический модуль, позволяющий на основании анализа геометрии спрогнозировать применение того или иного алгоритма укладки, гибкие алгоритмы построения раскройных карт и оптимизации - ядро алгоритмического комплекса использованного при создании универсального пакета для раскроя листового материала.
Для реализации Nest Class Library (NCL) был выбран объектно-ориентированный язык C++, что позволило построить хорошо структурированный программный продукт, обладающий огромным потенциалом для дальнейшего развития. Следствием применения объектно-ориентированного подхода стала возможность легко интегрировать NCL в другие программные продукты, расширяя как их возможности, так и возможности NCL. Например, при интеграции с AutoCAD фирмы Autodesk, NCL получает возможность напрямую работать с чертежами AutoCAD и генерировать раскройные карты напрямую в его среде, используя весь набор инструментов, предоставляемый этим пакетом без необходимости создавать промежуточные файлы для передачи графической информации. В четвертой главе рассматриваются вопросы, связанные с реализацией NCL, работой NCL в структуре САПР, методы интеграции разработанного комплекса с продуктами сторонних разработчиков. Также описаны структуры данных и объектов NCL.
Современные условия производства диктуют жесткие требования к скорости выполнения проектных задач, специально для ускорения процесса генерации раскройных карт в NCL впервые реализована поддержка многопроцессорных систем, что позволило значительно сократить время расчетов на машинах с более чем одним процессором.
Практическая применимость и эффективность результатов диссертационной работы подтверждена внедрением на промышленных предприятиях. Акты внедрения приведены в приложении к диссертации.
Обзор алгоритмов и программ прямоугольно раскроя в единичном производстве
Одна из самых распространенных задач раскроя, встречающихся на практике - задача размещения прямоугольных заготовок на прямоугольных листах фиксированных размеров. Простота формы прямоугольных заготовок облегчает построение допустимых вариантов раскройных карт, поэтому даже при раскрое листов на заготовки сложных форм их часто предварительно заключают в прямоугольники и решают задачу прямоугольного раскроя. При нормировании расхода металла на машиностроительных предприятиях также учитываются прямоугольные размеры заготовок.
В единичном производстве задача прямоугольного раскроя обычно ставится следующим образом. Из листового проката WJXHJ, где і -количество листов, получить заготовки ш различных типоразмеров Wjxhj, в количестве Ilj.
Методы решения этой задачи, как уже говорилось в параграфе 1 этой главы, зависят от типа оборудования, которое предполагается использовать для резки листового материала. В случае прямоугольного раскроя методы делятся на две основные группы: гильотинный раскрой для резки на гильотинных ножницах и прямоугольный раскрой - для остального оборудования.
При решении этой задачи для случая гильотинного раскроя широко пользуются различные эвристические методы и допущения [24 - 29].
Одним из широко распространенных методов является поиск с запретами [30] (Tabu search, TS). Поиск с запретами является метаэвристическим алгоритмом, обеспечивающим направленный итерационный поиск решения путем последовательного улучшения некоторого исходной карты раскроя.
Осуществляемые алгоритмом TS на каждом шаге преобразования — это замена двух заготовок в двух различных слоях гильотинного раскроя друг на друга. При этом оценкой для определения качества замены является величина: A=(Ak+Aj)-(Ako+Ajo) где к и j - номера участвующих в замене слоев заготовок; (A +Aj) - суммарный остаток по этим двум слоям после замены; (Ako+Ajo) - суммарный остаток до замены.
В качестве исходного используется раскрой, получаемый простым эвристическим алгоритмом, построенным по принципу FFD (первый подходящий с упорядочиванием). Возможны замены с участием лишь одной заготовки, когда эта заготовка удаляется из одного слоя и укладывается в другой. Благодаря этому становится возможным как уничтожение старых слоев в результате выбора из них заготовок, так и создание новых.
Поиск с запретами производит перебор возможных вариантов замен и осуществляет выбор лучшего преобразования. При этом учитываются два списка запретов, глобальный и локальный, в которых содержится информация о последних произведенных преобразованиях. Оба списка запретов организованы по принципу FIFO (очереди). Каждый новый элемент добавляется в хвост списка, а головной при этом удаляется.
Основным недостатком этого поиска с запретами является достаточно большое время работы при большом количестве заготовок. Рекурсивный метод [31] (ReCursive Algorithm, RCA) лишен этого недостатка и позволяет находить решение за один проход, хотя при достаточно небольших размерах заготовок по отношению к размеру листа глубина рекурсии становится достаточно большой, что приводит к резкому увеличению времени работы алгоритма. В этом случае рекомендуется использовать упрощенный рекурсивный метод. Метод RCA основан на выделении прямоугольных фрагментов на рулоне материала. При раскрое прямоугольного участка используется его часть, оставшаяся его часть представляет собой совокупность двух прямоугольных фрагментов меньших размеров. Выбор карты раскроя основан на сравнении коэффициентов раскроя.
Использование рекурсивного алгоритма позволяет получать карты раскроя, обеспечивающие эффективное использование материала, с минимальными затратами времени. Это дает возможность использовать данный метод или его упрощенные модификации в качестве составной части более сложных алгоритмов.
Как уже отмечалось выше использование гильотинного раскроя обусловлено применением в производстве гильотинных ножниц. Однако с внедрением новой техники, в частности машин термической резки листового материала, позволило уйти от использования гильотинного раскроя, что позволило снять ряд технологических ограничений с раскройных карт и тем самым значительно повысить коэффициент использования материала (рис 1.3). Не следует все же забывать, что это относится только к машиностроению, в таких областях как деревообрабатывающая промышленность и резка стекла использование гильотинного раскроя остается актуальным.
Среди алгоритмов прямоугольного раскроя следует отметить метод зон (МЗ), предложенный Липовецким А. И. [7]. Это единственный метод, который теоретически гарантирует получение оптимального решения задачи прямоугольного раскроя (при условии, что поворот заготовок разрешен только на 90) за конечное число шагов. Из теории МЗ следует, что хотя бы одно оптимальное решение содержится во множестве 0(N!2) размещений, имеющих специальную структуру, где N - количество размещаемых прямоугольных заготовок. Известные реализации МЗ являются (по схеме организации вычислений) вариантами метода ветвей и границ. Учитывая огромный размер дерева вариантов, который следует обойти, для реализации этого метода пользуются правилами сокращения обхода дерева и экономными методами обхода [32]. Программная реализация этого метода была осуществлена на кафедре Исследования Операций, Государственного Университета, Санкт-Петербург.
Различные подходы к размещению геометрических объектов произвольной формы
Проектирование раскройных карт - наиболее ресурсоемкая операция фигурного раскроя листового материала. От эффективности данной процедуры зависит качество и скорость работы всего алгоритма, поэтому к выбору способа формирования раскройных карт следует относиться с предельным вниманием.
Одним из самых простых методов формирования раскройных карт является метод, основанный на моделировании движений заготовки (рис 2.1).
Этот подход полностью повторяет действия человека при интерактивном проектировании раскройных карт. Первое что делает этот метод — это поиск свободного места на листе, куда можно положить очередную заготовку. Затем с помощью операций параллельного переноса и вращение ищется оптимальное положение заготовки, причем все операции по переносу заготовки выполняются таким образом, чтобы не допустить пересечения с уже уложенными заготовками. Этот подход используется в модуле T-Flex «Раскрой» фирмы «Топ Системы». Основным недостатком такого подхода является зависимость скорости укладки очередной заготовки от количества и сложности геометрии уже уложенных заготовок, как на этапе занесения в свободную область, так и при движении заготовки в этой области.
Предположим, что уже размещено п заготовок, каждая из которых содержит m элементов и укладывается очередная заготовка, содержащая к элементов. Тогда при каждой попытке поместить заготовку на лист и при каждом движении укладываемой заготовки нам необходимо выполнить Р проверок: Причем, если количество движений детали обычно не превышает десятка, то количество попыток возрастает по мере заполнения листа, что приводит к еще большему замедлению работы алгоритма. Например, раскройная карта, показанная на рис. 2.2 рассчитывается несколько часов.
Различные модификации этого метода хорошо зарекомендовали себя при использовании в условиях серийного производства и при укладке большого количества однотипных деталей простой формы. Так как позволяют точно позиционировать детали друг относительно друга и максимально плотно прижимать детали друг к другу, обеспечивая тем самым относительно высокую плотность укладки деталей. К тому же не последним достоинством данного подхода является простота его реализации и удовлетворительная скорость работы для небольшого количества деталей.
Чтобы ликвидировать основные недостатки предыдущего метода -зависимость скорости укладки очередной детали от количества уже уложенных деталей и степени заполнения листа, предлагается использовать следующий подход. Вместо того чтобы хранить все упакованные на лист детали, и каждый раз проверять укладываемую деталь на предмет пересечения с остальными деталями, можно хранить только свободные области листа (рис. 2.3). Свободные области листа на рисунке показаны пунктиром.
Преимущества такого подхода очевидны: - практически нет зависимости от количества уже уложенных деталей; - нет необходимости искать свободные области для укладки очередной детали, так как все они уже найдены; - существует возможность аппроксимации свободных областей для осуществления еще более быстрой укладки деталей. Существенным недостатком этого метода является сложность реализации алгоритма построения/модификации свободных областей листа после укладки очередной детали. В тоже время при использовании этого способа широко применяется аппроксимация свободных областей более простыми геометрическими объектами, что в свою очередь может оказать существенное влияние на эффективность работы алгоритма и снизить коэффициент использования материала в спроектированных раскройных картах. Основываясь на вышесказанном и некоторых зарубежных разработках, в рамках данной диссертационной работы предлагается следующий способ формирования раскройных карт. Сущность предлагаемого метода состоит в том, что векторное изображение заготовки заменяется его растровым аналогом (рис. 2.4) и дальнейшая работа по укладки объекта ведется с его «изображением», а не векторным представлением. Наибольшую трудность при реализации растрового метода размещения заготовок вызывают алгоритмы рисования окружностей, дуг окружностей, отрезков прямых и алгоритмы заливки контура. Больших успехов в реализации этих алгоритмов достиг Брезенхем, его разработки были обобщены и дополнены достижениями других исследователей Вельтмандером П. В. [47]. В рамках данной работы используются модифицированные алгоритмы Брезенхема, а также новый алгоритм заполнения замкнутого контура обладающий высоким быстродействием и надежностью работы. Для хранения растровых данных в памяти компьютера используется массив данных размерностью nxm.
Комбинирование различных алгоритмов укладки плоских геометрических объектов
Для решения этой задачи в NCL был реализован следующий алгоритм модификации задания на раскрой. Во время формирования блоков в задание на раскрой добавляются копии деталей, из которых сформированы блоки, причем эти копии остаются связанными с оригинальными деталями в блоках и укладка целого блока деталей автоматически удаляет из списка деталей подлежащих укладки не только сам блок, но и связанные с ним копии деталей. Если же не удается уложить ни один из блоков или уложить очередной блок, то укладываются оставшиеся копии деталей. Происходит как бы "разбивка" блока на составляющие. Укладка копии детали, соответственно, приводит к удалению ее оригинала из блока.
Такой подход интересен еще и тем, что при переборе нескольких вариантов последовательностей укладки деталей позволяет укладывать блоки и детали их составляющие в произвольной последовательности, то есть сначала может быть уложена часть деталей, а затем блоки.
На сегодняшний день написано множество специализированных алгоритмов автоматического раскроя листового материала. Одни из них предназначены для раскроя исключительно прямоугольных деталей, другие специализируются на укладке деталей более сложной или произвольной формы, некоторые из этих алгоритмов были рассмотрены в первой главе данной диссертационной работы. Основным недостатком всех этих алгоритмов является их узкая специализация. Ниже приведен алгоритм, позволяющий на основе существующих методов раскроя, создать новый алгоритм, который бы наиболее эффективно использовал преимущества специализированных алгоритмов автоматического раскроя.
На первом этапе алгоритма (рис. 3.7) создается как можно большее число различных блоков для различных алгоритмов. Единственное ограничение — один блок может содержать только то количество деталей, которое указано в задании на раскрой. Это означает, что в двух произвольно взятых блоках суммарное количество деталей в общем случае может превышать заданное.
Второй этап - это анализ геометрии получившихся блоков и выбор алгоритмов (нескольких или одного) для раскроя. Под алгоритмом здесь подразумевается один из специализированных алгоритмов раскроя листового материала и его параметры, то есть один и тот же алгоритм с разными параметрами в данной терминологии означает два разных алгоритма.
Третий этап это создание по одному заданию на раскрой для каждого из выбранных алгоритмов. Задания на раскрой создаются из сформированных на первом этапе алгоритма блоков таким образом, чтобы вновь созданные задания совпадали по номенклатуре с исходным заданием на раскрой. Каждому заданию ставится в соответствие специализированный алгоритм с набором параметров, а также, если позволяет алгоритм, порядок укладки блоков.
Четвертый этап - это собственно раскрой с использованием выбранных алгоритмов и последующая доработка получившихся раскройных карт. Доработка — это попытка уложить оставшиеся после раскроя блоки на свободные места в раскройной карте, используя специализированный алгоритм распознавания образов.
Последний этап - выбор наилучшей карты раскроя. В зависимости от пожеланий пользователя это может быть карта с наибольшим коэффициентом раскроя материала, карта с наиболее регулярным раскроем и т. д. В общем случае этот этап может влиять на этап формирования блоков и этап создания заданий на раскрой.
Рассмотренный выше подход к созданию алгоритмов раскроя листового материала (в общем случае этот же метод можно использовать и в трехмерном раскрое), позволяет создавать эффективные алгоритмы раскроя материала, используя любое количество специализированных алгоритмов. При этом подходе используются наиболее сильные стороны алгоритмов, а его недостатки компенсируются использованием других алгоритмов. Границы применимости того или иного алгоритма можно определить опытным путем, создав тестовый набор заданий на раскрой, в который бы входили задания наиболее характерные для отрасли промышленности, в которой предполагается использовать этот алгоритм.
Таким образом, разобранный алгоритм комбинирования различных специализированных алгоритмов раскроя позволяет не только наиболее эффективно использовать каждый алгоритм, но и имеет возможность адаптироваться к условиям производства, в котором ему предстоит работать.
Исследуем возможность распределения заданий по разным алгоритмам, исходя из заданной номенклатуры деталей. Наиболее очевидным является разделение заданий на раскрой на две большие группы -это задания для прямоугольного раскроя и задания для фигурного раскроя. Исследуем возможности автоматического разделения заданий на данные группы. Для этого введем понятие прямоугольности заготовки и задания на раскрой. Прямоугольностью заготовки называется величина равная отношению площади заготовки к площади минимального прямоугольника описанного вокруг заготовки.
В результате данного эксперимента было показано, что алгоритм Капрал становится эффективнее алгоритма фигурного раскроя при значениях коэффициента прямоугольности больше 0.85. Следует, однако, отметить, что данное значение является усредненным и в реальных алгоритмах выбора метода раскроя при значениях коэффициента прямоугольности [0.80, 0.87] рекомендуется запускать алгоритмы как прямоугольного, так и фигурного раскроя. В противном случае возрастает вероятность принятия неправильного решения об использовании того или иного метода.
Создание приложений ориентированных на работу в многопроцессорных системах
Один из наиболее эффективных способов повышения производительности алгоритмов заключается в распараллеливании вычислений в многопроцессорных и параллельных структурах. Наиболее распространенными и доступными на сегодняшний день являются симметричные мультипроцессорные компьютеры (SMP) [98, 100], в том числе и на базе процессоров Pentium. Цель создания SMP-платформ — обеспечение возможности наращивания производительности путем добавления процессоров без изменения приложений.
Процессор Pentium содержит специальные аппаратные средства, поддерживающие SMP-системы. Феномен стандартных SMP-платформ состоит в том, что они широко используются в качестве серверов систем различного масштаба: для рабочих групп, отделов и даже предприятий. Для деловых приложений на основе ОС нового поколения типа Windows NT (Microsoft), NetWare (Novell), UnixWare (Novell), Open Server/MPS (SCO) и других доступен большой выбор высокопроизводительных SMP-платформ на основе Intel-архитектуры традиционных производителей.
Симметричные многопроцессорные SMP-системы могут исполнять любую задачу или поток на любом свободном процессоре. SMP-системы не только более гибки и эффективны, но и более устойчивы к отказам отдельных процессоров. В асимметричных системах при отказе процессора, выделенного под ОС, система немедленно полностью прекращает работу. В SMP-системах в таких ситуациях ОС начинает использовать другие процессоры. SMP-системы обеспечивают также хорошее соотношение цена/производительность, так как добавление процессора не требует приобретения новой компьютерной системы.
Если ОС может исполнять более одной последовательности инструкций в одной задаче, говорят, что она поддерживает многопоточную (с многими нитями управления) архитектуру, эффективно реализующую программным способом параллельную обработку и максимизирующую использование единичного процессора.
Обычно каждой задаче приписывается определенная область адресного пространства, в которой начинается ее исполнение. Каждому потоку выделяются для исполнения ресурсы, как для процесса, но потоки в рамках одной задачи (или процесса) не разделены в адресном пространстве. Каждый поток может использовать данные и файлы других потоков, что облегчает ОС легкое и быстрое переключение потоков (малых процессов).
Примерами ОС, которые поддерживают многопоточную архитектуру, являются Windows NT, ХР и UnixWare 2.0. До недавнего времени большинство традиционных UNIX-систем не поддерживали такую архитектуру; сейчас эта технология начинает проникать в некоторые фирменные ОС на основе UNIX (например, SunSoft Solaris 2.4, HP-UX v. 10).
Потоки могут запускаться и завершаться очень быстро, поскольку нет необходимости заново создавать новую задачу и связанную с ней структуру ОС. Например, в серверах для обслуживания соединения с клиентом создается новый поток. Если не используется многопоточная архитектура, приходится создавать совершенно новый процесс и настраиваться на новое адресное пространство, что ведет к большим накладным расходам и снижает производительность.
Применительно к раскрою листового материала преимущества многопроцессорной среды очевидны, можно запустить одновременно несколько потоков вычислений (рис. 4.12), каждый из которых будет выполняться на отдельном процессоре. В NCL потоки используются для нескольких целей. Во-первых, главный поток обеспечивает возможность вмешательства пользователя в процесс проектирования, а также позволяет просматривать достигнутый на данный момент результат не прерывая хода вычислений. Во-вторых, это потоки создаваемые для каждого запускаемого алгоритма раскроя, то есть в NCL есть возможность одновременно запустить несколько различных алгоритмов, причем время выполнения этих алгоритмов в многопроцессорной среде будет равно времени работы самого медленного алгоритма, в отличие от однопроцессорных систем, где время работы отдельных алгоритмов складывается [рис. 4.13].
Самым сложным моментом при проектировании многопоточных систем является синхронизация обмена данными. В частности, в NCL такая ситуация возникает каждый раз когда требуется обновить данные о лучшем на текущий момент наборе раскройных карт. Так как в любой момент времени эта информация может быть затребована из другого потока или быть изменена параллельным потоком проектирования раскройных карт, то требуется принятие специальных мер для обеспечения целостности информации. Такие точки программы, в которых данные могут быть изменены одновременно из нескольких потоков, называются критическими секциями [102-104].
В NCL доступ к критическим секциям организован средствами операционной системы Windows [92], таким образом, что изменять/читать данные в критической секции может только один поток, если в это же время второй поток пытается получить доступ к критической секции, то его выполнение приостанавливается до тех пор, пока первый поток не выйдет из критической секции. Введение многопоточности позволило легко управлять внешними подключаемыми модулями предназначенными для расширения номенклатуры конфигураций раскраиваемых деталей.
Еще одной отличительной особенностью NCL по сравнению с другими подобными разработками является возможность ее интеграции с различными CAD\CAM системами сторонних разработчиков. В NCL пересмотрено несколько способов взаимодействия и передачи информации между NCL и CAD\CAM системой [рис. 4.14].
Так как система NCL разрабатывалась в рамках САПР "Сириус", то первым интерфейсом обмена данных между NCL и другими подсистемами САПР "Сириус" [рис. 4.15] стал файловый обмен. В структуре "Сириуса" NCL входит в модуль автоматического раскроя и получает задания на раскрой непосредственно из модуля подготовки заданий на раскрой или модуля планирования раскроя. Дальнейший путь раскройных карт полученных в NCL определяется оператором в зависимости от полученного результата. Если результирующая карта раскроя, полученная в NCL, удовлетворяет требованиям, предъявляемым на предприятии, то она передается непосредственно в модуль термической резки, в противном случае существует возможность передать полученный в автоматическом режиме результат в модуль интерактивного раскроя для дальнейшей обработки.
