Scheduling in robotic cells

Abstract

Numerous industrial studies have identified significant improvements in productivity that can result from the use of robots to serve (i.e., load parts onto and unload parts from) similar machines producing a family of similar parts. A robotic cell consists of several production machines served by a single robot, often with no intermediate buffers. We consider a class of problems that arise in the scheduling of robotic cells. The objective is the minimization of the steady state cycle time to produce a minimal part set, or equivalently the maximization of long-run throughput rate. Two decisions need to be made simultaneously: finding the optimal robot move cycle, and finding the optimal part sequence through the cell. The results to be described include: efficient algorithms, intractability proofs, the identification of easily solvable special cases, and computationally effective heuristics for hard problems. We also discuss tradeoffs between throughput rate and inventory from combining several minimal part sets together, bounds on cell transition times from initialization into a steady state, and the design of cells and buffers within a larger manufacturing environment. We also report the first progress towards resolving a well-known conjecture for identical part problems. Finally, we provide a list of open problemsmore » in robotic cell scheduling. Some of the procedures described have been implemented in a fully operational robotic cell at the University of Toronto. The cell is used for teaching purposes, and access is also provided to industry.« less