1. Introduction
Classical metaheuristics for job shop scheduling often trade off solution quality against convergence speed on large problem instances, and quantum-inspired evolutionary algorithms have shown promise in other combinatorial domains by maintaining a superposition-like probabilistic population representation that can be evaluated entirely on classical hardware.
2. Methodology
A qubit-inspired evolutionary algorithm representing each scheduling decision as a probability amplitude pair, updated via a rotation-gate-inspired operator toward better-performing solutions, was applied to a 200-job, 20-machine job shop scheduling benchmark derived from standard OR-Library instances, and compared against a standard genetic algorithm and simulated annealing under an equal function-evaluation budget.
3. Results
The quantum-inspired algorithm found solutions with makespan averaging 6.1 percent above the best-known lower bound across the benchmark instance set, compared with 9.8 percent for the genetic algorithm and 11.4 percent for simulated annealing, while reaching its best solution in 34 percent fewer iterations on average than the genetic algorithm.
4. Conclusion
Quantum-inspired probabilistic representations improve both solution quality and convergence speed for large-scale job shop scheduling without requiring quantum hardware. Future work will evaluate hybridisation with problem-specific local search operators.
References
[1] Han K.-H. and Kim J.-H., Quantum-inspired evolutionary algorithm for a class of combinatorial optimization, IEEE Transactions on Evolutionary Computation, 2002. [2] Pinedo M., Scheduling: Theory, Algorithms, and Systems, Springer, 2016.