A branch and bound algorithm for the optimization of batch scheduling in pipeline systems
Abstract
Introduction: The optimization of batch scheduling ensures efficiency in production and computational processes. Modern methods of scheduling optimization are characterized by limitations on the dimensionality of tasks or the impossibility of obtaining solutions that approach the globally optimal ones. Purpose: To develop a branch and bound algorithm for the optimization of batch scheduling in pipeline systems. Results: We obtain a mathematical model of multistage processes that allows to identifythe point in timewhenbatch jobs start running in the appropriate positions in the sequences of the implementation of actions with them on the devices of pipeline systems. We present the criterion for optimizing solutions thatcorresponds to the point intime when the tasks included into the batch stop running.We formulate a method of partitioning sets of solutions into their subsets (branch tree vertices). This methodinvolves adding a package of different types oneat a time to the sequence of implementation of actions with them from the sets not included into them. We develop a method for constructing solutions according to the order of execution on the devices of the packages which are included in the formed subsets. For these subsets we calculate the values of the criterionused when updating the upper estimates. We synthesize a method for determining the values of the lower estimates of the criterion for sets of solutions corresponding to the vertices of the tree obtained as a result of branching. Abranch and boundalgorithm is also developed. Practicalrelevance:The studies that are conducted with the use of the software implementation of the algorithm have shown that it allows up to 35% decrease in the time for batch jobs execution as compared to the solutions without optimization. With a small number of task types, the algorithm allows one to get a solution which approximates the globally optimal one. With the increase in the number of task types, the accuracy of approximation of the solutions to the globally optimal ones is 0.9–0.95.
