Result: A polynomial algorithm for 2-cyclic robotic scheduling
Title:
A polynomial algorithm for 2-cyclic robotic scheduling
Authors:
Source:
MICAI 2006 (advances in artificial intelligence)Lecture notes in computer science. :439-449
Publisher Information:
Berlin; Heidelberg; New York: Springer, 2006.
Publication Year:
2006
Physical Description:
print, 20 ref 1
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Recherche operationnelle. Gestion, Operational research. Management science, Recherche opérationnelle et modèles formalisés de gestion, Operational research and scientific management, Ordonnancement, Scheduling, sequencing, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Intelligence artificielle, Artificial intelligence, Automatique théorique. Systèmes, Control theory. Systems, Robotique, Robotics, Atelier flexible, Flexible manufacturing system, Sistema flexible producción, Chaîne fabrication, Production line, Línea fabricación, Complexité algorithme, Algorithm complexity, Complejidad algoritmo, Complexité temps, Time complexity, Complejidad tiempo, Intelligence artificielle, Artificial intelligence, Inteligencia artificial, Machine unique, Single machine, Máquina única, Méthode polynomiale, Polynomial method, Método polinomial, Ordonnancement, Scheduling, Reglamento, Pilotage ordinateur, Computer control, Control por ordenador, Robot, Robotique, Robotics, Robótica, Système cyclique, Cyclic system, Sistema cíclico, Temps minimal, Minimum time, Tiempo mínimo, Temps polynomial, Polynomial time, Tiempo polinomial, Théorie euclidienne, Euclidean theory, Teoría euclidiana, Complexité polynômial, Polynomial complexity, Complejidad polinomial
Document Type:
Conference
Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Institute for Industrial Mathematics, Beer-Sheva, Israel
Holon Institute of Technology, Holon, Israel
Holon Institute of Technology, Holon, Israel
ISSN:
0302-9743
Rights:
Copyright 2007 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Operational research. Management
Operational research. Management
Accession Number:
edscal.19151727
Database:
PASCAL Archive
Further Information
We solve a single-robot m-machine cyclic scheduling problem arising in flexible manufacturing systems served by computer-controlled robots. The problem is to find the minimum cycle time for the so-called 2-cyclic (or 2-degree) schedules, in which exactly two parts enter and two parts leave the production line during each cycle. An earlier known polynomial time algorithm for this problem was applicable only to the Euclidean case, where the transportation times must satisfy the triangle inequality. In this paper we study a general non-Euclidean case. Applying a geometrical approach, we construct a polynomial time algorithm of complexity O(m5 log m).