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.
Symbols:
| 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 |
Literature:
- Askin/Standridge
(1983), Abschnitt 8.3
|
