BMW Group: Quantum Annealing for Production Scheduling

The Problem

BMW Group manufactures hundreds of thousands of vehicles per year across multiple factories, each producing thousands of distinct configurations. Assigning car orders to production slots on assembly lines is a massive constraint satisfaction problem.

The constraints are strict: paint shop sequencing limits which colors can follow each other (avoiding costly color changeovers), component delivery windows restrict when specific configurations can be built, and assembly line capacity creates hard slot limits. The full problem involves millions of variables and has to be solved repeatedly as orders change.

Classical scheduling software (SAP APO) handles this but can take hours to compute solutions for hard subproblems. BMW asked: can quantum annealing accelerate the hardest parts?

Formulating Scheduling as QUBO

D-Wave quantum annealers solve Quadratic Unconstrained Binary Optimization (QUBO) problems. Every variable must be binary (0 or 1) and the objective must be quadratic. BMW’s team reformulated scheduling subproblems to fit this structure.

For a simplified version: assign N jobs to T time slots, one job per slot, minimizing penalty costs for sequencing violations and deadline misses.

import dimod
from dwave.system import LeapHybridSampler

# Small example: 4 jobs, 4 time slots
# x[i][t] = 1 if job i is assigned to slot t
n_jobs = 4
n_slots = 4

# Penalty weight for constraint violations
penalty = 10.0

# Build QUBO dictionary
Q = {}

# Constraint 1: each job assigned to exactly one slot
for i in range(n_jobs):
    for t in range(n_slots):
        key = (f"x_{i}_{t}", f"x_{i}_{t}")
        Q[key] = Q.get(key, 0) - penalty
        for t2 in range(t + 1, n_slots):
            key2 = (f"x_{i}_{t}", f"x_{i}_{t2}")
            Q[key2] = Q.get(key2, 0) + 2 * penalty

# Constraint 2: each slot holds at most one job
for t in range(n_slots):
    for i in range(n_jobs):
        key = (f"x_{i}_{t}", f"x_{i}_{t}")
        Q[key] = Q.get(key, 0) - penalty
        for i2 in range(i + 1, n_jobs):
            key2 = (f"x_{i}_{t}", f"x_{i2}_{t}")
            Q[key2] = Q.get(key2, 0) + 2 * penalty

# Sequencing cost: penalize adjacent color changes
color_change_cost = {(0, 1): 3.0, (1, 2): 1.0, (2, 3): 5.0}
for (i, j), cost in color_change_cost.items():
    for t in range(n_slots - 1):
        key = (f"x_{i}_{t}", f"x_{j}_{t+1}")
        Q[key] = Q.get(key, 0) + cost

# Solve using D-Wave Leap hybrid solver
bqm = dimod.BinaryQuadraticModel.from_qubo(Q)
sampler = LeapHybridSampler()
response = sampler.sample(bqm, time_limit=3)

best = response.first.sample
assigned = {f"x_{i}_{t}": best[f"x_{i}_{t}"]
            for i in range(n_jobs) for t in range(n_slots)
            if best.get(f"x_{i}_{t}", 0) == 1}
print("Job assignments:", assigned)

How the Hybrid Solver Works

BMW did not send the full scheduling problem to a D-Wave quantum annealer directly. Current D-Wave systems have limited qubit connectivity, and the full BMW problem has far more variables than any annealer can handle natively.

Instead, they used D-Wave’s Leap hybrid solver, which works in stages. A classical preprocessing layer decomposes the problem and identifies the hardest subproblems. Those subproblems are embedded onto the quantum annealer. The quantum annealer explores the energy landscape to find low-energy configurations. Classical postprocessing assembles the final solution.

This hybrid approach is key to getting practical value out of today’s hardware.

Results

BMW reported that scheduling subproblems which previously took hours of classical compute time were resolved in minutes using the hybrid solver. The full production scheduling workflow still relies on classical software for high-level planning, but the quantum component accelerates the bottleneck subproblems.

BMW presented the work at the Q2B (Quantum to Business) conference in 2021. The results were notable enough to demonstrate real-world applicability, though the team was clear that full quantum advantage over the best classical solvers remains unproven.

What This Means for Manufacturing

BMW’s project is a template for near-term quantum use in industry. The lessons:

• QUBO reformulation is non-trivial: Domain experts must work closely with quantum software teams to map business constraints into QUBO form
• Hybrid is essential today: Neither pure quantum nor pure classical, but orchestrated together
• Subproblem selection matters: Quantum hardware helps only on the specific subproblems that map well to the annealer’s topology

The manufacturing sector is a strong early candidate for quantum annealing because production scheduling, supply chain routing, and parts logistics are all combinatorial problems with natural QUBO formulations.

Framework

BMW used D-Wave’s Ocean SDK, specifically the dimod library for QUBO construction and LeapHybridSampler from dwave.system for hybrid solving.

Learn more: Quantum Annealing Reference