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.