1. Insertion techniques for the heuristic solution of the job shop problem
- Author
-
Frank Werner and Andreas Winkler
- Subjects
Mathematical optimization ,Job shop scheduling ,Neighbourhood heuristics ,Job shop ,Scheduling ,Applied Mathematics ,Insertion algorithm ,Flow shop scheduling ,Neighbourhood graph ,Constructive ,Scheduling (computing) ,Beam search ,Discrete Mathematics and Combinatorics ,Path search ,Algorithm ,Neighbourhood (mathematics) ,Job shop problem ,Mathematics - 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.
- Published
- 1995
- Full Text
- View/download PDF