Scholarlink

The line balancing problem is a critical challenge in Industry 4.0 due to its significant impact on the efficiency, flexibility, and productivity of modern manufacturing systems. While this problem is classified as NP-hard, various optimisation tools have been developed to obtain feasible solutions. In this work, the line balancing problem (SALB-1 and SALB-2) is addressed using Quantum Annealing heuristics, implemented on D-Wave’s Leap technology. The SALB-1 and SALB-2 problems are first formulated as Quadratic Unconstrained Binary Optimization (QUBO) models. Then, using the Python package dwave.system, SALB-1 is solved with the Binary Quadratic Model class, and SALB-2 is tackled using the Constrained Quadratic Model class. To evaluate the implementation, three problem instances are solved, achieving the optimal solution in five out of six experiments. The cycle time of the experiment in which the algorithm did not find the optimum is 5 s above the optimum value. The code is available for download, allowing readers to replicate the results or solve larger instances using accounts with unrestricted access to D-Wave’s QPUs and hybrid solvers.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Modeling the Line Balancing Problem as a QUBO Model and Solving It by Quantum Annealing

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Luis A. Moncayo-Martínez,
  • Naihui He

摘要

The line balancing problem is a critical challenge in Industry 4.0 due to its significant impact on the efficiency, flexibility, and productivity of modern manufacturing systems. While this problem is classified as NP-hard, various optimisation tools have been developed to obtain feasible solutions. In this work, the line balancing problem (SALB-1 and SALB-2) is addressed using Quantum Annealing heuristics, implemented on D-Wave’s Leap technology. The SALB-1 and SALB-2 problems are first formulated as Quadratic Unconstrained Binary Optimization (QUBO) models. Then, using the Python package dwave.system, SALB-1 is solved with the Binary Quadratic Model class, and SALB-2 is tackled using the Constrained Quadratic Model class. To evaluate the implementation, three problem instances are solved, achieving the optimal solution in five out of six experiments. The cycle time of the experiment in which the algorithm did not find the optimum is 5 s above the optimum value. The code is available for download, allowing readers to replicate the results or solve larger instances using accounts with unrestricted access to D-Wave’s QPUs and hybrid solvers.