Solving the cyclic job shop scheduling problem with linear precedence constraints using CP techniques

摘要

A cyclic scheduling problem is a problem which, under the requirement of respecting a finite Set of constraints, consists in ordering a finite set of tasks occurring an indefinite number of times. In this piper, we propose, by employing different techniques that have been developed by the constraint programming (CP) community, to attack the cyclic lob shop scheduling problem with linear precedence constraints. Indeed, this problem can be cast as a constraint satisfaction problem (CSP) or a constraint optimization Problem (COP). By limiting the periodicity of the searched solution, we show that a complete tree search approach is viable since it allows giving satisfactory results while minimizing the overall execution time. Furthermore, such a solution is more adapted to an industrial context since a limited periodicity can be easily exploited.