Все выпуски

Рассматриваются вопросы, связанные с решением аддитивной задачи последовательного обхода множеств с ограничениями предшествования и функциями стоимости, допускающими зависимость от списка заданий. В качестве базового метода используется широко понимаемое динамическое программирование (ДП), дополняемое в случае задач ощутимой размерности декомпозициями семейства заданий и преобразованием параметров исходной задачи. Возможные применения связаны, в частности, с задачей управления инструментом при фигурной листовой резке деталей на машинах с ЧПУ. В этой задаче важным обстоятельством является учет условий предшествования, имеющих, в частности, следующий смысл: в случае детали с отверстиями резка каждого из внутренних контуров (отвечающих отверстиям) должна предшествовать резке внешнего контура. Сам критерий качества в данной задаче, как правило, является аддитивным. Другой тип ограничений касается избежания термических деформаций деталей. При использовании подхода с применением штрафов за нарушение условий, связанных с эффективным отводом тепла при выполнении врезки, возникают функции стоимости, допускающие зависимость от списка заданий, выполненных на текущий момент времени. Заметим, что в другой прикладной задаче, а именно в задаче о демонтаже радиационно опасных объектов, возникают функции стоимости с зависимостью от списка заданий, не выполненных на данный момент (а, следовательно, касающихся недемонтированных объектов). В итоге мы приходим к очень общей задаче с ограничениями предшествования и функциями стоимости с зависимостью от списка заданий. Применяемая в случае ощутимой размерности декомпозиция с последующей реализацией ДП требует, с одной стороны, разработки методов кластеризации, а, с другой, построения адекватной конструкции распределения глобальных условий предшествования по кластерам. В теоретической части работы обсуждается случай двух кластеров, который позволяет охватить единой схемой целый ряд практически интересных задач диапазонного (в смысле размерности) типа. Указан алгоритм построения композиционного решения, включающий этап обучения кластеризации на основе жадного алгоритма. Данный «композиционный» алгоритм реализован на ПЭВМ; проведен вычислительный эксперимент.

Рассматривается минимаксная задача маршрутизации с элементами декомпозиции. В простейшем случае предполагается, что все множество заданий разбито в сумму двух подмножеств (кластеров), причем выполнение заданий из второго подмножества может быть начато только после завершения всех заданий из первого. Для упомянутой двухкластерной задачи построен алгоритм для нахождения оптимального композиционного решения, включающего маршрут (перестановку индексов заданий) и точку старта, базирующийся на использовании широко понимаемого динамического программирования. На основе данного подхода построен также алгоритм для решения задачи маршрутизации в случае произвольного упорядоченного конечного набора кластеров; алгоритм реализован на ПЭВМ, проведен вычислительный эксперимент. Возможные применения могут быть связаны с некоторыми логистическими задачами в малой авиации, когда требуется обеспечить посещение многих пунктов одним транспортным средством (самолет, вертолет) с ограниченной дальностью беспосадочного полета.

В работе исследуется алгоритм решения уравнения кристаллического фазового поля (Phase Field Crystal - PFC) в гиперболической постановке. Уравнение описывает фазовые превращения из метастабильного или неустойчивого состояния на масштабе атомной плотности и является дифференциальным уравнением шестого порядка по пространству и второго порядка по времени. Алгоритм основан на методе изогеометрического анализа (IGA) и реализован посредством библиотеки PetIGA. Полученный программный код допускает распараллеливание расчетов, что существенно ускоряет процесс решения задачи. Дана оценка эффективности используемых инструментов при проведении расчетов на высокопроизводительных вычислительных кластерах. Проведен анализ эффективности исследуемого алгоритма при работе с гетерогенными вычислительными системами.

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