  The Job-Shop Scheduling Problem (JSSP) stands as one of the most renowned
challenges in scheduling. It is characterized as a disjunctive problem, wherein
a solution is fully depicted through an oriented disjunctive graph, with
earliest starting times computed using a longest path algorithm. The complexity
of solving this problem arises in part from the requirement that disjunctive
graphs representing solutions must be acyclic. Consequently, enumerating these
graphs is feasible for small-scale instances only. A significant advancement in
this field, credited to (Bierwith, 1995), is the introduction of the 'vector by
repetition' (commonly known as Bierwith's vector). Notably, this vector
possesses the property that it can be mapped to an acyclic disjunctive graph,
thereby enabling the mapping of a vector to a solution. This property has
facilitated the development of highly efficient resolution schemes, as it
allows the enumeration of solutions only i.e. acyclic disjunctive graphs. Our
objective is to demonstrate how Bierwith's vector can be integrated into a
Quantum Approximate Optimization Algorithm (QAOA) to tackle the job-shop
problem using a novel quantum approach.
