This study proposes a novel approach to optimizing individual work schedules for book digitization using mixed-integer programming (MIP). By leveraging the power of MIP solvers, we aimed to minimize the overall digitization time while considering various constraints and process dependencies. The book digitization process involves three key steps: cutting, scanning, and binding. Each step has specific requirements and limitations such as the number of pages that can be processed simultaneously and potential bottlenecks. To address these complexities, we formulate the problem as a one-machine job shop scheduling problem with additional constraints to capture the unique characteristics of book digitization. We conducted a series of experiments to evaluate the performance of our proposed approach. By comparing the optimized schedules with the baseline approach, we demonstrated significant reductions in the overall processing time. In addition, we analyzed the impact of different weighting schemes on the optimization results, highlighting the importance of identifying and prioritizing critical processes. Our findings suggest that MIP-based optimization can be a valuable tool for improving the efficiency of individual work schedules, even in seemingly simple tasks, such as book digitization. By carefully considering specific constraints and objectives, we can save time and leverage resources by carefully considering specific constraints and objectives.
References
[1]
Zhang, J., Liu, C., Li, X., Zhen, H., Yuan, M., Li, Y., et al. (2023) A Survey for Solving Mixed Integer Programming via Machine Learning. Neurocomputing, 519, 205-217. https://doi.org/10.1016/j.neucom.2022.11.024
[2]
Bixby, R.E. (2012) A Brief History of Linear and Mixed-Integer Programming Computation. In: Documenta Mathematica Series, EMS Press, 107-121. https://doi.org/10.4171/dms/6/16
[3]
Bengio, Y., Lodi, A. and Prouvost, A. (2021) Machine Learning for Combinatorial Optimization: A Methodological Tour D’horizon. European Journal of Operational Research, 290, 405-421. https://doi.org/10.1016/j.ejor.2020.07.063
[4]
Nair, V., Bartunov, S., Gimeno, F., Von Glehn, I., Lichocki, P., Lobov, I. and Zwols, Y. (2020) Solving Mixed Integer Programs Using Neural Networks. https://doi.org/10.48550/arXiv.2012.13349
[5]
Solnon, C., Cung, V.D., Nguyen, A. and Artigues, C. (2008) The Car Sequencing Problem: Overview of State-of-the-Art Methods and Industrial Case-Study of the ROADEF’2005 Challenge Problem. European Journal of Operational Research, 191, 912-927. https://doi.org/10.1016/j.ejor.2007.04.033
[6]
Morales-Espana, G., Latorre, J.M. and Ramos, A. (2013) Tight and Compact MILP Formulation for the Thermal Unit Commitment Problem. IEEE Transactions on Power Systems, 28, 4897-4908. https://doi.org/10.1109/tpwrs.2013.2251373
[7]
Koch, T., Berthold, T., Pedersen, J. and Vanaret, C. (2022) Progress in Mathematical Programming Solvers from 2001 to 2020. EURO Journal on Computational Optimization, 10, Article 100031. https://doi.org/10.1016/j.ejco.2022.100031
[8]
González, M., López-Espín, J.J. and Aparicio, J. (2020) A Parallel Algorithm for Matheuristics: A Comparison of Optimization Solvers. Electronics, 9, Article 1541. https://doi.org/10.3390/electronics9091541
[9]
Turner, M., Chmiela, A., Koch, T. and Winkler, M. (2023) PySCIPOpt-ML: Embedding Trained Machine Learning Models into Mixed-Integer Programs. https://doi.org/10.48550/arXiv.2312.08074
[10]
Ahmadi Teshnizi, A., Gao, W. and Udell, M. (2023) Optimus: Optimization Modeling Using MIP Solvers and Large Language Models.
[11]
Wang, T., Yu, W.Y., She, R., Yang, W., Chen, T. and Zhang, J. (2024) Leveraging Large Language Models for Solving Rare MIP Challenges. https://doi.org/10.48550/arXiv.2409.04464
[12]
Brech, C., Ernst, A. and Kolisch, R. (2019) Scheduling Medical Residents’ Training at University Hospitals. European Journal of Operational Research, 274, 253-266. https://doi.org/10.1016/j.ejor.2018.04.003
[13]
Vermuyten, H., Namorado Rosa, J., Marques, I., Beliën, J. and Barbosa-Póvoa, A. (2018) Integrated Staff Scheduling at a Medical Emergency Service: An Optimisation Approach. Expert Systems with Applications, 112, 62-76. https://doi.org/10.1016/j.eswa.2018.06.017
[14]
Luo, L., Liu, X., Cui, X., Cheng, Y., Yu, X., Li, Y., et al. (2020) Applying Queuing Theory and Mixed Integer Programming to Blood Center Nursing Schedules of a Large Hospital in China. Computational and Mathematical Methods in Medicine, 2020, 1-7. https://doi.org/10.1155/2020/9373942
[15]
Hewitt, M., Chacosky, A., Grasman, S.E. and Thomas, B.W. (2015) Integer Programming Techniques for Solving Non-Linear Workforce Planning Models with Learning. European Journal of Operational Research, 242, 942-950. https://doi.org/10.1016/j.ejor.2014.10.060
[16]
Wang, H., Alidaee, B., Ortiz, J. and Wang, W. (2020) The Multi-Skilled Multi-Period Workforce Assignment Problem. International Journal of Production Research, 59, 5477-5494. https://doi.org/10.1080/00207543.2020.1783009
[17]
Vahedi-Nouri, B., Tavakkoli-Moghaddam, R., Hanzálek, Z. and Dolgui, A. (2022) Workforce Planning and Production Scheduling in a Reconfigurable Manufacturing System Facing the COVID-19 Pandemic. Journal of Manufacturing Systems, 63, 563-574. https://doi.org/10.1016/j.jmsy.2022.04.018
[18]
Köseli, İ., Soysal, M., Çimen, M. and Sel, Ç. (2023) Optimizing Food Logistics through a Stochastic Inventory Routing Problem under Energy, Waste and Workforce Concerns. Journal of Cleaner Production, 389, Article 136094. https://doi.org/10.1016/j.jclepro.2023.136094
[19]
Laesanklang, W., Landa-Silva, D. and Arturo Castillo Salazar, J. (2015) Mixed Integer Programming with Decomposition to Solve a Workforce Scheduling and Routing Problem. Proceedings of the International Conference on Operations Research and Enterprise Systems, Lisbon, 10-12 January 2015, 283-293. https://doi.org/10.5220/0005223602830293
[20]
Moussavi, S.E., Mahdjoub, M. and Grunder, O. (2019) A Matheuristic Approach to the Integration of Worker Assignment and Vehicle Routing Problems: Application to Home Healthcare Scheduling. Expert Systems with Applications, 125, 317-332. https://doi.org/10.1016/j.eswa.2019.02.009
[21]
IDC (2024) Tablet Shipments Show Signs of Recovery in Q1 2024. https://www.idc.com/getdoc.jsp?containerId=prUS52105224
[22]
Nagaraj, A. and Reimers, I. (2023) Digitization and the Market for Physical Works: Evidence from the Google Books Project. American Economic Journal: Economic Policy, 15, 428-458. https://doi.org/10.1257/pol.20210702
[23]
Library Vision (2022) How to Scan Old Books: Digitizing Used Books into a PDF. https://www.libraryvision.org/digitization/how-to-scan-old-books/
[24]
Fortune Business Insights (2024) Document Scanner Market Size, Share Industry Analysis 2032. https://www.fortunebusinessinsights.com/document-scanner-market-106606
[25]
The Business Research Company (2024) Scanner Market Report 2024—Scanner Market Analysis and Forecast 2033. https://www.thebusinessresearchcompany.com/report/scanner-global-market-report
[26]
Takahashi, K. (2014) An Analysis on Work Efficiency of Personal Book Scanning Process with Integer Programming Solver. Scheduling Symposium 2014, Toyama, 29-30 September 2014, 171-176.
[27]
Gurobi Optimization (2024) Gurobi Optimizer: The World’s Fastest Solver. https://www.gurobi.com/solutions/gurobi-optimizer/
[28]
Johnson, S.M. (1954) Optimal Two and Three-Stage Production Schedules with Setup Times Included. Naval Research Logistics Quarterly, 1, 61-68. https://doi.org/10.1002/nav.3800010110
[29]
Potts, C.N. and Van Wassenhove, L.N. (1982) A Decomposition Algorithm for the Single Machine Total Tardiness Problem. Operations Research Letters, 1, 177-181. https://doi.org/10.1016/0167-6377(82)90035-9
[30]
Kubo, M., Pedro, J., Muramatsu, M. and Rais, A. (2012) Mathematical Optimization: Solving Problems Using Gurobi and Python. Kindai Kagaku Sha.
