Sequencing of parts in a robotic cell

Abstract : This paper considers scheduling problems in a robotic cell which produces a set of parts on several machines served by a robot. We study the problem of sequencing parts in the cell in order to minimize 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 cycles in a robotic cell with more than two machines producing more than two part-types. We first give a mathematical formulation to the problem, and then propose a branch-and-bound algorithm to solve it. The bounding scheme of this algorithm is based on relaxing, for all the machines except two, the constraint that the machine is occupied by a part for a period at least as long as the processing time of the part. It turns out that the lower bound obtained in this way is tight. This relaxation allows us to overcome the complexity of the problem. The lower bound can be computed using the algorithm of Gilmory and Gilmore. Computational experiments on part sequencing problems in three-machine robotic cells are given.
Type de document :
[Research Report] RR-2496, INRIA. 1995, pp.26
Liste complète des métadonnées
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 14:41:11
Dernière modification le : samedi 17 septembre 2016 - 01:06:55
Document(s) archivé(s) le : mardi 12 avril 2011 - 15:46:13



  • HAL Id : inria-00074179, version 1



Haoxun Chen, Chengbin Chu, Jean-Marie Proth. Sequencing of parts in a robotic cell. [Research Report] RR-2496, INRIA. 1995, pp.26. 〈inria-00074179〉



Consultations de la notice


Téléchargements de fichiers