Все выпуски

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

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

The article is concerned with the procedure of insertion of optimizable fragments of route solutions into the global solutions of the «big» problem defined by heuristic algorithms. Setting of the route problem takes into account some singularities of the engineering problem about the sequential cutting of details each having one exterior and probably several interior contours. The latter ones must be subjected to cutting previously in comparison with the exterior contour, which leads to a great number of given preceding conditions. These conditions are actively used to decrease the computational complexity. Nevertheless, the problem dimensionality remains sufficiently large that does not permit to use “global’’ dynamic programming and forces heuristic algorithms to be used (the problem under investigation is a hard-solvable problem in the traditional sense). Therefore, it is interesting to develop the methods for correction of solutions based on the above-mentioned algorithms. In the present investigation, such correction is realized by the replacement of fragments (of the above-mentioned solutions) having a moderate dimensionality by optimal “blocks’’ constructed by dynamic programming with local preceding conditions which are compatible with the constraints of the initial “big’’ problem. The proposed replacement does not deteriorate, but, in typical cases, improves the quality of the initial heuristic solution. This is verified by the computing experiment on multi-core computer.

The proposed algorithm is realized in the iterated regime: the solution (in the form of “route-trace’’) obtained after the first insertion on the basis of dynamic programming is taken as an initial solution for which the insertion is constructed again. In addition, the beginning of the new insertion is chosen randomly in the bounds defined by the possibilities of formation of a sliding “window’’ of the appreciable dimensionality which is in fact sufficient for the employment of the economical version of dynamic programming. Further, the procedure is repeated. The operation of the iterated algorithm is illustrated by solution of model problems including the versions with sufficiently dense “packing’’ of parts on a sheet, which is typical for the engineering production.

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

The paper presents a problem statement for random hard particles packing as minimization of an objective function that is the measure of overlapping of R³ subdomains representing particles and forbidden zones, with desired pack characteristics being accounted for by an additional summand in the objective function. A new algorithm based on the random search approach is proposed; it assesses a new particles configuration after each movement, and particles grow from an initial to full size as overlaps being removed. This algorithm is matched with the viscous suspension algorithm for the case of packing equal-sized spheres in a periodic cube. For packing fractions φ < 0,55 the random search algorithm yields packs with fewer and smaller particle clusters than the viscous suspension one, in denser packs differences are insignificant. An example of creating a pack with the feature that particles are shifted closely to the solid boundary is shown as well.