《1995 Insertion techniques for the heuristic solution of the job shop problem》.pdf

DISCRETE APPLIED MATHEMATICS F3swIER Discrete Applied Mathematics 58 (1995) 191-211 Insertion techniques for the heuristic solution of the job shop problem Frank Werner, Andreas Winkler Fakultiitfiir Mathematik, Technische Universitiit “Otto von Guericke”, PSF 4120, 39016 Magdeburg, Germany Received 7 January 1992;revised 20 November 1992 Abstract In this paper we 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 we successively insert the operations into feasible partial schedules. In the iterative phase we generate paths in a particular neighbourhood graph instead of investigating the neighbourhood completely. To select “interesting” neighbours, we use the combinatorial path structure of feasible solutions of the job shop problem. The results of our algorithm are compared with those from other well-known methods on benchmark problems. Keywords: Scheduling; Job shop problem; Neighbourhood heuristics; Insertion algorithm; Path search 1. Introduction In this paper the classical job shop problem is considered. n jobs J1, J2, .. . ,Jn have to be processed on m machines Ml, M,, . . ., M,,,. Each job consists of several opera- tions where the op