On A Conjecture About Robotic Cells: New Simplified Proof For The Three-Machine Case

摘要

AbstractWe consider a robotic cell, consisting of a flow-shop in which the machines are served by a single central robot. We concentrate on the case where only one part type is produced and want to analyze the conjecture of Sethi, Sriskandarajah, Sorger, Blazewicz and Kubiak. This well-known conjecture claims that the repetition of the best one-unit production cycle will yield the maximum throughput rate in the set of all possible robot moves. The conjecture holds for two and three machines, but the existing proof by van de Klundert and Crama for the three-machine case is extremely tedious.We adopt the theoretical background developed by Crama and van de Klundert. Using a particular state graph, the k-unit production cycles are represented as special paths and cycles for which general properties and bounds for the m-machine robotic cell can be obtained. By means of these concepts, we shall give a concise proof for the validity of the conjecture for the three-machine case.RésuméOn considère une cellule de production composée de m machines et d'un robot chargé du transfert des pièces entre les machines. Les pièces à produire sont toutes identiques et doivent passer successivement, et dans le même ordre, sur toutes les machines. Une machine ne peut accueillir plus d'une pièce à la fois. On souhaite analyser la conjecture de Sethi, Sriskandarajah, Sorger, Blazewicz et Kubiak qui prétend que le taux maximum de production peut être obtenu en répétant le meilleur cycle de production d'une seule pièce. Cette conjecture a été démontrée pour deux et trois machines, mais la preuve de van de Klundert et Crama pour le cas de trois machines est très fastidieuse.En utilisant les bases théoriques introduites par Crama et van de Klundert, nous définissons des graphes particuliers, les graphes d'état, dans lesquels les cycles de production de k pièces sont représentés par des chemins et par des cycles. Ces graphes permettent de trouver des propriétés et des bornes pour les cellules de production. Au moyen de ces concepts, nous donnons une preuve concise de la validité de la conjecture pour le cas de trois machines. Additional informationNotes on contributorsNadia BraunerGerd Finke received the M.Sc. and Ph.D. degrees in mathematics from the University of Kiel, West Germany, in 1969. He then joined the Faculty of Engineering of the Technical University of Nova Scotia, Halifax, Canada, where he served as Professor in the Departments of Applied Mathematics and Industrial Engineering till 1988. He is currently Professor and Director of graduate studies in operations research at the University Joseph Fourier in Grenoble, France. His main interests are in combinatorial optimization, scheduling and O.R. methods applied to manufacturing systems.Gerd FinkeNadia Brauner est ingénieur en informatique et mathématiques appliquées. Elle prépare actuellement une thèse en informatique (spécialité recherche opérationnelle) à l'université Joseph Fourier à Grenoble en France. Elle travaille au sein de l'équipe recherche opérationnelle du département de mathématiques discrètes du laboratoire Leibniz-IMAG. Sa recherche porte sur l'ordonnancement dans les cellules robotisées et sur des problèmes de poinçonnage de tôle.