Recognizing finite repetitive scheduling patterns in manufacturing systems

Optimization of timing behaviour of manufacturing systems can be regardedas a scheduling problem in which tasks model the various productionprocesses. Typical for many manufacturing systems is that (collectionsof) tasks can be associated with manufacturing entities, which canbe structured hierarchically. Execution of production processes for severalinstances of these entities results in nested finite repetitions, whichblows up the size of the task graph that is needed for the specification ofthe scheduling problem, and, in an even worse way, the number of possibleschedules. We present a subclass of UML activity diagrams whichis generic for the number of repetitions, and therefore suitable for thecompact specification of task graphs for these manufacturing systems.The approach to reduce the complexity of the scheduling problem exploitsthe repetitive patterns. It reduces the original problem to a problemcontaining the minimum amount of identical repetitions, and afterscheduling of this much smaller problem the schedule is expanded tothe original size. We demonstrate our technique on a real-life examplefrom the semiconductor industry.