Insertion techniques for the heuristic solution of the job shop problem

In this paper the authors deal with the heuristic solution of the classical job shop problem. Both the constructive and the iterative phase of our algorithm apply insertion techniques combined with beam search. In the first phase they successively insert the operations into feasible partial schedules. In the interactive phase the authors generate paths in a particular neighbourhood graph instead of investigating the neighbourhood completely. To select ‘interesting’ neighbours, they use the combinatorial path structure of feasible solutions of the job shop problem. The results of the algorithm are compared with those from other well-known methods on benchmark problems.