PROCESS OPTIMISATION IN MANUFACTURING INDUSTRY
The integration of quantum computing in the manufacturing industry holds significant promise for advancing value creation by optimising various aspects in manufacturing processes. Notably, the computational capabilities offered by quantum technology are anticipated to bring about substantial benefits in the design, planning, and scheduling phases, and therefore enhance the overall efficiency and productivity.
In the following, we exemplify the application of quantum computation to the automotive industry via the multi-car paint shop problem. Our Quantum Computer minimises the number of colour switches in the production chain of a car paint shop.
© Photocredits: Shutterstock
OPTIMISING COLOuR SWITCHES IN A CAR PAINT SHOP
We implement a quantum optimisation algorithm to find the minimum number of colour-switches necessary to cover all cars queued in a car paint shop.
The multi-car paint shop problem is an important optimisation task in the automotive industry (NP-complete). The objective is to reduce costs and production time, by finding the minimum number of colour switches for painting adjacent cars in a paint-shop queue.
Formally the problem is described as N cars entering the paint shop to be painted with a black or white filler layer. Each car in the sequence belongs to one of M ensembles (e.g. defined by the car type), with the constraint that in each ensemble a given number kM of cars must be painted black. Our quantum system decides how to paint each car in the sequence, such that the number of filler-colour switches between adjacent cars is minimal, while the ensemble constraints are satisfied. The proof-of-concept experiment elaborated below shows that AQT’s quantum computers can be harnessed to solve real-world optimisation problems. Our systems will be accessible via the Cloud to also solve your optimisation problem!
IMPLEMENTATION DETAILS AND RESULTS
For the experimental implementation of the car-paint shop problem we use a 10-qubit register on AQT’s quantum computer, and encode the following settings (see figure 1):
Following ref. [https://www.computer.org/csdl/proceedings-article/qce/2021/169100a035/1yEZ9U3caCk], we represent each car by a qubit and encode the problem in an Ising-type Hamiltonian:
The ground state of the Hamiltonian represents the optimum solution of our problem. We get approximate solutions for the ground state using the variational QAOA (Quantum Approximate Optimisation Algorithm) of the Qiskit SDK (see figure 2). Results are returned as a bit-string, directly corresponding to the suggested sequence of black (0) and white (1) filler-colour for the incoming cars.
Note that for 10 cars there exist 210 = 1024 possible colour sequences, for 30 cars this already amounts to 1 billion. From all possibilities we let the quantum implementation preselect 200 promising candidate solutions and subsequently classically pick the best (lowest energy) solution that fulfils the ensemble constraints.
Using our quantum computer for the quantum preselection, we successfully find the ideal solution for the filler-paint sequence:[1, 1, 1, 0, 0, 0, 0, 0, 0, 0] = [‘W’, ‘W’, ‘W’, ‘B’, ‘B’, ‘B’, ‘B’, ‘B’, ‘B’, ‘B’], corresponding to only 1 colour switch (see figure 3).
Obtaining such an optimised solution, while fulfilling the ensemble constraints, is not trivial. In comparison, one can try a classical heuristic “black-first algorithm”: it paints cars black as long as the ensemble constraints allow for. That is, if the incoming car belongs to ensemble “Small” it is painted black if the number of “small” cars to be painted black is not yet exceeded. Otherwise, it is painted white. This classical greedy algorithm finds a solution with 6 colour switches:[‘B’, ‘B’, ‘W’, ‘B’, ‘B’, ‘W’, ‘B’, ‘B’, ‘W’, ‘B’], which would be associated with significantly higher costs or time compared to the solution calculated on the AQT quantum computer.
FIGURE 1: Problem description
Cars are affiliated to one of three ensembles “Small”, “Medium” or “Large”. The cars come into the car-paint shop in a random order. For each ensemble there is a given number of cars to be painted black.
FIGURE 2: Solving the problem using QAOA (Quantum Approximate Optimisation Algorithm)
The QAOA (Quantum Approximate Optimisation Algorithm) searches for the lowest energy state of the Hamiltonian that encodes the problem: 1. A quantum state is prepared by a sequence of single- and two-qubit gates defined by parameters alpha, beta, … 2. The energy of the state is measured. 3. Parameters alpha, beta, … are adapted and steps 1-3 repeated to find the quantum state with lowest energy.
FIGURE 3: Result
Solution for the filler-paint sequence as found by our quantum computer, based on trapped-ion technology. The car-paint shop needs to perform only 1 colour switch to fulfil all requirements.
