Two-Level Optimization of Task Distribution into Batches and Scheduling Their Execution in Pipeline Systems with Limited Buffers

Currently, existing mathematical models and algorithms provide optimization of schedules for the execution of single tasks or fixed task packages on devices of conveyor systems containing buffers of limited sizes. These models and algorithms do not allow searching for optimal solutions for grouping the same type of tasks into packages and by sequence of packages to implement operations with them on devices of conveyor systems. Increasing the efficiency of using the resources of conveyor systems is achieved by optimizing solutions for grouping the same type of tasks into packages and by sequences of packages for performing operations with them. The solution to this problem is carried out in the work by using an approach that implements two-level optimization, which allows you to form a hierarchy of subtasks for finding effective solutions. The involvement of the mentioned approach involves the development of mathematical models of hierarchical games that allow identifying effective solutions of the type under consideration. Two mathematical models of hierarchical games have been constructed, the use of which makes it possible to optimize package compositions at the upper level by the leading player and optimize package execution schedules in pipeline systems at the lower level by the slave player. The method of determining the optimal solutions for each of the players provides for the order of moves set in the game and the exchange of solutions between them during the game. The first mathematical model of the hierarchical game implements the definition of effective solutions when taking into account the downtime of processing devices in the process of implementing operations with packages. The second mathematical model of the game implements the definition of effective solutions, taking into account the total waiting time for buffers to place tasks in them, with which operations on previous devices were completed. To do this, expressions have been formed that allow you to determine buffer downtime while waiting for tasks from packages to be ready for placement based on the time characteristics of the processes of performing operations with them on the devices of the systems under consideration. The algorithm for determining optimal solutions according to the order of operations with packages at the lower level in each of the hierarchical games is based on a developed mathematical model of the processes of implementing actions with packages in these systems and the corresponding modeling algorithm. The implementation of the optimization approach under consideration allowed us to obtain results that showed that the use of buffers can significantly increase the efficiency of the processes of performing operations with packets on the devices of the systems under consideration; increasing the size of intermediate buffers allows us to increase the efficiency of these processes to a greater extent with significant heterogeneities in the values of time parameters characterizing them; using the first model of a hierarchical game allows us to achieve a greater increase in the efficiency of processes in comparison with the second model.