Preview
Unable to display preview. Download preview PDF.
References
E.H.L. Aarts and J. Korst (1989) Simulated Annealing and Boltzmann Machines. John Wiley and Sons, Chichester.
E.H.L. Aarts, P.J.M. van Laarhoven, J.K. Lenstra and N.L.J. Ulder (1994) A computational study of local search algorithms for job shop scheduling. ORSA Journal on Computing 6, 118–125.
J. Adams, E. Balas, and D. Zawack (1988) The shifting bottleneck procedure for job shop scheduling. Management Science 34, 391–401.
K.R. Baker (1974) Introduction to Sequencing and Scheduling. Wiley, New York.
P. Brucker, J. Hurink and F. Werner (1993) Improving local search heuristics for some scheduling problems. Working paper, University of Osnabrück, Discrete Applied Meth. (to appear).
P. Brucker, J. Hurink and F. Werner (1994) Improving local search heuristics for some scheduling problems, Part II. Working paper, University Osnabrück.
V. Cerny (1985) Thermodynamical approach to the traveling salesman problem; an efficient simulation algorithm. Journal of Optimization Theory and Application 45, 41–51.
L. Davis (1985) Job shop scheduling with genetic algorithms. Proc. an Int. Conf. Genetic Algorithms and Their Applications (J.J. Grefenstette, ed.), Lawrence Erlbaum Ass., 136–140.
M. Dell'Amico and M. Trubian (1993) Applying tabu-search to the job shop scheduling problem. Annals of Operations Research 41, 231–252.
U. Dorndorf and E. Pesch (1995) Evolution based learning in a job shop scheduling environment. Computers & Operations Research 22, 25–40.
A.E. Eiben, E.H.L. Aarts and K.H. van Hee (1991) Global convergence of genetic algorithms: a Markov Chain analysis. Proc. 1st. Int. Workshop on Parallel Problem Solving from Nature (H.-P. Schwefel and R. Männer, eds.), Lecture Notes in Computer Science 496, 4–9.
S. French (1982) Sequencing and Sheduling: An Introduction to the Mathematics of the Job Shop. Wiley, New York.
C.A. Glass, C.N. Potts and P. Shade (1992) Genetic algorithms and neighbouhood search for scheduling unrelated parallel machines. Working paper, University of Southampton.
F. Glover (1977) Heuristic for integer programming using surrogate constraints. Decision Sciences 8, 156–160.
F. Glover (1986) Future paths for integer programming and links to artificial intelligence. Computers and Operations Research 13, 533–549.
F. Glover (1989) Tabu Search-Part I. ORSA Journal on Computing 1, 190–206
F. Glover (1990) Tabu Search-Part II. ORSA Journal on Computing 2, 4–32.
F. Glover (1991) Multilevel tabu search and embedded search neighbourhoods for the traveling salesman problem. Working paper, University of Colorado, Boulder.
F. Glover (1992) Ejection chains, reference structures and alternating path methods for traveling salesman problems. Working paper, University of Colorado, Boulder.
F. Glover and H.J. Greenberg (1989) New approaches for heuristic search: A bilateral linkage with artificial intelligence. European Journal of Operational Research 13, 119–130.
F. Glover and C. McMillan (1986) The general employee scheduling problem: an integration of MS and AI. Computers and Operations Research 13, 563–573.
D.E. Goldberg (1989a) Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading.
D.E. Goldberg (1989b) Zen and the art of genetic algorithms. Proc. 3rd Int. Conf. Genetic Algorithms (J.D. Schaffer, ed.), Morgan Kaufmann Publ. 80–85.
M. Gorges-Schleuter (1989) ASPARAGOS, a parallel genetic algorithm and population genetics. Proc. 3rd Int. Conf. Genetic Algorithms (J.D. Schaffer, ed.), Morgan Kaufmann Publ., 422–427.
J.J. Grefenstette (1987) Incorporating problem specific knowledge into genetic algorithms. Genetic algorithms and simulated annealing (L. Davis, ed.), Pitman, 42–60.
J.J. Grefenstette, R. Gopal, B. Rosmaita, and D. van Gucht (1985) Genetic algorithms for the traveling salesman problem. Proc. 1st. Int. Conf. Genetic Algorithms and their Applications (J.J. Grefenstette, ed.), Lawrence Erlbaum Ass., 160–168.
M. Grötschel and O. Holland (1991) Solution of large-scale symmetric travelling salesman problems. Math. Programming 51, 141–202.
P. Hansen, and B. Jaumard (1990) Algorithms for the maximum satisfiability problem, Computing 44, 279–303.
A. Hertz and D. de Werra (1987) Using tabu search techniques for graph coloring. Computing 39, 345–351.
A. Hertz and D. de Werra (1990) The tabu search metaheuristic: How we use it. Annals of Math. and Artificial Intelligence 1, 111–121.
J.H. Holland (1975) Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor.
P. Jog, J.Y. Suh, and D. van Gucht (1989) The effects of population size, heuristic crossover and local improvement on a genetic algorithm for the traveling salesman problem. Proc. 3rd. Int. Conf. Genetic Algorithms (J.D. Schaffer, ed.), Morgan Kaufmann Publ., 110–115.
D.S. Johnson (1990) Local optimization and the traveling salesman problem. Proc. 17th Colloq. Automata, Languages, and Programming, Springer-Verlag, 446–461.
D.S. Johnson, C.R. Aragon, L.A. McGeoch, and C. Schevon (1989) Optimization by simulated annealing: An experimental evaluation; Part I, Graph partitioning. Operations Research 37, 865–892.
D.S. Johnson, C.R. Aragon, L.A. McGeoch and C. Schevon (1989) Optimization by simulated annealing: An experimental evaluation; Part II, Graph coloring and number partitioning. Operations Research 39, 378–406.
D.S. Johnson, C.H. Papadimitriou, and M. Yannakakis (1988) How easy is local search? J. Computer System Sci. 37, 79–100.
S. Kirkpatrick, C.D. Gelatt Jr., and M.P. Vecchi (1983) Optimization by simulated annealing. Science 220, 671–680.
A. Kolen and E. Pesch (1994) Genetic local search in combinatorial optimization. Discrete Applied Mathematics 48, 273–284.
P.J.M. van Laarhoven and E.H.L. Aarts (1987) Simulated Annealing: Theory and Applications. Reider, Dordrecht.
P.J.M. van Laarhoven, E.H.L. Aarts, and J.K. Lenstra (1992) Job shop scheduling by simulated annealing. Operations Research 40, 113–125.
E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shoys (eds.) (1985) The Traveling Salesman Problem. John Wiley and Sons.
G.E. Liepins and M.R. Hilliard (1989) Genetic Algorithms: foundations and applications. Annals of Operations Research 21, 31–57.
S. Lin and B.W. Kernighan (1973) An effective heuristic algorithm for the Traveling Salesman Problem. Operations Research 21, 498–516.
Z. Michalewitcz (1992) Genetic Algorithms + Data Structures = Evolution Programs. Springer, Berlin.
M. Malek, M. Guruswamy, M. Pandya, and H. Owens (1989) Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem. Linkages with Artificial Intelligence (F. Glover and H.J. Greenberg, eds.) Annals of Operations Research 21, 59–84.
H. Matsuo, C.J. Suh, and R.S. Sullivan (1988) A controlled search simulated annealing method for the general jobshop scheduling problem. Working paper 03-04-88, Department of Management, University of Texas, Austin.
N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, and E. Teller (1953) Equation of state calculations by fast computing machines. Journal of Chemical Physics 21, 1087–1092.
H. Mühlenbein (1989) Parallel genetic algorithms, population genetics and combinatorial optimization. Proc. 3rd Conf. Genetic Algorithms (J.D. Schaffer, ed.), Morgan Kaufmann Publ., 416–421.
H. Mühlenbein, M. Gorges-Schleuter, and O. Krämer (1987) New solutions to the mapping problem of parallel systems: the evolution approach. Parallel Computing 4, 269–279.
H. Mühlenbein, M. Gorges-Schleuter, and O. Krämer (1988) Evolution algorithms in combinatorial optimization. Parallel Computing. 7, 65–85.
E. Nowicki and C. Smutnicki (1993) A fast taboo search algorithm for the job shop problem. Working paper, Technical University of Wroclaw.
S.S. Panwalkar and W. Iskander (1977) A survey of scheduling rules. Operations Research 25, 45–61.
E. Pesch and S. Voß, eds. (1995) Applied Local Search. OR Spektrum (special issue, to appear).
I. Rechenberg (1973) Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Problemata, Frommann-Holzboog.
B. Roy and B. Sussman (1964) Les problèmes d'ordonnancement avec contraintes disjonctives. SEMA, Note D.S. No. 9., Paris.
H.-P. Schwefel (1977) Numerische Optimierung von Computer-Modellen mittels der Evolutionsstrategie. Birkhäuser Basel.
W.E. Smith (1956) Various optimizers for single-stage production. Naval Research Logistics Quarterly 3, 59–66.
J.Y. Suh and D. van Gucht (1987) Incorporating heuristic information into genetic search. Proc. 2nd Int. Conf Genetic Algorithms (J.J. Grefenstette, ed.), Lawrence Erlbaum Ass. 100–107.
E. Taillard (1994) Parallel taboo search technique for the job shop scheduling problem. ORSA Journal On Computing 6, 108–117.
N.L.J. Ulder, E.L. Aarts, H.-J. Bandelt, P.J.M. van Laarhoven, and E. Pesch (1991) Genetic local search algorithms for the traveling salesman problem. Proc. 1st. Int. Workshop on Parallel Problem Solving from Nature (H.-P. Schwefel and R. Männer, eds.), Lecture Notes in Computer Science 496, 109–116.
M. Widmer (1991) Job shop scheduling with tooling constraints: a tabu search approach. J. Operational Research Society 42, 75–82.
M. Yannakakis (1990) The analysis of local search problems and their heuristics. Proc. 7th. Annual Symposium on Theoretical Aspects of Computer Science (C. Choffrut and T. Lengauer, eds.). Lecture Notes in Computer Science 415, 298–311.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Crama, Y., Kolen, A.W.J., Pesch, E.J. (1995). Local search in combinatorial optimization. In: Braspenning, P.J., Thuijsman, F., Weijters, A.J.M.M. (eds) Artificial Neural Networks. Lecture Notes in Computer Science, vol 931. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0027029
Download citation
DOI: https://doi.org/10.1007/BFb0027029
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-59488-8
Online ISBN: 978-3-540-49283-2
eBook Packages: Springer Book Archive