Abstract
Quantum computing has emerged in recent years as an alternative to classical computing, which could improve the latter in solving some types of problems. One of the quantum programming models, Adiabatic Quantum Computing, has been successfully used to solve problems such as graph partitioning, traffic routing and task scheduling. Specifically, in this paper we focus on the scheduling on unrelated parallel machines problem. It is a workload-balancing problem where the processing time of any procedure executed on any of the available processing elements is known. Here, the problem is expressed as Quadratic Unconstrained Binary Optimisation, which can be subsequently solved using quantum annealers. The quantum nonlinear programming framework discussed in this work consists of three steps: quadratic approximation of cost function, binary representation of parameter space, and solving the resulting Quadratic Unconstrained Binary Optimisation. One of the novelties in tackling this problem has been to compact the model bearing in mind the repetitions of each task, to make it possible to solve larger scheduling problems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ocean SDK demos. https://github.com/dwavesystems/demos
Bliek, C., Bonami, P., Lodi, A.: Solving mixed-integer quadratic programming problems with IBM-CPLEX: a progress report. In: Proceedings of the Twenty-Sixth RAMP Symposium, pp. 16–17 (2014)
Carugno, C., Ferrari Dacrema, M., Cremonesi, P.: Evaluating the job shop scheduling problem on a D-Wave quantum annealer. Sci. Rep. 12(1), 1–11 (2022)
Fourer, R., Gay, D.M., Kernighan, B.W.: AMPL. A Modeling Language for Mathematical Programming. Thomson (2003)
Gehrke, J.C., Jansen, K., Kraft, S.E.J., Schikowski, J.: A PTAS for scheduling unrelated machines of few different types. In: Freivalds, R.M., Engels, G., Catania, B. (eds.) SOFSEM 2016. LNCS, vol. 9587, pp. 290–301. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49192-8_24
Glover, F., Kochenberger, G., Hennig, R., Du, Y.: Quantum bridge analytics I: a tutorial on formulating and using QUBO models. Ann. Oper. Res. 314, 141–183 (2022). https://doi.org/10.1007/s10479-022-04634-2
Grant, E.K., Humble, T.S.: Adiabatic quantum computing and quantum annealing. Oxford Research Encyclopedia of Physics, July 2020
Kochenberger, G., et al.: The unconstrained binary quadratic programming problem: a survey. J. Comb. Optim. 28(1), 58–81 (2014). https://doi.org/10.1007/s10878-014-9734-0
Koshikawa, A.S., Ohzeki, M., Kadowaki, T., Tanaka, K.: Benchmark test of black-box optimization using D-Wave quantum annealer. J. Phys. Soc. Jpn. 90(6), 064001 (2021)
Ku, W.Y., Beck, J.C.: Mixed integer programming models for job shop scheduling: a computational analysis. Comput. Oper. Res. 73, 165–173 (2016)
Lewis, M., Alidaee, B., Kochenberger, G.: Using xQx to model and solve the uncapacitated task allocation problem. Oper. Res. Lett. 33(2), 176–182 (2005)
Lucas, A.: Ising formulations of many NP problems. Front. Phys. 2, 5 (2014)
Mohseni, N., McMahon, P.L., Byrnes, T.: Ising machines as hardware solvers of combinatorial optimization problems. Nat. Rev. Phys. 4(6), 363–379 (2022). https://doi.org/10.1038/s42254-022-00440-8
Orts, F., Ortega, G., Puertas, A.M., García, I., Garzón, E.M.: On solving the unrelated parallel machine scheduling problem: active microrheology as a case study. J. Supercomput. 76(11), 8494–8509 (2020). https://doi.org/10.1007/s11227-019-03121-z
Phillipson, F., Bhatia, H.S.: Portfolio optimisation using the D-Wave quantum annealer. In: Paszynski, M., Kranzlmüller, D., Krzhizhanovskaya, V.V., Dongarra, J.J., Sloot, P.M.A. (eds.) ICCS 2021. LNCS, vol. 12747, pp. 45–59. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77980-1_4
Sels, V., Coelho, J., Dias, A., Vanhoucke, M.: Hybrid tabu search and a truncated branch-and-bound for the unrelated parallel machine scheduling problem. Comput. Oper. Res. 53, 107–117 (2015)
Wang, T., Liu, Z., Chen, Y., Xu, Y., Dai, X.: Load balancing task scheduling based on genetic algorithm in cloud computing. In: Proceedings of the 2014 IEEE 12th International Conference on Dependable, Autonomic and Secure Computing, DASC 2014, pp. 146–152. IEEE Computer Society (2014)
Willsch, D., et al.: Benchmarking advantage and D-Wave 2000Q quantum annealers with exact cover problems. Quantum Inf. Process. 21(4), 1–22 (2022). https://doi.org/10.1007/s11128-022-03476-y
Acknowledgements
This work has been supported by the projects: RTI2018-095993-B-I00 and PID2021-123278OB-I00 (funded by MCIN/AEI/10.13039/501 100011033/FEDER “A way to make Europe”); P20_00748, UAL2020-TIC-A2101, UAL18-FQM-B038-A and UAL18-TIC-A020-B (funded by Junta de Andalucía and the European Regional Development Fund, ERDF).
Authors would also like to thank Professor Dr. Elías F. Combarro, from the Informatics Department, University of Oviedo, Spain, because this work has been possible thanks to the contents of his interesting lectures about Quantum Computing at Almería University.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Orts, F., Puertas, A.M., Garzón, E.M., Ortega, G. (2023). Quantum Annealing to Solve the Unrelated Parallel Machine Scheduling Problem. In: Wyrzykowski, R., Dongarra, J., Deelman, E., Karczewski, K. (eds) Parallel Processing and Applied Mathematics. PPAM 2022. Lecture Notes in Computer Science, vol 13827. Springer, Cham. https://doi.org/10.1007/978-3-031-30445-3_14
Download citation
DOI: https://doi.org/10.1007/978-3-031-30445-3_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-30444-6
Online ISBN: 978-3-031-30445-3
eBook Packages: Computer ScienceComputer Science (R0)