Insertion techniques for the heuristic solution of the job shop problem. (English) Zbl 0833.90073

Summary: 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.


90B35 Deterministic scheduling theory in operations research
Full Text: DOI


[1] Adams, J.; Balas, E.; Zawack, D., The shifting bottleneck procedure for job shop scheduling, Management Sci., 34, 391-401 (1988) · Zbl 0637.90051
[2] Bräsel, H., Lateinische Rechtecke und Maschinenbelegung, (Dissertation, B (1990), TU Magdeburg)
[3] Bräsel, H.; Tautenhahn, T.; Werner, F., Constructive heuristic algorithms for the open shop problem (1991), TU Magdeburg, preprint · Zbl 0796.90031
[4] Bräsel, H.; Werner, F., The job-shop problem — modelling by latin rectangles, exact and heuristic solution, (Sebastian, H. J.; Tammer, K., System Modelling and Optimization, Proceedings of the 14th IFIP Conference Leipzig (1989)) · Zbl 0704.90049
[5] Brucker, P.; Jurisch, B.; Sievers, B., A fast branch and bound algorithm for the job-shop problem (1990), Universität Osnabrück, preprint
[6] Carlier, J.; Pinson, E., An algorithm for solving the job-shop problem, Management Sci., 35, 164-176 (1989) · Zbl 0677.90036
[7] Florian, M.; Trepant, P.; Mahon, G. Mc, An implicit enumeration algorithm for the machine sequencing problem, Management Sci., 17, B782-B792 (1971) · Zbl 0224.90047
[8] Glover, F., Tabu search — part I, ORSA J. Comput., 1/3, 190-206 (1989) · Zbl 0753.90054
[9] Grabowski, J., A new algorithm of solving the flow-shop problem, (Feichtinger, G.; Kall, P., Operations Research in Progress (1982)), 57-75
[10] Haupt, R., A survey of priority rule-based scheduling, OR Spektrum, 11, 3-16 (1989) · Zbl 0658.90047
[11] Van Laarhoven, P. J.M.; Aarts, E. H.L., Simulated Annealing: Theory and Applications (1987), Reidel: Reidel Dordrecht · Zbl 0643.65028
[12] Lawler, E. L.; Lenstra, J. K.; Kan, A. H.G. Rinnooy; Shmoys, D. B., Sequencing and scheduling: algorithms and complexity, (Report BS-R8909 (1989), Department of Operations Research, Statistics and System Theory)
[13] Muth, J. F.; Thompson, G. L., Industrial Scheduling (1963), Prentice Hall: Prentice Hall Englewood Cliffs, NJ
[14] Nawaz, M.; Enscore, E. E.; Ham, I., A heuristic algorithm for the \(m\)-machine, \(n\)-job flow shop sequencing problem, OMEGA, 11, 91-95 (1983)
[15] Ow, P. S.; Morton, T. E., The single machine early/tardy problem, Management Sci., 35, 177-191 (1989) · Zbl 0666.90043
[16] Rosenkrantz, D. J.; Stearns, R. E.; Lewis, P. M., An analysis of several heuristics for the traveling salesman problem, SIAM J. Comput., 6, 563-581 (1977) · Zbl 0364.90104
[17] Spachis, A. S.; King, J. R., Job-shop scheduling heuristics with local neighbourhood search, Internat. J. Prod. Res., 17, 507-526 (1979)
[18] Werner, F., Zu einigen Nachbarschaftsstrukturen für Iterationsverfahren zur näherungsweisen Lösung spezieller Reihenfolgeprobleme, Wiss. Z. Tech. Univ. Magdeburg, 31, 5, 48-54 (1987)
[19] Werner, F., Zu einigen Nachbarschaftsstrukturen für Iterationsverfahren zur näherungsweisen Lösung spezieller Reihenfolgeprobleme, Optimization, 19, 539-556 (1988) · Zbl 0651.90042
[20] Werner, F., Iterative heuristics for the job-shop problem (1988), TU Magdeburg
[21] Werner, F., Zur Struktur und näherungsweisen Lösung ausgewählter kombinatorischer Optimierungsprobleme, (Dissertation, B (1989), TU Magdeburg)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.