Groupe d’études et de recherche en analyse des décisions

G-85-20

Sequencing Punch Operations in a FMS: A Three-Dimensional Space-Filling Curve Approach

, , et

A Travelling Salesman Problem in a three-dimensional spatial domain is associated with a scheduling problem encountered in a flexible manufacturing cell including a computer-controlled punching machine. The heuristic recently proposed by Bartholdi and Platzman, which uses a spacefilling curve as a quick way to organize a tour of a set of locations to visit in a unit square, is tested and generalized to the spatial domain describing the punch operations. A new recursive procedure is proposed for the construction of open spacefilling curves in the unit cube and in a parallelopiped. Numerical experimentations show that the 3-dimensional spacefilling curve heuristic becomes attractive when the number of punches executed by each tool is relatively small and when the turret rotation speed is relatively high.

, 35 pages