Home Production Management Trainer HomeOverviewTactical PlanningOperative PlanningMiscellaneousGerman Pages

Operations sequencing with sequence-dependent setup costs/times

For a given set of jobs to be performed on a single machine with sequence-dependent setup costs or setup times a sequence is determined with the help of the closest-insertion or, alternatively, the farthest-insertation heuristic.

The sequencing problem is modeled as a traveling-salesman-problem (TSP) with each job being a node in the TSP-network and the arcs representing the setups between jobs. At the beginning of the heuristic one job must be selected to mark the current state of the machine. The heuristic runs through several iterations. It starts by selecting one job and builds up partial subtours with increasing numbers of assigned jobs. In each iteration the node is selected from those currently unassigned that is closest to (farthest from) any node in the partial sequence. Having determined this node, we insert it into the sequence with minimum increase of the length of the sequence.


d(i,j) setup costs (time), if job j is performed directly after job i
i-xxx job i is already assigned to the partial sequence


- Askin/Standridge (1983), Abschnitt 8.3

Copyright ©2006 POM Prof. Tempelmeier GmbH All rights reserved. | About Us | Contact | Impressum |