Все выпуски

В статье рассматривается экстремальная задача маршрутизации с ограничениями. В общей формулировке предполагается, что объектами посещения являются любые непустые конечные множества — мегаполисы. Основной прикладной задачей, рассматриваемой в данном исследовании, является задача оптимизации траектории движения инструмента для станков листовой резки с ЧПУ, известная как проблема пути резания. Эта проблема возникает на этапе разработки управляющих программ для станков с ЧПУ. Возможны и другие приложения. В частности, результаты исследования могут быть использованы в задаче минимизация дозы облучения при демонтаже системы радиационно-опасных элементов после аварий на АЭС и в транспортных проблемах. В качестве ограничений исследуются ограничения предшествования. Они могут быть использованы для уменьшения вычислительной сложности. В качестве основного метода исследования использовалось широко понимаемое динамическое программирование. Предлагаемая реализация метода учитывает ограничения предшествования и зависимость целевых функций от списка задач. Последняя относится к классу очень сложных состояний, которые определяют допустимость маршрута на каждом шаге маршрутизации, в зависимости от уже выполненных или, наоборот, еще не завершенных задач. Применительно к задаче резки зависимость целевой функции от списка задач позволяет уменьшать термические деформации материала при резке. В работе математическая формализация экстремальной задачи маршрутизации с дополнительными ограничениями, описание метода и полученный с его помощью точный алгоритм. Оптимизации подлежат порядок выполнения задач, конкретная траектория процесса, и его начальная точка.

The paper deals with an extremal routing problem with constraints. In the general formulation, it is assumed that the objects of visiting are any non-empty finite sets — megalopolises. The main applied problem considered in this study is the tool path optimization problem for CNC sheet-cutting machines, known as the Cutting Path Problem. This problem arises at the stage of developing control programs for CNC machines. Other applications are also possible. In particular, the results obtained in the chapter can be used in the problem of minimizing the radiation dose when dismantling a system of radiation-hazardous elements after accidents at nuclear power plants and in transport problems. Among tasks constraints, the precedence constraints are investigated. These constraints can be used to reduce computational complexity. As the main method, the study used broadly understood dynamic programming. The offered realization of the method takes into account the precedence constraints and the dependence of the objective functions on the task list. This dependence belongs to the class of very complex conditions that determine the route admissibility at each routing step, depending on the tasks already completed or, on the contrary, not yet completed. As applied to the Cutting Path Problem, the dependence of the objective function on the task list makes it possible to reduce thermal deformations of the material during cutting. The chapter provides a mathematical formalization of an extremal routing problem with additional constraints, a description of the method, and the exact algorithm obtained with its help. The order of task execution, the specific trajectory of the process, and the starting point are optimized.

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

We consider a routing problem with constraints and complicated cost functions. The visited objects are assumed to be clusters, or megalopolises (nonempty finite sets), and the visit to each of them entails certain tasks, which we call interior jobs. The order of visits is subject to precedence constraints. The costs of movements depend on the set of pending tasks (not yet complete at the time of the movement), which is also referred to as “sequence dependence”, “position dependence”, and “state dependence”. Such a dependence arises, in particular, in routing problems concerning emergencies at nuclear power plants, similar to the Chernobyl and Fukushima Daiichi incidents. For example, one could consider a disaster recovery problem concerned with sequential dismantlement of radiation sources; in this case, the crew conducting the dismantlement is exposed to radiation from the sources that have not yet been dealt with. This gives rise to dependence on pending tasks in the cost functions that measure the crew's radiation exposure. The latter dependence reflects the “shutdown” operations for the corresponding radiation sources. This paper sets forth an approach to a parallel solution for this problem, which was implemented and run on the URAN supercomputer.

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

We consider a problem of sequential traversal of megalopolises (nonempty finite sets) with travel cost functions depending on the set of pending tasks and precedence constraints. Its formulation is aimed at engineering problems in fission power generation connected with minimizing the exposure of staff to radiation and in machine engineering (routing of a CNC sheet cutting machine's tool). This discrete optimization problem is assumed to be sufficiently large-scale to necessitate the use of heuristics. We consider a procedure of local improvement for heuristics through a successive application of optimizing multi-inserts-finite disjoint sets of inserts. Each insert is assumed to be optimized by means of a broadly understood dynamic programming procedure. We show that in an “additive” routing problem of this kind (with precedence constraints and complex travel cost functions) the result's improvements are also aggregated additively. The proposed construction admits a parallel implementation for multiprocessor systems; in this case, the inserts are distributed to computational nodes and formed in an independent way.

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

The article deals with the problem of admissible routing for a system of cycles each of which contains exterior permutation and works connected with megalopolises (non-empty finite sets) visiting. In the initial setting, a resource constraint is given; this constraint should be fulfilled for every cycle under permutation. The solvability conditions in this problem are connected with the extremum of the auxiliary bottleneck routing problem without above-mentioned constraint, in which the apparatus of widely understood dynamic programming (DP) is used. A particular case of the setting is the known bottleneck courier problem which can be used (in particular) for routing a vehicle (airplane or helicopter) aiming to realize the given shipping system with a limited fuel reserve on each flight. An algorithm implemented on a personal computer is constructed.

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

The “additive” problem of sequentially visiting megalopolises (nonempty finite sets) is considered; some tasks are executed as the megalopolises are visited. Permutations and operations are evaluated by cost functions that admit a dependence on the list of tasks. There are restrictions of different types, which include precedence conditions used in the “positive direction” (to reduce the complexity of calculations). In addition, this conception involves dynamical restrictions that are formed in the process of task execution. This conception is oriented to engineering applications associated with sheet cutting on CNC machines. An approach to constructing optimal solutions based on a nonstandard version of dynamic programming (DP) is investigated. This approach takes into account restrictions of different types, including dynamic constraints which naturally arise in sheet cutting applications (in particular, it takes into account heat tolerances related to diffusion of heat in the vicinities of tie-in points). In this regard, a combination of “direct” interdictions of movements and cutting and a system of penalties is allowed; in the latter case, cost functions with a dependence on the list of tasks arise. The variant of DP that is used allows one to optimize the selection of a starting point, the route, which is identified with a permutation of the indexes, and the trajectory corresponding to the above-mentioned route. An economical variant of DP is used at the stage of construction of the Bellman function. This conception allows avoiding calculation of the whole array of values of this function; instead, only the system of its layers is defined (in the case of using the precedence conditions, which are typical of the problem of sheet cutting, this conception results in a considerable reduction of calculation costs). An optimal DP-based algorithm is constructed and realized on PC, and the results of the computational experiment are presented.

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

The problem of sequential megalopolis circuit with constraints in the form of preceding conditions and (interior) works realized in the megalopolises is considered. The singularity is a dependence of costs of exterior permutations and interior works on the task list. The iteration method with elements of decompositions of the joint solution defined as a pair «route-trace» is constructed.

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

Основное внимание в работе уделяется построению оптимизирующих вставок в усложненных условиях: требуется редуцировать фрагмент условий предшествования и трансформировать соответствующие функции стоимости; в последнем случае важно сохранить в надлежащей форме зависимость от списка заданий. Оба упомянутых обстоятельства учитываются при построении процедуры, имеющей смысл алгоритма на функциональном уровне.

The problem of sequential circuit of megalopolises with precedence conditions and cost functions that permit a dependence on tasks list is considered. Such problems can arise, in particular, in atomic energetic while investigating the questions connected with lowering of workers irradiation under permutations in radiative fields for realization of services connected with division of radiating elements. Another application of the developed methods is connected with important engineering problem of routing the instrument movements under the leaf cutting on numerically controlled machines. This problem has sufficiently large dimensionality and many precedence conditions: if a detail has not only exterior but at least one interior contours (the simplest example is a washer) then the interior contours must be cut before the cutting of exterior contour (finite sets located near corresponding contours are used as megalopolises). In this case the possible dependence of cost functions on tasks list can reflect various technological conditions. We note that perceptible dimensionality characterized by all contours in total leads to necessity of heuristics employment. Therefore, questions concerning at least local improvement of solutions appear sufficiently important for the investigation.

The basic attention in the article is devoted to the construction of optimizing insertions in complicated conditions: it is required to reduce the fragment of precedence conditions and to transform the corresponding cost functions; in the last case, it is important to preserve the dependence on tasks list. Both above-mentioned moments are taken into account under the procedure construction having the sense of algorithm on functional level.

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

A complicated variant of the “bottleneck problem” is considered, namely: the problem of sequential visiting of megalopolises with preceding constraints. It is supposed that costs functions and “current” constraints with respect to displacements selection depend on the tasks list which is not completed at the moment. The variant of widely understood dynamic programming is proposed, it doesn't foresee (with preceding conditions) construction of the whole array of the Bellman function values; the special layers of this function realizing in its totality the partial array of its values are constructed (it helps to decrease the calculation complexity). An algorithm of the problem value (global extremum) calculation is proposed, the computer realization of which implies the existence of only one layer of the Bellman function in a memory of computer; the obtained value may be used for the heuristics testing. The optimal algorithm of “complete” solving of the route problem is constructed, within which all layers of the Bellman function are used at the route and trace constructing.

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

The route problem with precedence conditions and cost functions depending on the jobs list is considered; these singularities correspond to engineering applications. In particular, the above-mentioned singularities exist in statements of some problems arising in nuclear energetics and in machines with numerical control. Problems involved in sequentially circuiting megalopolises and in carrying out some (interior) work during these circuits are investigated. A procedure for local improvement of heuristic solutions for problems of perceptible dimension is proposed; this procedure exploits insertions on the dynamic programming base. Dynamic programming is realized in the form of a variant that does not provide for construction of a “full” array of values of the Bellman function. The search for localization of an insertion involves restricting to the variant of the Bellman procedure that realizes the extremum of the (local) criterion without constructing a corresponding solution in the form of a route-track pair. A more complete and more cost-intensive (in the sense of memory resources) procedure including determination of the above-mentioned (local optimal) solution is planned after the choice of the insertion localization.