Qualitative Constraints for Job Shop Scheduling

This paper introduces a translation of the job shop scheduling problem into a qualitative constraint satisfaction problem using INDU and Allen relations. We show that the translation is sound and complete. We also use the notion of frozen constraints and show that it allows the user to consider only par- tial solutions when searching for solutions. Our work constitutes a new approach to the problem of constructing content- motivated benchworks for qualitative calculi.