ShiromaEfficient Production Planning and Scheduling

GABLER EDITION WISSENSCHAFT Information Engineering und IV -Control I i ng Herausgegeben von Professor Dr. Franz Lehner

Die Schriftenreihe prasentiert aktuelle Forschungsergebnisse der Wirtschaftsinformatik sowie interdisziplinare Ansatze aus Informatik und Betriebswirtschaftslehre. Ein zentrales Anliegen ist dabei die Pfiege der Verbindung zwischen Theorie und Praxis durch eine an­wendungsorientierte Darstellung sowie durch die Aktualitat der Bei­trage. Mit der inhaltlichen Orientierung an Fragen des Information Engineerings und des IV-Controllings 5011 insbesondere ein Beitrag zur theoretischen Fundierung und Weiterentwicklung eines wichtigen Teilbereichs der Wirtsc~aftsinformatik geleistet werden.

Patricia Jay Shiroma

Efficient Production Planning and Scheduling An Integrated Approach with Genetic Algorithms and Simulation

With a Foreword by Prof. Dr. Gerhard Niemeyer

Springer Fachmedien Wiesbaden GmbH

Die Deutsche Bibliothek - C1P-Einheitsaufnahme

Shiroma, Patricia Jay:Efficient production planning and scheduling : on integ rotedapproach with genetic algorithms and simulation/ Patricia Jay Shiroma . W ith a foreword by Gerhard Niemeyer.- Wiesbaden : Dt. Univ.-Verl. ; Wiesbaden : Gabler, 1996(Gabler Edition Wissenschaft : Information Engineeringund IV-Controlling)Zugl.: Regensburg, Univ., Diss., 1996

Gabler Verlag , Deutscher Universitäts-Verlag, Wiesbaden

© Springer Fachmedien Wiesbaden 1996Ursprünglich erschienen bei Betriebswirtschaftlicher Verlag Dr. Th. Gabler GmbH, Wiesbaden 1996.

Lektorat: Cloudia Splittgerber

Dos Werk einschließlich oller seiner Teile ist urheberrechtlich geschützt.Jede Verwertung außerhalb der engen Grenzen des Urheberrechtsge­setzes ist ohne Zustimmung des Verlages u.(lzulässig und strafbar. Dosgilt insbesondere für Vervielfältigungen, Ubersetzungen, Mikroverfil­mungen und die Einspeicheru ng uno Verarbeitung in elektronischenSystemen.

Höchste inhaltliche und technische Qualität unserer Produkte ist unser Ziel. Bei der Produktion undAuslieferung unserer Bücher wollen wir die Umwelt schonen : Dieses Buch ist auf säurefreiem undchlorfrei gebleichtem Papier gedruckt.

Die W iedergabe von Gebrauchsnomen, Handelsnomen, Warenbezeichnungen usw. in diesemWerk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, daß solche Namenim Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten wärenund daher von jedermann benutzt werden dürften.

ISBN 978-3-8244-6426-5 ISBN 978-3-663-08438-9 (eBook)DOI 10.1007/978-3-663-08438-9

Foreword

Production scheduling with resource allocation is a highly complex planning process. In addition to evaluating the large number of possible job sequences, a number of other variables must also be considered. Machine capacities, availability of personnel and material, delivery deadlines as well as penalty costs for missed deadlines must all be taken into account.

Most of the competing theoretical methods used today make a number of unrealistic assumptions in order to simplify the problem. Although the resulting models can be solved mathematically, they are often so constrained that they no longer reflect reality and are therefore unusable in practice.

This work presents an original solution to the problem of production scheduling with simultaneous resource allocation. The interactive integration of genetic algorithms with system simulation makes it possible to handle the complexity inherent to this planning problem without losing information. Furthermore, the combination of a genetic algorithm with tabu search represents a further innovation which improves efficiency of the search process. Finally, the introduction of an adaptive mutation controller prevents the algorithm from stagnating at local optima. The effectiveness of these methods is tested on an application to generate production schedules for an actual manufacturing firm with large numbers of job orders.

Gerhard Niemeyer Regensburg, Germany

v

Preface

This dissertation investigates the possibility of combining genetic algorithms and simulation studies to generate improved production plans for job-based manufacturing processes. A genetic algorithm is a type of search method based on principles of natu­ral selection and evolution. Simulation has proven highly effective in modeling the complexity inherent to dynamic, non-linear systems. The integration of genetic algo­rithms with simulation studies takes advantage of the synergistic effects between the two methods and results in a flexible, highly effective production scheduling system.

First, the problem of job-oriented production planning and scheduling is formally de­fined. Next, the advantages and disadvantages of existing methods to solve this prob­lem are evaluated. The combination of genetic algorithms with simulation is proposed as a new solution. The nature and theoretical foundations of genetic algorithms are discussed in detail. New methods for the hybridization of genetic algorithms with simulation studies are introduced. The feasibility of embedding genetic algorithms within the AMTOS simulation system is investigated. The results of an actual case study applying a hybrid system of genetic algorithms with simulation in order to im­prove production planning for a large pharmaceutical firm are presented. Finally, plans for future research are discussed.

Acknowledgements

I would like to thank my dissertation advisors at the University of Regensburg, Prof. Dr. Gerhard Niemeyer and Prof. Dr. Dieter Bartmann, for their valuable guidance and helpful suggestions during the both development phase and through the review process. I also thank the editor of this series, Prof. Dr. Franz Lehner of the University of Regensburg, for his assistance in the publication of this work.

I would like to express my gratitude to Prof. Fred Glover, Prof. James Kelly and Prof. Manuel Laguna, of the University of Colorado at Boulder, for their expert advice and assistance in the area of tabu search.

VII

I am grateful for the editorial assistance provided by Ms. Claudia Splitgerber at Gabler-Verlag in the completion of this book.

I thank Brett Tanaka, of the Hawaii Pacific University, for his help in reviewing and proofreading the manuscript.

I thank my colleagues at the Institute for Business Informatics, Michael Bosch, Chris­tine Handl, Werner Hopf, Claus Lindenau, Norbert Meck! and Veronika Wolf, for their continued encouragement and thought-provoking discussions.

Special thanks go to my partner and best friend, Matthias Brockmann, for his under­standing and tolerance on the long and often difficult road to completing this disserta­tion.

Finally, I would like to thank my entire family for their inexhaustible encouragement and moral support; This book is dedicated to my parents.

VIII

Patricia Jay Shiroma Regensburg, Germany

Table of Contents

Introduction ................................................................................................................. 1 1.1 Motivation .......................................................................................................... 1 1.2 Problem Definition and Extensions ................................................................... 5

1.2.1 Definition of the Standard Job-Based Production Planning Problem ..... 5 1.2.2 Deficiencies in the Standard Problem Definition .................................... 6

1.2.2.1 Time-Cost Tradeoffs .................................................................. 6 1.2.2.2 Time Aspect of Dynamic Resource Allocation .......................... 7

1.2.3 Expanded Problem Definition ................................................................. 8 1.3 Failure of Traditional Operations Research Methods to Solve Problems

with Nonlinear Dependencies 1.3.1 Linear Programming 1.3.2 Hillclimbing Methods

9

9 9

1.4 Simulation ........................................................................................................ 11 1.5 Cybernetic System Theory ............................................................................... 12

1.5.1 Automata Theory ................................................................................... 13 1.5.2 Cybernetics ............................................................................................ 15

1.6 Generation of Input Parameters for Simulation Studies .................................. 16 1.6.1 Simple Heuristics .................................................................................. 16 1.6.2 Nearest Neighbor. .................................................................................. 16 1.6.3 Balancing Machine Load ...................................................................... 18 1.6.4 Expert Systems ...................................................................................... 19 1.6.5 Enumeration 21 1.6.6 Dynamic Programming ......................................................................... 22 1.6.7 Branch and Bound ................................................................................. 24 1.6.8 Simulated Annealing ............................................................................. 29

2 The Nature of Evolutionary Algorithms ................................................................... 33 2.1 Evolutionary Programming .............................................................................. 35 2.2 Evolutionary Strategies .................................................................................... 36 2.3 Genetic Algorithms .......................................................................................... 37

2.3.1 Selection ................................................................................................ 38 2.3.2 Crossover ............................................................................................... 39 2.3.3 Mutation ................................................................................................ 40 2.3.4 Convergence .......................................................................................... 41 2.3.5 Example of a Genetic Algorithm in Pseudo-Pascal .............................. 42

IX

3 Theoretical Foundations of Genetic Algorithms ....................................................... 43 3.1 Schema Theorem .............................................................................................. 43

3.1.1 Schemata 44 3.1.2 Upper and Lower Bounds on the Number of Schemata Evaluated ....... 45 3.1.3 Hyperplane Sampling ............................................................................ 45 3.1.4 Effects of Fitness Proportional Reproduction ....................................... 47 3.1.5 Effects of Crossover .............................................................................. 49 3.1.6 Effects of Mutation ............................................................................... 50 3.1.7 Schema Theorem Summarized .............................................................. 51

3.2 The Building Block Hypothesis ....................................................................... 52 3.3 Interacting Roles of Crossover and Mutation .................................................. 54 3.4 Self-Organizing Systems and Artificial Life .................................................... 55

3.4.1 Artificial Life ........................................................................................ 55 3.4.2 The Game of Life .................................................................................. 56 3.4.3 Manipulation of DNA to Solve Combinatorial Problems ..................... 57 3.4.4 Generation of Computer Programs with Natural Selection .................. 59 3.4.5 Sirriulation of a Market Economy with Autonomous Agents ............... 61

4 Methodology ............................................................................................................. 63 4.1 Classic vs. Hybrid Genetic Algorithms ............................................................ 65 4.2 Time Constraints when Combining Genetic Algorithms with Simulation ...... 66

4.2.1 Minimization of the Number of Simulation Runs ................................. 67 4.2.1.1 Delta Evaluation ....................................................................... 68 4.2.1.2 Messy Genetic Algorithms ....................................................... 68 4.2.1.3 Chromosome Representation ................................................... 69

4.2.1.3.1 Binary vs. Real Coding Schemes .............................. 69 4.2.1.3.2 Hierarchical, Dynamic Data Structure ...................... 71

4.2.1.4 Modification of Genetic Operators .......................................... 73 4.2.1.4.1 Selection .................................................................... 73

4.2.1.4.1.1 Generational vs. Steady State Algorithms ........................ 74

4.2.1.4.1.2 Fitness Proportional vs. Rank-Based Selection 75

4.2.1.4.2 Modifications to the Crossover Operator ................. 77 4.2.1.4.2.1 Multi-Point Crossover ........................... 77 4.2.1.4.2.2 Uniform Crossover. ............................... 78 4.2.1.4.2.3 Intelligent Crossover ............................. 79 4.2.1.4.2.4 Order Crossover 80

x

4.2.1.4.3 Order-Based Mutation 81 4.2.1.5 Adaptive Feedback Controller to Vary Mutation Rate ............ 82 4.2.1.6 Tabu List of Previously Evaluated Schedules .......................... 85

4.2.2 Minimization of the Processing Time for Each Simulation .................. 86 4.2.2.1 Simulation Model ..................................................................... 86

4.2.2.1.1 Petri-Nets .................................................................. 87 4.2.2.1.2 Dynamic Agents ............ ; ........................................... 88

4.2.2.2 Hierarchical, Dynamic Data Structure ..................................... 89

4.3 Multiobjective Fitness Function ....................................................................... 91 4.3.1 Hard Constraints .................................................................................... 91 4.3.2 Soft Constraints ..................................................................................... 92 4.3.3 Competing Objectives: Minimization of Time and/or Costs .............. 93

5 Feasibility Study: A Hybrid Genetic Algorithm Embedded in AMTOS .................. 97 5.1 AMTOS Simulation Software .......................................................................... 97 5.2 Feedback Loop Between AMTOS and the Genetic Algorithm ....................... 97 5.3 First Experiments with Small Problems ........................................................... 99 5.4 Results ............................................................................................................ 101 5.5 Conclusions .................................................................................................... 102

6 Case Study: Implementation of a Hybrid Genetic Algorithm for Production Planning in a Large Pharmaceutical Company ..................................... 105 6.1 Problem Description ....................................................................................... 105 6.2 Hybridization .................................................................................................. 107

6.2.1 DISYS Object-Oriented Data Management and Logistics System ..... 107 6.2.2 AMTOS Simulation System ................................................................ 110 6.2.3 Genetic Algorithm ............................................................................... 110

6.3 Comparison of Two Different Types of Genetic Algorithms ........................ 113 6.3.1 Genetic Algorithm Type 1.. ................................................................. 113

6.3.1.1 Convergence Rate .................................................................. 114 6.3.1.2 Mutation Rate ......................................................................... 115 6.3.1.3 Optimization According to Different Goals ........................... 116

6.3.2 Genetic Algorithm Type 2 (with Tabu List) ....................................... 117 6.3.2.1 Convergence Rate .................................................................. 118 6.3.2.2 Mutation Rate ......................................................................... 119 6.3.2.3 Optimization According to Different Goals ........................... 120

XI

6.4 Comparison to Other Stochastic Optimization Methods ................................ 121 6.4.1 Monte Carlo Random Search .............................................................. 122 6.4.2 Tabu Search ......................................................................................... 123 6.4.3 Evolutionary Strategy .......................................................................... 125

6.5 Results 6.6 Conclusions

7 Summary and Plans for Future Research 7.1 Summary

126 134

137 137

7.2 Plans for Future Research .............................................................................. 138 7.2.1 Seeded Genetic Algorithms ................................................................. 138 7.2.2 Rescheduling ....................................................................................... 139 7.2.3 Parallel Genetic Algorithms ................................................................ 139 7.2.4 Fuzzy Logic Fitness Functions ............................................................ 141 7.2.5 Self-Organizing Systems: Autonomous Agents ................................. 142

Bibliography 143

XII

List of Figures

1.1 Computer Integrated Management System .......................................................... 3 1.2 The Role of CIM in an Integrated Management System ...................................... 4 1.3 Processing Path for 1 Job ..................................................................................... 5 1.4 Hillclimbing Algorithm ...................................................................................... 10 1.5 Multimodal Search Space ................................................................................... 11 1.6 Simple Automaton .............................................................................................. 13 1.7 Networks of Automata ....................................................................................... 14 1.8 Feedback Controller ........................................................................................... 15 1.9 Dynamic Programming ....................................................................................... 23 1.10 Branch and Bound - Node 1 ............................................................................... 25 1.11 Branch and Bound - Node 2 ............................................................................... 26 1.12 Branch and Bound - Node 4 1.13 Branch and Bound - Final Tree 1.14 Simulated Annealing 1.15 Simulated Annealing of a Multimodal Function

2.1 Randomly Generated Initial Population

27 28 29 30

38 2.2 Population Convergence ..................................................................................... 41

3.1 Visualization of Schemata as Hyperplanes in 3-Dimensional Space ................. 46 3.2 Genetic Hierarchy ............................................................................................... 53 3.3 Glider Propagating Through an Array of Cellular Automata ............................. 57 3.4 Genetic Programming ......................................................................................... 59 3.5 Crossover Operator in Genetic Programming .................................................... 60 3.6 Resulting Offspring ............................................................................................ 60

4.1 Hybrid System Combining Genetic Algorithms with Simulation ...................... 64 4.2 Hierarchical, Dynamic Data Structure for Chromosome Representation .......... 72 4.3 Order-Based Mutation ........................................................................................ 82 4.4 Adaptive Feedback Controller ............................................................................ 83 4.5 Deceptive Problem ............................................................................................. 84 4.6 Petri-Net Based Simulation ModeL .................................................................. 87 4.7 Simulation Model with Dynamic Agents ........................................................... 88 4.8 Simulation List for 1 Member of the Population 90

XIII

5.1 5.2 5.3 5.4

6.1 6.2 6.3 6.4

Hybrid System with Genetic Algorithm and AMTOS AMTOS Simulation Model

98 99

Differing Results for Costs When Costs or Time Optimized ........................... 101 Differing Results for Times When Costs or Time Optimized .......................... 102

Processing Sequence of Tasks for 2 Jobs ......................................................... 106 DrSYS Telecommunications for Data Acquisition and Distribution ............... 108 Generation of an Operations Plan .................................................................... 109 Hybrid System Combining DISYS, AMTOS & Genetic Algorithm ............... 111

6.5 Hierarchical, Dynamic Data Structure 112 114 6.6 Population Convergence for Genetic Algorithm Type 1

6.7 Dynamic Variation of Mutation Rate for Genetic Algorithm Type 1 .............. 115 6.8 Variation in Processing Time With Different Optimization Goals - GA 1 ...... 116 6.9 Variation in Processing Costs With Different Optimization Goals - GA 1 ..... 117 6.10 Population Convergence for Genetic Algorithm Type 2 .................................. 118 6.11 Dynamic Variation of Mutation Rate for Genetic Algorithm Type 2 .............. 119 6.12 Variation in Processing Time With Different Optimization Goals - GA 2 ...... 120 6.13 Variation in Processing Costs With Different Optimization Goals - GA 2 ..... 121 6.14 Convergence of Elements in Tabu List.. .......................................................... 124 6.15 Times for Best Schedules Over 500 Generations- Time Optimized ................ 127 6.16 Corresponding Costs for Schedules with Best Times - Time Optimized ......... 127 6.17 Costs for Best Schedules Over 500 Generations - Costs Optimized ................ 128 6.18 Corresponding Times for Schedules with Best Costs - Costs Optimized ........ 128 6.19 Best Times Found After 500 Generations - Time Optimized .......................... 129 6.20 Corresponding Costs for Schedules with Best Times - Time Optimized ......... 129 6.21 Best Costs Found After 500 Generations - Costs Optimized ........................... 130 6.22 Corresponding Times for Schedules with Best Costs - Costs Optimized ........ 130 6.23 Times of Best Schedules - Both Time and Costs Optimized ........................... 131 6.24 Costs of Best Schedules - Both Time and Costs Optimized 6.25 Times of Best Schedules Found After 500 Generations

Both Time and Costs Optimized 6.26 Costs of Best Schedules Found After 500 Generations

131

132

Both Time and Costs Optimized ...................................................................... 132 6.27 Relative Fitness of Five Optimization Methods ............................................... 134

7.1 Genetic Algorithm Seeded by an Expert System ............................................. 138 7.2 Parallel Genetic Algorithm ............................................................................... 140

XIV