Программный модуль для построения оптимального графика переработки сырья
Authors: Баландин Д.В. , Кузенков О.А. , Вильданов В.К. 
Published: December 2024

Одной из областей применения программных средств является организация технологического процесса, составление графика работы оборудования. Значимость проблемы оптимизации технологического режима объясняется тем, что часто изменение графика не требует привлечения дополнительных ресурсов, а отдача от выбора оптимальной последовательности стандартных операций порой сравнима с выигрышем от модернизации оборудования. Цель настоящего исследования состоит в разработке программного модуля для составления оптимального графика переработки сахарной свеклы. В основе создаваемого программного модуля лежит метод оптимизации, который можно рассматривать как модифицированный метод ветвей и границ или модифицированный метод динамического программирования. Построенный алгоритм на основе идей метода ветвей и границ позволяет существенно снизить необходимое число вычислений и сравнений. Программный модуль был реализован на языке программирования Python 3. Несмотря на невысокое быстродействие интерпретируемых языков, данный выбор позволяет, с одной стороны, ускорить разработку прототипа, а, с другой стороны, допускает в дальнейшем использование модулей для быстрой обработки массивов. Первая подпрограмма реализует инициализацию словаря, в котором ключу, содержащему сочетание из двух элементов множества номеров технологических этапов, соответствует перестановка, приводящая к максимальному выходу и значение этого выхода. В дальнейшем структура словаря не меняется, лишь увеличивается количество элементов в сочетании и соответствующей перестановке. Вторая подпрограмма для данного сочетания (представленного в виде упорядоченного кортежа значений) осуществляет поиск перестановки, обеспечивающей максимальный выход продукта. Благодаря структуре словаря, поиск реализован очень легко. Для сравнения эффективности работы созданного программного обеспечения был реализован также "жадный" алгоритм. Его стратегия состоит в том, что на каждом технологическом этапе обрабатывается сорт свеклы, обеспечивающий наибольший выход продукта на данном этапе. Выход сахара, получаемый "жадным" алгоритмом меньше либо равен максимальному выходу, однако, показано, что "жадная" стратегия обеспечивает большой выход лишь на первых этапах технологической обработки, и теряет на последних этапах по сравнению с реализованным оптимальным алгоритмом.
One of the areas of application of software is the organization of the technological process, the scheduling of the equipment. The importance of the problem of optimization of the technological regime is explained by the fact that often a change in the schedule does not require the involvement of additional resources, and the return on the choice of the optimal sequence of standard operations is sometimes comparable to the gain from the modernization of equipment. The purpose of this study is to develop a software module for drawing up an optimal sugar beet processing schedule. The created software module is based on the optimization method, which can be considered as a modified branch-and-bound method or a modified dynamic programming method. The constructed algorithm based on the ideas of the branch and bound method can significantly reduce the required number of calculations and comparisons. The program module was implemented in the Python 3 programming language. Despite the low speed of interpreted languages, this choice allows, on the one hand, to speed up the development of a prototype, and, on the other hand, allows further use of modules for fast processing of arrays. The first subroutine implements the initialization of the dictionary, in which a permutation leading to the maximum output and the value of this output corresponds to the key containing a combination of two elements of the set of numbers of technological stages. Due to the structure of the dictionary, the search is very easy. To compare the efficiency of the created software, a greedy algorithm was also implemented. His strategy is that at each technological stage, the beet variety is processed that provides the highest product yield at this stage. The sugar yield obtained by the "greedy" algorithm is less than or equal to the maximum yield, however, it is shown that the "greedy" strategy provides a large yield only at the first stages of technological processing, and loses at the last stages in comparison with the implemented optimal algorithm