Multiobjective Scheduling by Genetic Algorithms

by Bagchi, Tapan P.

• ISBN13: 9780792385615
• ISBN10: 0792385616
• eBook ISBN(s): 9781461552376
• Format: Hardcover
• Copyright: 1999-09-01
• Publisher: Kluwer Academic Pub
• More Book Details
• Purchase Benefits

Summary

Multiobjective Scheduling by Genetic Algorithms describes methods for developing multiobjective solutions to common production scheduling equations modeling in the literature as flowshops, job shops and open shops. The methodology is metaheuristic, one inspired by how nature has evolved a multitude of coexisting species of living beings on earth. Multiobjective flowshops, job shops and open shops are each highly relevant models in manufacturing, classroom scheduling or automotive assembly, yet for want of sound methods they have remained almost untouched to date. This text shows how methods such as Elitist Nondominated Sorting Genetic Algorithm (ENGA) can find a bevy of Pareto optimal solutions for them. Also it accents the value of hybridizing Gas with both solution-generating and solution-improvement methods. It envisions fundamental research into such methods, greatly strengthening the growing reach of metaheuristic methods. This book is therefore intended for students of industrial engineering, operations research, operations management and computer science, as well as practitioners. It may also assist in the development of efficient shop management software tools for schedulers and production planners who face multiple planning and operating objectives as a matter of course.

Table of Contents

Preface	xi
Shop Scheduling: An Overview	1	(18)
What Is Scheduling?	1	(4)
Machine Scheduling Preliminaries	5	(2)
Intelligent Solutions to Complex Problems	7	(4)
Scheduling Techniques: Analytical, Heuristic and Metaheuristic	11	(4)
Outline of this Text	15	(4)
What are Genetic Algorithms?	19	(36)
Evolutionary Computation and Biology	19	(10)
Working Principles	29	(2)
The Genetic Search Process	31	(4)
The Simple Genetic Algorithm (SGA)	35	(1)
An Application of GA in Numerical Optimization	35	(8)
Genetic Algorithms vs. Traditional Optimization	43	(3)
Theoretical Foundation of GAs	46	(5)
Schema Processing: An Illustration	51	(1)
Advanced Models of Genetic Algorithms	51	(4)
Calibration of GA Parameters	55	(22)
GA Parameters and the Control of Search	55	(5)
The Role of the ``Elite'' who Parent the Next Generation	60	(5)
The Factorial Parametric Study	65	(6)
Experimental Results and Their Interpretation	71	(4)
Chapter Summary	75	(2)
Flowshop Scheduling	77	(32)
The Flowshop	77	(3)
Flowshop Model Formulation	80	(1)
The Two-Machine Flowshop	81	(2)
Sequencing the General m-Machine Flowshop	83	(2)
Heuristic Methods for Flowshop Scheduling	85	(7)
Darwinian and Lamarckian Genetic Algorithms	92	(5)
Flowshop Sequencing by GA: An Illustration	97	(2)
Darwinian and Lamarckian Theories of Natural Evolution	99	(3)
Some Inspiring Results of using Lamarckism	102	(4)
A Multiobjective GA for Flowshop Scheduling	106	(1)
Chapter Summary	107	(2)
Job Shop Scheduling	109	(27)
The Classical Job Shop Problem (JSP)	109	(8)
Heuristic Methods for Scheduling the Job Shop	117	(5)
Genetic Algorithms for Job Shop Scheduling	122	(13)
Chapter Summary	135	(1)
Multiobjective Optimization	136	(11)
Multiple Criteria Decision Making	136	(2)
A Sufficient Condition: Conflicting Criteria	138	(1)
Classification of Multiobjective Problems	138	(1)
Solution Methods	139	(3)
Multiple Criteria Optimization Redefined	142	(1)
The Concept of Pareto Optimality and ``Efficient'' Solutions	143	(4)
Niche Formation and Speciation: Foundations of Multiobjective GAs	147	(24)
Biological Moorings of Natural Evolution	148	(6)
Evolution is also Cultural	154	(4)
The Natural World of a Thousand Species	158	(2)
Key Factors Affecting the Formation of Species	160	(1)
What is a Niche?	161	(2)
Population Diversification through Niche Compacting	163	(3)
Speciation: The Formation of New Species	166	(5)
The Nondominated Sorting Genetic Algorithm: NSGA	171	(32)
Genetic Drift: A Characteristic Feature of SGA	171	(2)
The Vector Evaluated Genetic Algorithm (VEGA)	173	(1)
Niche, Species, Sharing and Function Optimization	174	(5)
Multiobjective Optimization Genetic Algorithm (MOGA)	179	(1)
Pareto Domination Tournaments	179	(1)
A Multiobjective GA Based on the Weighted Sum	180	(1)
The Nondominated Sorting Genetic Algorithm (NSGA)	181	(6)
Applying NSGA: A Numerical Example	187	(15)
Chapter Summary	202	(1)
Multiobjective Flowshop Scheduling	203	(13)
Traditional Methods to Sequence Jobs in the Multiobjective Flowshop	203	(3)
Disadvantages of Classical Methods	206	(1)
Adaptive Random Search Optimization	207	(1)
Recollection of the Concept of Pareto Optimality	207	(2)
NSGA Solutions to the Multiobjective Flowshop	209	(2)
How NSGA Produced Pareto Optimal Sequences	211	(3)
The Quality of the Final Solutions	214	(1)
Chapter Summary	214	(2)
A New Genetic Algorithm for Sequencing the Multiobjective Flowshop	216	(29)
The Elitist Nondominated Sorting Genetic Algorithm (ENGA)	217	(2)
Initialization of ENGA (Box 1)	219	(1)
Performance Evaluation	220	(4)
Genetic Processing Operators	224	(6)
The Additional Nondominated Sorting and Ranking (Box 8)	230	(2)
Stopping Condition and Output Module	232	(1)
Parameterization of ENGA by Design of Experiments	232	(5)
Application of ENGA to the 49-Job 15-Machine Flowshop	237	(1)
Chapter Summary	237	(8)
A Comparison of Multiobjective Flowshop Sequencing by NSGA and ENGA	245	(11)
NSGA vs. ENGA: Computational Experience	245	(2)
Statistical Evaluation of GA Results	247	(2)
Chapter Summary	249	(7)
Multiobjective Job Shop Scheduling	256	(11)
Multiobjective JSP Implementation	256	(5)
NSGA vs. ENGA: Computational Experience	261	(1)
Chapter Summary	261	(6)
Multiobjective Open Shop Scheduling	267	(10)
An Overview of the Open Shop	267	(1)
Multiobjective GA Implementation	268	(2)
NSGA vs. ENGA: Some Computational Results	270	(7)
Epilog and Directions for Further Work	277	(16)
Exact solutions	278	(1)
Solving the General Job Shop	278	(1)
Seeking Pareto Optimality	279	(1)
Optimization of GA Parameters	279	(2)
ENGA vs. Other Multiobjective Solution Methods	281	(2)
Conflicting and Synergistic Optimization Objectives	283	(5)
Darwinian and Lamarckian GAs: The High Value of Hybridizing	288	(1)
Concluding Remarks	289	(4)
References	293	(14)
Appendix C++ Codes for a Hybridized GA to Sequence the Single-Objective Flowshop	307	(34)
Glossary	341	(10)
Index	351