A heap of pieces model for the cyclic job shop problem

International audienceIn classical scheduling, a set of tasks is executed once while the determined scheduleoptimizes objective functions such as the makespan or earliness-tardiness. In contrast, cyclicscheduling means performing a set of generic tasks infinitely often while minimizing thetime between two occurrences of the same task. Cyclic scheduling has several applications,e.g. in robotic industry (see Kats and Levner [1997]), in manufacturing systems (see Pinedo[2005] and Hillion and Proth [1989]) or multiprocessor computing (see Hanen and Munier[1995b]). It has been studied from multiple perspectives, since there exist several possiblerepresentations of the problem such as graph theory, mixed integer linear programming,Petri nets or (max; +) algebra. An overview about cyclic scheduling problems and thedifferent approaches can be found in Hanen and Munier [1995a].However, a less known tool is the heaps of pieces approach. A first paper consideringthis modelling for cyclic scheduling is Gaubert and Mairesse [1999]. The authors introducea method to represent safe Petri nets as particular automata which compute the height ofheaps of pieces. This approach enables to compute efficiently the throughput of a cyclicschedule. In this paper, we use the heaps of pieces approach for solving cyclic schedulingproblems with resource constraints