Application of quantum annealing for scalable robotic assembly line optimization: a case study

Moritz Willmann, Marcel Albus, Jan Schnabel, Marco Roth · 2024

Read Application of quantum annealing for scalable robotic assembly line optimization: a case study by Moritz Willmann, Marcel Albus, Jan Schnabel, Marco Roth (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-09239.txt.

Introduction

Moritz Willmann and three co-authors test in 2024 quantum annealing on the problem of balancing a robotic assembly line. Spreading tasks evenly across stations drives factory efficiency, but mass customization has swollen the problem past what classical solvers handle comfortably. The team recasts the balancing task as a binary optimization problem suited to quantum hardware.

A hybrid quantum-classical solver ran on a D-Wave Advantage machine and was compared with the exact optimum in a real-world-based case study. The quantum route showed real promise for cutting costs and raising output. Hardware limits and problem quirks still bite, so the authors frame the trial as a scouting report: quantum help for factory planning is coming, not yet here.

Catalog record

CREATORMoritz Willmann, Marcel Albus, Jan Schnabel, Marco Roth
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE24 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-09239

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Application of quantum annealing for scalable robotic assembly line optimization: a case study Moritz Willmann, Marcel Albus, Jan Schnabel, Marco Roth Abstract The even distribution and optimization of tasks across resources and workstations is a critical process in manufacturing aimed at maximizing efficiency, productivity, and profitability, known as Robotic Assembly Line Balancing (RALB) . With the increasing complexity of manufacturing required by mass customization, traditional computational approaches struggle to solve RALB problems efficiently. To address these scalability challenges, we investigate applying quantum computing, particularly quantum annealing, to the real-world based problem. We transform the integer programming formulation into a quadratic unconstrained binary optimization problem, which is then solved using a hybrid quantum-classical algorithm on the D-Wave Advantage 4.1 quantum computer. In a case study, the quantum solution is compared to an exact solution, demonstrating the potential for quantum computing to enhance manufacturing productivity and reduce costs. Nevertheless, limitations of quantum annealing, including hardware constraints and problem-specific challenges, suggest that continued advancements in quantum technology will be necessary to improve its applicability to RALB manufacturing optimization. I Introduction Robotic Assembly Line Balancing (RALB) is crucial for maximizing production efficiency, productivity, and profitability [ 1 ] . It involves assigning tasks among workstations to optimize production time or workstation count, considering automated resources and alternatives [ 2 ] . An optimal line balance is essential for today’s manufacturing companies to meet customer demands while maintaining competitiveness [ 3 ] . With increasing manufacturing complexity due to mass customization, traditional approaches face scalability challanges and struggle to solve the Robotic Assembly Line Balancing Problems (RALBPs) efficiently [ 4 , 5 ] . Quantum computing shows promising results in addressing these scalability challenges, potentially enabling near-optimal or faster optimal solutions for RALBP [ 6 , 7 ] . Quantum algorithms like Quantum Approximate Optimization Algorithm (QAOA) [ 8 ] , and quantum annealing [ 9 ] have shown promising results in solving different optimization problems [ 10 , 11 ] , making them appealing for the RALBP . We investigate the potential of quantum computing for RALBP , scrutinizing the approach to address scalability challenges by translating the Integer Programming (IP) problem into a Quadratic Unconstrained Binary Optimization (QUBO) and mapping it to an Ising model. We solve a problem instance on the D-Wave Advantage 4.1 quantum computer to identify potentials and problems. In this use case study, we compare a quantum approach to classical methods for solving the RALBP , assessing their practical benefits in real-world manufacturing scenarios. By detailing the procedure to address the problem with quantum computing and providing a corresponding python tool [ 12 ] , we aim at enabling manufacturers to assess the potential of quantum computing for the RALBP . The remainder of this paper is structured as follows. In Section II , the current state of the art of solving the RALBP as well as the application of quantum computing to combinatorial optimization problems (COPs) is discussed. Section III presents the IP and the QUBO model formulation, and the quantum annealing solution approach. A RALBP case study is presented in Section IV , and Section V discusses the results and provides an outlook. II Related Work The definition of the RALBP , is driven by real-world manufacturing needs for flexibility and increased competitiveness through specialized production equipment [ 2 ] . Classical methods for solving the RALBP include exact methods [ 13 ] , heuristics [ 14 , 15 ] and meta-heuristic approaches [ 16 , 17 ] , with significant improvements in the last decades [ 18 ] . However, these methods often struggle when dealing with large-scale and highly complex instances [ 19 ] . Either they provide high-quality results for small instances through exact solution techniques [ 20 ] , or scalability in complex instances with reduced quality through meta-heuristic techniques [ 16 ] . As the number of tasks and workstations increases, the computational complexity proves a significant issue due to the NP-hard problem type, making it infeasible to find optimal solutions within a reasonable time. This scalability issue has motivated the exploration of new computational paradigms, such as quantum computing, to tackle the RALBP more efficiently. Recently, the availability of early-stage quantum computing devices has raised interest in applying quantum algorithms to a wide range of problems. Alongside the simulation of physical systems and machine learning, COPs has been one of the areas of research where quantum computing has been applied [ 10 ] . Quantum annealing, a specialized form of quantum computation, is naturally suited for solving COPs [ 21 ] . It returns the lowest possible energy in a physical system described by the Ising Hamiltonian, which corresponds to the optimal solution of the COP . Quantum annealers are already commercially available and have been applied to various industrial problems [ 22 , 23 ] . Quantum annealing has shown promising results in manufacturing, including layout planning [ 19 ] , job shop scheduling [ 24 ] , and production planning [ 4 ] . A list of industry-related reference problems suitable for quantum computing in the automotive industry has been curated [ 25 ] , with some already being addressed [ 26 ] . Benefits of quantum annealing in manufacturing include handling complex combinatorial problems, potentially finding higher-quality solutions, or faster solution generation for certain problems [ 25 , 21 , 6 ] . However, limited qubit counts, connectivity issues, and noise in quantum systems currently restrict its universal applicability. III Methods In this section, we introduce the IP model for the RALBP . This is then used to reformulate the problem in a QUBO form which allows for a solution with a quantum computer. III.1 Integer Programming Model Formulation The RALBP aims to assign tasks to production equipment and allocate equipment to workstations to manufacture a desired product. An assignment optimization can maximize efficiency or minimize investment costs. Manufacturing requires all tasks to be assigned, each with equipment-specific processing times, following a predetermined assembly order within a given cycle time. The pieces of equipment are selected from available production resources. The IP model formulation requires two binary decision variables, one for the assignment of equipment to workstations and the second for the assignment of tasks to workstations. We define y_{jk}=1 if equipment j is assigned to workstation k , 0 otherwise. Additionally, x_{ijk}=1 if task i is performed by equipment j at workstation k , 0 otherwise. An overview of the variable notation for the RALBP model is given in Table 1 . This results in the IP problem formulation for the RALBP [ 2 ] : \displaystyle\min\sum_{j=1}^{r}\sum_{k=1}^{m}c_{j}y_{jk} (1) s.t. \displaystyle\sum_{j=1}^{r}\sum_{k=1}^{m}x_{ijk}=1 \displaystyle\forall i (2) \displaystyle\sum_{i=1}^{n}t_{ij}x_{ijk}\leq Cy_{jk} \displaystyle\forall j,k (3) \displaystyle\sum_{i=1}^{n}\sum_{j=1}^{r}t_{ij}x_{ijk}\leq C \displaystyle\forall k (4) \displaystyle\sum_{j=1}^{r}\sum_{k=1}^{m}kx_{pjk}\leq\sum_{j=1}^{r}\sum_{l=1}^{m}lx_{ijl} \displaystyle\forall p\in\mathcal{P}_{i},i (5) The objective function ( 1 ) minimizes total equipment costs. Constraint ( 2 ) assigns each task to exactly one workstation. Constraint ( 3 ) ensures that the task time at each piece of equipment does not exceed cycle time and that pieces of equipment can only perform tasks if assigned to the workstation. Additionally, multiple pieces of equipment can be assigned to one workstation. The sum of the total workstation task time is limited to cycle time by constraint

Read the complete text