Cost Optimization and Design of Production Lines

Solving the Assemly Line Balancing Problem

Fraunhofer IPA

In the demonstrator, an instance of the Assembly Line Balancing (ALB) problem is formulated and solved. In assembly line balancing, a production line for a specific product is to be set up in such a way that the lowest possible acquisition costs for machines are incurred and a specified cycle time is maintained. The problem is formulated mathematically as a Quadratic Unrestricted Binary Optimization problem (QUBO). It is then solved using simulated annealing and a heuristic search. The results show that the optimal solution of the instance is found with this method.

Optimal cutting layouts for metal parts manufacturing (BPP)

Fraunhofer IPA

The 2D irregular strip packing problem consists in finding the position and orientation of a set of polygons commonly referred to as "pieces" into a strip, i.e. a rectangular-shaped container with imposed and fixed height and variable length, such that: all the pieces fit completely inside the container, no two pieces intersect or »overlap« and the container's length is minimum. This problem is of significant economic importance as it allows the Manufacturing Industry to minimize its costs for materials such as fabric, leather, carton, wood, plastic, glass, ceramic or metal which are used for producing elementary parts composing finished products, such as cloths, cars, ships, electrical appliances, machines and packaging. The problem is also is great ecological importance, as it allows to reduce the industrial consumption of natural resources and the amount of industrial waste. Our solution is a hybrid quantum-classical algorithm that decomposes the problem into a rectangle packing problem and instances of the Traveling Salesman Problem (TSP). The TSP is solved by the Quantum Approximate Optimization Algorithm (QAOA) which is executed on the IBM Quantum System One, located in Ehningen, Germany. Our solution allows an arbitrary number of orientations of the pieces, scales up to a hundred pieces and is able to solve optimally a special class of "puzzle-like" problems.


The interactive demonstrator notebooks have been licensed under the Apache licence (version 2.0). The files may only be used in accordance with the licence. A copy of the licence can be downloaded from Except as required by applicable law or agreed to in writing, software distributed under this licence is distributed on an "AS IS" basis, without warranties or conditions of any kind, either express or implied. See the licence for the specific rights and restrictions associated with it.
This is a research prototype. Liability for loss of profit, loss of production, business interruption, loss of use, loss of data and information, financing costs and other financial and consequential damage is excluded, except in cases of gross negligence, intent and personal injury.