New Pre-Print “Highly Efficient Encoding for Job-Shop Scheduling Problems and its Application on Quantum Computers”
Combinatorial optimization problems are regarded as a promising use case for quantum computing. One such problem, which is of paramount relevance in industry, computation, and economics, is (flexible) job shop scheduling. 
It considers a set of jobs of varying processing times and seeks to schedule them on a set of machines and/or operators with varying processing capabilities such that the makespan, the time it takes to complete the last finishing job, is minimized. In quantum computing, reducing the number of variables, i.e. qubits, representing the problem becomes crucial.
Our preprint (https://arxiv.org/abs/2401.16381) introduces an efficient encoding based on permutations and inversion vectors. For the popular problem of N jobs with N operations, the number of variables is at least reduced by a factor N/log(N) as compared to the widely considered time indexed encodings. Importantly, the encoding we develop also enables significantly more compact classical representations and will therefore be highly useful even beyond applicability on quantum hardware.