CYCLIC SCHEDULING OF OPERATIONS FOR A PART TYPE IN AN FMS HANDLED BY A SINGLE ROBOT - A PARAMETRIC CRITICAL-PATH APPROACH

We consider two problems of periodic scheduling of parts in a robotic production system functioning under a given repetitive robot's route. The objective is to determine the starting times and durations of proc essing operations so as to minimize the cycle length. We reduce the pr oblems to finding parametric critical paths in networks with varying a re lengths. In contrast to previously known methods, which solve these cyclic scheduling problems in cubic time, the parametric network appr oach solves the problems in O (m(2) log m) time, m being the problem s ize.