Transforming part-sequencing problems in a robotic cell into a GTSP

Abstract

This paper shows how to solve two-part sequencing problems in a three-machine robotic cell so as to minimize the cycle time. We start dealing with cycles whose associated part-sequencing problems do not have the structure of a travelling salesman problem (TSP). The idea behind our approach is to modify the waiting time formula and formulate the closely related modified problem as a generalized travelling salesman problem (GTSP). The other cycles to be tackled are those that have a TSP structure for their associated part-sequencing problem. The existence of common states between these cycles allows us to mix and mould all of them into a GTSP. The solution procedures, designed for both cycle classes, are merged into a single heuristic and evaluated. The computational results provided prove the efficiency of the approaches.

Keywords:

• scheduling
• sequencing
• heuristics
• flexible manufacturing systems

Acknowledgements

We are grateful to Professor Chadlia Mohsen, for her assistance throughout the progress of this work.