Dfjsp QA Eval

dfjsp-qa-eval

Solving Distributed Flexible Job Shop Scheduling Problems in the Wool Textile Industry with Quantum Annealing — Toma et al. (2024) (arXiv:2403.06699, 2024)

What this evaluates

Evaluates the ability of a quantum annealer (D-Wave) to solve distributed flexible job shop scheduling problems (DFJSP) compared to classical simulated annealing. It probes solver performance in terms of solution quality (energy, makespan, constraint satisfaction) and computational efficiency (runtime scaling) across varying problem sizes.

Datasets

• Custom DFJSP instances (wool textile industry) — total 6; splits: test (6)

Metrics

• System energy (primary) — range: other
  • The total cost value of the QUBO objective function, including penalty terms for constraint violations.
• Makespan — range: other
  • The total time to complete all operations, calculated as the difference between the maximum and minimum ending times of all operations.
• Calculation time — range: other
  • Wall-clock or CPU time required by the solver to generate the sample set and return the best solution.
• Broken constraints — range: other
  • Number of violated constraints in the returned schedule, indicating infeasible assignments.

Input / output format

Input: QUBO formulation of DFJSP instances with binary variables x_i,o,m,t representing job, operation, machine, and time. Problem sizes range from 50 to 250 logical variables, mapped to physical qubits via embedding chains.

Output: A sample set of 1000 solutions (reads) from the QPU or SA sampler. The best solution is selected as the sample with the lowest system energy.

Scoring recipe

def evaluate_solver(samples, problem_size):
    best = min(samples, key=lambda s: s.energy)
    energy = best.energy
    makespan = max(best.end_times) - min(best.end_times)
    violations = count_broken_constraints(best)
    runtime = measure_solver_time()
    return {
        'energy': energy,
        'makespan': makespan,
        'violations': violations,
        'runtime': runtime
    }

Common pitfalls

• Chain strength must be carefully tuned per instance; default or poorly chosen values lead to high broken-chain rates and inconsistent solutions.
• QPU access time is compared against SA CPU time, but hardware limitations cap embeddable problem sizes at 250 variables, making extrapolation to larger instances speculative.
• The evaluation prioritizes consistent, feasible schedules over finding the global energy minimum, which may differ from standard optimization benchmarks.

Evidence (verbatim from paper)

To provide the Contributions 2 and 3 formulated in Section[1], the results obtained from the experiment are analyzed from both a qualitative and a quantitative perspective. The first answers the question of how good the returned solution is in terms of system energy and makespan. The second compares QPU (Quantum Processing Unit) access time and CPU (Central Processing Unit) time of SA (Simulated Annealing) to assess whether there is a speed advantage in using the quantum annealer to solve the DFJSP (Distributed Flexible Job Shop Scheduling Problem) with distributed operations.

Citation

@misc{toma2024dfjspqa,
  title={Solving Distributed Flexible Job Shop Scheduling Problems in the Wool Textile Industry with Quantum Annealing},
  author={Toma et al. (2024)},
  year={2024},
  note={arXiv:2403.06699}
}

• arXiv: 2403.06699