Operations sequencing with sequencedependent setup costs/times
For a given set of jobs to be performed on a single machine with sequencedependent
setup costs or setup times a sequence is determined with the help of the closestinsertion
or, alternatively, the farthestinsertation heuristic.
The sequencing problem is modeled as a travelingsalesmanproblem (TSP) with
each job being a node in the TSPnetwork 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 
ixxx 
job i is already assigned to the partial sequence 
Literature:
 Askin/Standridge
(1983), Abschnitt 8.3
