Cyclic scheduling in a robotic production line

The solution of cyclic scheduling problems is part of the classical repertoire on scheduling algorithms. We consider a problem of cyclic scheduling of identical parts in a production line where transportation of the parts between machines is performed by several robots. The problem is to find co-ordinated movements of the parts and robots in the line with the no-wait constraints imported; the objective is to maximize the throughput rate. Unlike many previous algorithms which are either heuristic or at best solve the single-robot version of the problem in O(m(4) log m) time, the proposed algorithm provides an exact solution for the more complicated case of multiple robots and solves the problem in O(m(3) log m) time, where in denotes the number of machines in the line. Copyright (C) 2002 John Wiley Sons, Ltd.