The time varying 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, in manufacturing systems or multiprocessor computing. It has beenstudied from multiple perspectives, since there exist several possible representations of theproblem such as graph theory, mixed integer linear programming, Petri nets or (max, +)algebra. An overview about cyclic scheduling problems and the different approaches can befound in [Hanen and Munier, 1995a] and [Brucker and Kampmeyer, 2008]. However, fewworks have tackled the robust version of this problem although the literature for robustclassical scheduling problem is large. In this paper, we consider a subset of tasks thathave variable processing times. Besides, the minimum processing time and the maximumprocessing time of these tasks are known. We propose a method that finds the schedulewhich minimizes the expected cycle time. We show that the evaluation of a schedule can beconsidered as a volume calculus of polyhedron. More precisely, for each schedule we derive aset of polyhedron and the integral calculus (based on the Vinci library [Bueler et al., 2000])of their volume leads to an evaluation of the performance of the considered schedule. Thisapproach enables to derive a branch and bound procedure to choose the best schedule inthe sense of the smallest cycle time with respect to the variability of the processing times