Scheduling in robotic cells: Complexity and steady state analysis

This paper considers the scheduling of operations in a manufacturing cell that repetitively produces a family of similar parts on several machines served by a robot. The decisions to be made include finding the robot move cycle and the part sequence that jointly minimize the production cycle time, o...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 1998-08, Vol.109 (1), p.43-65
Main Authors: Hall, Nicholas G., Kamoun, Hichem, Sriskandarajah, Chelliah
Format: Article
Language:English
Subjects:
Applied sciences
Computational complexity
Computer science
control theory
systems
Control theory. Systems
Deterministic scheduling
Exact sciences and technology
Manufacturing
Manufacturing cells
Operational research and scientific management
Operational research. Management science
Operations research
Production scheduling
Robotic cell
Robotics
Robots
Scheduling, sequencing
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper considers the scheduling of operations in a manufacturing cell that repetitively produces a family of similar parts on several machines served by a robot. The decisions to be made include finding the robot move cycle and the part sequence that jointly minimize the production cycle time, or equivalently maximize the throughput rate. We focus on complexity issues and steady state performance. In a three machine cell producing multiple part-types, we prove that in two out of the six potentially optimal robot move cycles for producing one unit, the recognition version of the part sequencing problem is unary NP-complete. The other four cycles have earlier been shown to define efficiently solvable part 'sequencing problems. The general part sequencing problem not restricted to any robot move cycle in a three machine cell is shown to be unary NP-complete. Finally, we discuss the ways in which a robotic cell converges to a steady state.
ISSN:0377-2217
1872-6860
DOI:10.1016/S0377-2217(96)00333-5