Cyclic multiple-robot scheduling with time-window constraints using a critical path approach

An automated production system is considered in which several robots are used for transporting parts between workstations following a given route in a carousel mode. The problem is to maximize the throughput rate. Extending previous works treating scheduling problems for a single robot, we consider a more realistic case in which workstations are served by multiple robots. A graph model of the production process is developed, making it possible to apply PERT–CPM solution techniques. The problem is proved to be solvable in polynomial time.