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 functioningunder a given repetitive robot's route. The objective is to determine the starting times and durations ofprocessing operations so as to minimize the cycle length. We reduce the problems to findingparametric critical paths in networks with varying arc lengths. In contrast to previously knownmethods, which solve these cyclic scheduling problems in cubic time, the parametric networkapproach solves the problems in O (m{sup}2 log m) time, m being the problem size.