The paper considers the problem of optimizing the sequence of printing job execution in a computer-integrated information system of a printing enterprise. The relevance of the study is conditioned the need to improve the efficiency of production processes under conditions of increasing order complexity, diversity of materials, and frequent changes in technological parameters. The main objective of the work is to develop and investigate an algorithm for optimizing the job execution sequence based on the branch and bound method, taking into account the costs of equipment setup and reconfiguration. A mathematical model of the problem is formulated, in which the sequence of job execution is represented as a route over the set of admissible permutations, while transition costs between jobs are described using a cost matrix. The use of a cost matrix reduction procedure is proposed to obtain a lower bound estimate of the objective function, which enables the implementation of an efficient pruning mechanism for eliminating non-optimal solutions during the search process.
The developed algorithm involves constructing a decision tree with successive branching of the set of admissible solutions and applying a penalty function to select the most promising transitions between jobs. The conducted experimental study confirmed the effectiveness of the proposed approach: a reduction in total setup costs of up to 39.5% compared to a non-optimized sequence was achieved, along with a decrease in the overall production cycle time.
The obtained dependencies demonstrate that as the number of jobs increases, the branch and bound method provides signifi - better scalability compared to exhaustive search, making it suitable for practical implementation in information systems of printing enterprises. The results obtained can be used to improve production planning efficiency, reduce equipment downtime, and optimize resource utilization.
- Metaheuristics for the online printing shop scheduling problem / W. T. Lunardi et al. European Journal of Operational Research. 2021. Vol. 2, no. 293. P. 419–441. URL: https://doi.org/ 10.1016/j.ejor.2020.12.021.
- Mixed Integer linear programming and constraint programming models for the online printing shop scheduling problem / W. T. Lunardi et al. Computers & Operations Research. 2020. Vol. 123. P. 105020. URL: https://doi.org/10.1016/j.cor.2020.105020.
- A job sequence optimization approach for parallel machine scheduling problem in printing manufacturing systems / H. Li et al. IEEE Access. 2024. P. 1. URL: https://doi.org/10.1109/ access.2024.3396455.
- Job Shop Scheduling Problem Optimization by Means of Graph-Based Algorithm / J. Stastny et al. Applied Sciences. 2021. Vol. 11, no. 4. P. 1921. URL: https://doi.org/10.3390/ app11041921.
- Mahdavi Mazdeh M., Sarhadi M., Hindi K. S. A branch-and-bound algorithm for single- machine scheduling with batch delivery and job release times. Computers & Operations Research. 2008. Vol. 35, no. 4. P. 1099–1111. URL: https://doi.org/10.1016/j.cor.2006.07.006.
- Abranchandboundalgorithmforaparallelmachineschedulingproblemingreenmanufacturing industry considering time cost and power consumption / Y. Xiao et al. Journal of Cleaner Production. 2021. Vol. 320. P. 128867. URL: https://doi.org/10.1016/j.jclepro.2021.128867.
- Matsii O. B. Review of routing problems reducible to the traveling salesman problem. Open Information and Computer Integrated Technologies. 2020. No. 86. pp. 152–159. URL: https:// doi.org/10.32620/oikit.2019.86.11.
- Stoliarova A. V., Barau K. Analysis of the efficiency of algorithms for solving viscoelasticity problems. Visnyk of Zaporizhzhya National University. Physical and Mathematical Sciences. 2024. No. 1. pp. 84–91. URL: https://doi.org/10.26661/2786-6254-2024-1-10.
- Shapovalova S., Yaremenko D. Application of MATLAB in studying genetic algorithms: solving the traveling salesman problem. In: The Results of Scientific Mind’s Development: 2019 / ed. N. Tupko. 2019. URL: https://doi.org/10.36074/22.12.2019.v1.23.