GA & SCHEDULING BOOK AVAILABLE


Subject: GA & SCHEDULING BOOK AVAILABLE
From: Dirk Mattfeld (dirk@medusa.fb7.uni-bremen.de)
Date: Tue Apr 16 1996 - 15:37:02 MET DST


[posting to several mailing lists -- apologies to those who,
 by subscribing to multiple lists, receive multiple copies.]

BOOK ANNOUNCEMENT
-----------------

Title: Evolutionary Search and the Job Shop;
           Investigations on Genetic Algorithms
           for Production Scheduling

Author: Dirk C. Mattfeld

Series: Production and Logistics

Editors: Horst Tempelmeier, University of Cologne

           Wolfgang Domschke, University of Darmstadt
           Andreas Drexl, University of Kiel
           Bernhard Fleischmann, University of Augsburg
           Hans-Otto Guenther, University of Berlin
           Hartmut Stadtler, University of Darmstadt

Publisher: Springer/Physica Verlag, Heidelberg

Pages: X, 152 pp., 62 figs., 30 tabs.

Available: March 96, ISBN 3-7908-0917-9

Price: DM 75.00, approx. USD 50.00

Order: http://medusa.fb7.uni-bremen.de/Leute/dirk.html

PREFACE
-------

   Production planning and control systems suffer from insufficient
computational support in the field of production scheduling.
Practical requirements dictate highly constrained mathematical models
with complex and often contradicting objectives. Therefore scheduling
even in computerized manufacturing systems still relies on simple
priority rule based heuristics. Thus, we can expect a great so far
unexploited optimization potential in manufacturing environments.

   Within the last decade academic research in scheduling has gained a
significant progress due to modern Local Search based heuristics.
Much effort has been put into suitable neighborhood definitions which
go for the key feature of Local Search. However, it remains
questionable whether this work can be transferred in order to fit the
flexible requirements of production scheduling.

   Evolutionary Algorithms can be formulated almost independently of
the detailed shaping of the problems under consideration. As one
would expect, a weak formulation of the problem in the algorithm comes
along with a quite inefficient search. Nevertheless, for practical
requirements the advantage of constraint and objective independence is
most obvious.

   In this book Evolutionary Algorithms are applied to the Job Shop
Scheduling Problem. The problem is analyzed and a survey is given on
conventional solution techniques and recent Local Search approaches.
Evolutionary Algorithms and their appliance to combinatorial problems
are covered. Then, a search space analysis for the Job Shop Problem
is performed before a Genetic Algorithm is developed. Finally, this
algorithm is refined resulting in a parallel genetic search approach.

   The benefit of this book is twofold. It gives a comprehensive
survey of recent advances for both, production scheduling and
Evolutionary Algorithms in the didactic way of a textbook. Moreover,
it presents an efficient and robust optimization strategy which can
cope with varying constraints and objectives of real world scheduling
problems.

TABLE OF CONTENTS
-----------------

1. Introduction .............................................. 1
    1.1 Production Planning .................................. 1
    1.2 Production Scheduling ................................ 3
    1.3 Heuristic Search ..................................... 4

2. Job Shop Scheduling ........................................ 7
    2.1 Representation of the JSP ............................ 7
    2.2 Schedule Generation Techniques ....................... 17
    2.3 Enumeration Methods .................................. 22

3. Local Search Techniques ................................... 27
    3.1 Neighborhood Definitions .............................. 28
    3.2 Local Hill Climbing .................................. 37
    3.3 Local Search Extensions .............................. 44

4. Evolutionary Algorithms .................................... 49
    4.1 The Evolutionary Metaphor ............................ 49
    4.2 Adaptation in Epistatic Domains ...................... 54
    4.3 Genetic Hybrids ...................................... 60

5. Perspectives on Adaptive Scheduling ....................... 65
    5.1 Configuring the Solution Space ....................... 65
    5.2 Properties of the Search Space ....................... 75
    5.3 Summary of Perspectives .............................. 90

6. Population Flow in Adaptive Scheduling .................... 93
    6.1 Genetic Algorithm Template ........................... 95
    6.2 Inheritance Management ............................... 96
    6.3 Population Management .................................104
    6.4 Applying Adaptive Scheduling .........................108

7. Adaptation of Structured Populations ......................113
    7.1 Finite and Structured Populations ....................114
    7.2 Inheritance of Attitudes .............................123

8. A Computational Study .....................................133
    8.1 Survey of the GA-Approaches ..........................133
    8.2 Benchmark Study ......................................136

9. Conclusions and Outlook ...................................145
    9.1 The Real World is Different ...........................145
    9.2 GAs and Real World Scheduling .........................147

References .....................................................149

Best regards,

----
Dr. Dirk C. Mattfeld

University of Bremen Tel: +49-421-218-2011 Dept. of Economics Fax: +49-421-218-4271 Post Box 33 04 40 Email: dirk@fb7.uni-bremen.de D-28334 Bremen, Germany Web: medusa.fb7.uni-bremen.de



This archive was generated by hypermail 2b25 : Fri Mar 03 2000 - 16:17:09 MET