Все выпуски

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

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

В работе представлена постановка задачи случайной упаковки твёрдых частиц в пространстве в виде минимизации целевой функции, являющейся мерой пересечений подобластей (представляющих частицы и запрещённые области) в R³; при этом желаемые особенности упаковки учитываются дополнительным слагаемым в целевой функции. Предложен новый алгоритм упаковки на основе метода случайного поиска, в котором оценка новой конфигурации частиц производится после каждого перемещения, а сами частицы увеличивают свой размер от начального до заданного по мере устранения пересечений между ними. Данный алгоритм сопоставлен с алгоритмом вязкой суспензии для случая упаковки равновеликих сфер в периодическом кубе; при плотности упаковки φ < 0,55 алгоритм случайного поиска формирует упаковки с меньшим количеством и размером кластеров частиц, в более плотных упаковках различия незначительны. Также показан пример формирования упаковки с особенностью в виде смещения частиц вплотную к твёрдой границе.