  We present a generalization of the binary paint shop problem (BPSP) to tackle
an automotive industry application, the multi-car paint shop (MCPS) problem.
The objective of the optimization is to minimize the number of color switches
between cars in a paint shop queue during manufacturing, a known NP-hard
problem. We distinguish between different sub-classes of paint shop problems,
and show how to formulate the basic MCPS problem as an Ising model. The problem
instances used in this study are generated using real-world data from a factory
in Wolfsburg, Germany. We compare the performance of the D-Wave 2000Q and
Advantage quantum processors to other classical solvers and a hybrid
quantum-classical algorithm offered by D-Wave Systems. We observe that the
quantum processors are well-suited for smaller problems, and the hybrid
algorithm for intermediate sizes. However, we find that the performance of
these algorithms quickly approaches that of a simple greedy algorithm in the
large size limit.

Quantum Physics;Emerging Technologies