SEQUENCING OF PARTS IN ROBOTIC CELLS

This paper considers scheduling problems in robotic cells that produce a set of part types on several machines served by one robot. We study the problem of sequencing parts of different types in a cell to minim ize the production cycle time when the sequence of the robot moves is given. This problem is NP-hard for most of the one-unit robot move cyc les in a robotic cell with more than two machines and producing more t han two parr types. We first give a mathematical formulation to the pr oblem, and then propose a branch-and-bound algorithm to solve it. The bounding scheme of this algorithm is based on relaxing, for all of the the machines except two, the constraints that a machine should be occ upied by a part for a period at least as long as the processing time o f the part. The lower bound obtained in this way is tight. This relaxa tion allows us to overcome the complexity of the problem. The lower bo und can be computed using the algorithm of Gilmore and Gomory. Computa tional experiments on part sequencing problems in three-machine roboti c cells are given.