Все выпуски

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

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.

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

The problem of coordinating the semantics of data presented within different models has remained relevant for a significant period of time. First of all, this is related to the convenience of work for users who are accustomed to certain tools, for example, spreadsheets. The data prepared in these environments needs to be loaded into a centralized database, which makes it possible to get rid of duplication and inconsistency of data. An obstacle to this path is the problem of data reconciliation. Editing data directly in the database is a difficult task for non-programmer users. The traditional way to solve this problem is to develop special applications that have limited functionality. This paper proposes a technology that allows editing data in a database using spreadsheets, making their rich functionality available. The main difference from similar approaches is the use of the “Transformation” model, which makes the presentation of data convenient for human perception. Since the “Transformation” data model differs significantly from the relational model, there is a need to reconcile data between the database and spreadsheets. To solve similar problems, L.A. Kalinichenko proposed a method of commutative transformations in databases. In this paper, this technique, with some modifications, is used in algorithms for transferring data from a database to “Transformation” and back. The article presents an overview of works on the problem of data matching in various sources, a description of the data model “Transformation”, including: a description of the table schema, conditions for the existence of a table instance and data editing operations. The paper describes an algorithm for loading data into a table from a database and the algorithm for transforming data in a database in accordance with changes in the table, defines the conditions for the commutativity of the transformations, and presents a proof of the correctness of the transformations.