Lecture Notes in Artificial Intelligence Subseries of Lecture Notes in Computer Science Edited by J. G. Carbonell and J. Siekmann
Lecture Notes in Computer Science Edited by G. Goos, J. Hartmanis, and J. van Leeuwen
2148
3
Berlin Heidelberg New York Barcelona Hong Kong London Milan Paris Tokyo
Alexander Nareyek (Ed.)
Local Search for Planning and Scheduling ECAI 2000 Workshop Berlin, Germany, August 21, 2000 Revised Papers
13
Series Editors Jaime G. Carbonell, Carnegie Mellon University, Pittsburgh, PA, USA J¨org Siekmann, University of Saarland, Saarbr¨ucken, Germany Volume Editor Alexander Nareyek GMD FIRST Kekuléstr. 7, 12489 Berlin, Germany E-mail:
[email protected]
Cataloging-in-Publication Data applied for Die Deutsche Bibliothek - CIP-Einheitsaufnahme Local search for planning and scheduling : revised papers / ECAI 2000 Workshop, Berlin, Germany, August 21, 2000. Alexander Nareyek (ed.). Berlin ; Heidelberg ; New York ; Barcelona ; Hong Kong ; London ; Milan ; Paris ; Tokyo : Springer, 2001 (Lecture notes in computer science ; Vol. 2148 : Lecture notes in artificial intelligence)
CR Subject Classification (1998): I.2.8, F.2.2, G.1.6, G.2.2 ISBN 3-540-42898-4 Springer-Verlag Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law. Springer-Verlag Berlin Heidelberg New York a member of BertelsmannSpringer Science+Business Media GmbH http://www.springer.de © Springer-Verlag Berlin Heidelberg 2001 Printed in Germany Typesetting: Camera-ready by author, data conversion by PTP-Berlin, Stefan Sossna Printed on acid-free paper SPIN: 10845478 06/3142 543210
Preface
With the increasing deployment of planning and scheduling systems, developers often have to deal with very large search spaces, real-time performance demands, and dynamic environments. Complete refinement methods do not scale well, making local search methods the only practical alternative. A dynamic environment also promotes the application of local search, the search heuristics not normally being affected by modifications of the search space. Furthermore, local search is well suited for anytime requirements because the optimization goal is improved iteratively. Such advantages are offset by the incompleteness of most local search methods, which makes it impossible to prove the inconsistency or optimality of the solutions generated. Popular local search approaches include evolutionary algorithms, simulated annealing, tabu search, min-conflicts, GSAT, and Walksat. The first article in this book – an invited contribution by Stefan Voß – gives an overview of these methods. The book is based on the cont