A scheduling method for a single machine scheduling problem with sequence dependent setup times is presented where similar products produced on the machine can be partitioned into families. A two-stage traveling salesman heuristic procedure is developed. In the first stage an n×n symmetric setup time matrix is generated for n products and the products are classified into families (groups) using either a hierarchical cluster analysis procedure or the users internal groupings. A Traveling Salesman Problem (TSP) is then solved to obtain an efficient sequence for each family. In the second stage, a special purpose traveling salesman heuristic is developed to combine the already sequenced families in an efficient way. The results of the computational study show that the Two-Stage Traveling Salesman procedure is approximately two to four times faster than the well known TSP heuristic by Lin and Kernighan, while the solution quality is comparable to Lin and Kernighan’s heuristic. The paper also illustrates the industrial application of the procedure for an automated cable assembly machine.
