We study the Job Shop Scheduling Problem with machine Availability Constraints (JSSP-AC) within a quantum-annealing framework. Using a dummy-job transformation, both fixed and variable machine unavailability periods are incorporated into a standard time-indexed quadratic unconstrained binary optimization (QUBO) model. We then introduce a constructive heuristic \(\mathcal {H}\) , its preemptive variant \(\mathcal {H}^*\) , and three annealing-based methods: \(\mathcal {M}_1\) , based on a naive time horizon; \(\mathcal {M}_2\) , using the tighter bound returned by \(\mathcal {H}\) ; and \(\mathcal {M}_3\) , which additionally uses the heuristic solution as a warm start in a reverse-annealing setting. A proof-of-concept experiment on D-Wave hardware confirms that the proposed formulation can be embedded and solved on small instances. On a broader benchmark, \(\mathcal {H}\) outperforms repaired dispatching heuristics, while the tighter horizon reduces QUBO size by 29.9%, quadratic terms by 46.4%, physical qubit usage by about 50%, and embedding time by 64%. The average optimality gap decreases from 18.3% for \(\mathcal {M}_1\) to 5.0% for \(\mathcal {M}_2\) and 3.3% for \(\mathcal {M}_3\) , highlighting the value of classical bounds and warm starts in quantum annealing for scheduling under machine unavailability.
