This book describes the potentialities of metaheuristics for solving production scheduling problems and the relationship between these two fields.For the past several years, there has been an increasing interest in using metaheuristic methods to solve scheduling problems. The main reasons for this are that such problems are generally hard to solve to optimality, as well as the fact that metaheuristics provide very good solutions in a reasonable time. The first part of the book presents eight applications of metaheuristics for solving various mono-objective scheduling problems. The second part is itself split into two, the first section being devoted to five multi-objective problems to which metaheuristics are adapted, while the second tackles various transportation problems related to the organization of production systems.Many real-world applications are presented by the authors, making this an invaluable resource for researchers and students in engineering, economics, mathematics and computer science.Contents1. An Estimation of Distribution Algorithm for Solving Flow Shop Scheduling Problems with Sequence-dependent Family Setup Times, Mansour Eddaly, Bassem Jarboui, Radhouan Bouabda, Patrick Siarry and Abdelwaheb Rebaï.2. Genetic Algorithms for Solving Flexible Job Shop Scheduling Problems, Imed Kacem.3. A Hybrid GRASP-Differential Evolution Algorithm for Solving Flow Shop Scheduling Problems with No-Wait Constraints, Hanen Akrout, Bassem Jarboui, Patrick Siarry and Abdelwaheb Rebaï.4. A Comparison of Local Search Metaheuristics for a Hierarchical Flow Shop Optimization Problem with Time Lags, Emna Dhouib, Jacques Teghem, Daniel Tuyttens and Taïcir Loukil.5. Neutrality in Flow Shop Scheduling Problems: Landscape Structure and Local Search, Marie-Eléonore Marmion.6. Evolutionary Metaheuristic Based on Genetic Algorithm: Application to Hybrid Flow Shop Problem with Availability Constraints, Nadia Chaaben, Racem Mellouli and Faouzi Masmoudi.7. Models and Methods in Graph Coloration for Various Production Problems, Nicolas Zufferey.8. Mathematical Programming and Heuristics for Scheduling Problems with Early and Tardy Penalties, Mustapha Ratli, Rachid Benmansour, Rita Macedo, Saïd Hanafi, Christophe Wilbaut.9. Metaheuristics for Biobjective Flow Shop Scheduling, Matthieu Basseur and Arnaud Liefooghe.10. Pareto Solution Strategies for the Industrial Car Sequencing Problem, Caroline Gagné, Arnaud Zinflou and Marc Gravel.11. Multi-Objective Metaheuristics for the Joint Scheduling of Production and Maintenance, Ali Berrichi and Farouk Yalaoui.12. Optimization via a Genetic Algorithm Parametrizing the AHP Method for Multicriteria Workshop Scheduling, Fouzia Ounnar, Patrick Pujo and Afef Denguir.13. A Multicriteria Genetic Algorithm for the Resource-constrained Task Scheduling Problem, Olfa Dridi, Saoussen Krichen and Adel Guitouni.14. Metaheuristics for the Solution of Vehicle Routing Problems in a Dynamic Context, Tienté Hsu, Gilles Gonçalves and Rémy Dupas.15. Combination of a Metaheuristic and a Simulation Model for the Scheduling of Resource-constrained Transport Activities, Virginie André, Nathalie Grangeon and Sylvie Norre.16. Vehicle Routing Problems with Scheduling Constraints, Rahma Lahyani, Frédéric Semet and Benoît Trouillet.17. Metaheuristics for Job Shop Scheduling with Transportation, Qiao Zhang, Hervé Manier, Marie-Ange Manier.About the AuthorsBassem Jarboui is Professor at the University of Sfax, Tunisia.Patrick Siarry is Professor at the Laboratoire Images, Signaux et Systèmes Intelligents (LISSI), University of Paris-Est Créteil, France.Jacques Teghem is Professor at the University of Mons, Belgium.
This book describes the potentialities of metaheuristics for solving production scheduling problems and the relationship between these two fields. For the past several years, there has been an increasing interest in using metaheuristic methods to solve scheduling problems.
This book describes the potentialities of metaheuristics forsolving production scheduling problems and the relationship betweenthese two fields.
For the past several years, there has been an increasing interestin using metaheuristic methods to solve scheduling problems.
This book describes the potentialities of metaheuristics for solving production scheduling problems and the relationship between these two fields.
For the past several years, there has been an increasing interest in using metaheuristic methods to solve scheduling problems. The main reasons for this are that such problems are generally hard to solve to optimality, as well as the fact that metaheuristics provide very good solutions in a reasonable time. The first part of the book presents eight applications of metaheuristics for solving various mono-objective scheduling problems. The second part is itself split into two, the first section being devoted to five multi-objective problems to which metaheuristics are adapted, while the second tackles various transportation problems related to the organization of production systems.
Many real-world applications are presented by the authors, making this an invaluable resource for researchers and students in engineering, economics, mathematics and computer science.
Contents
1. An Estimation of Distribution Algorithm for Solving Flow Shop Scheduling Problems with Sequence-dependent Family Setup Times, Mansour Eddaly, Bassem Jarboui, Radhouan Bouabda, Patrick Siarry and Abdelwaheb Rebaï.
2. Genetic Algorithms for Solving Flexible Job Shop Scheduling Problems, Imed Kacem.
3. A Hybrid GRASP-Differential Evolution Algorithm for Solving Flow Shop Scheduling Problems with No-Wait Constraints, Hanen Akrout, Bassem Jarboui, Patrick Siarry and Abdelwaheb Rebaï.
4. A Comparison of Local Search Metaheuristics for a Hierarchical Flow Shop Optimization Problem with Time Lags, Emna Dhouib, Jacques Teghem, Daniel Tuyttens and Taïcir Loukil.
5. Neutrality in Flow Shop Scheduling Problems: Landscape Structure and Local Search, Marie-Eléonore Marmion.
6. Evolutionary Metaheuristic Based on Genetic Algorithm: Application to Hybrid Flow Shop Problem with Availability Constraints, Nadia Chaaben, Racem Mellouli and Faouzi Masmoudi.
7. Models and Methods in Graph Coloration for Various Production Problems, Nicolas Zufferey.
8. Mathematical Programming and Heuristics for Scheduling Problems with Early and Tardy Penalties, Mustapha Ratli, Rachid Benmansour, Rita Macedo, Saïd Hanafi, Christophe Wilbaut.
9. Metaheuristics for Biobjective Flow Shop Scheduling, Matthieu Basseur and Arnaud Liefooghe.
10. Pareto Solution Strategies for the Industrial Car Sequencing Problem, Caroline Gagné, Arnaud Zinflou and Marc Gravel.
11. Multi-Objective Metaheuristics for the Joint Scheduling of Production and Maintenance, Ali Berrichi and Farouk Yalaoui.
12. Optimization via a Genetic Algorithm Parametrizing the AHP Method for Multicriteria Workshop Scheduling, Fouzia Ounnar, Patrick Pujo and Afef Denguir.
13. A Multicriteria Genetic Algorithm for the Resource-constrained Task Scheduling Problem, Olfa Dridi, Saoussen Krichen and Adel Guitouni.
14. Metaheuristics for the Solution of Vehicle Routing Problems in a Dynamic Context, Tienté Hsu, Gilles Gonçalves and Rémy Dupas.
15. Combination of a Metaheuristic and a Simulation Model for the Scheduling of Resource-constrained Transport Activities, Virginie André, Nathalie Grangeon and Sylvie Norre.
16. Vehicle Routing Problems with Scheduling Constraints, Rahma Lahyani, Frédéric Semet and Benoît Trouillet.
17. Metaheuristics for Job Shop Scheduling with Transportation, Qiao Zhang, Hervé Manier, Marie-Ange Manier.
About the Authors
Bassem Jarboui is Professor at the University of Sfax, Tunisia.
Patrick Siarry is Professor at the Laboratoire Images, Signaux et Systèmes Intelligents (LISSI), University of Paris-Est Créteil, France.
Jacques Teghem is Professor at the University of Mons, Belgium.
Introduction and Presentation xv
Bassem JARBOUI, Patrick SIARRY and Jacques TEGHEM
Chapter 1. An Estimation of Distribution Algorithm for Solving Flow Shop Scheduling Problems with Sequence-dependent Family Setup Times 1
Mansour EDDALY, Bassem JARBOUI, Radhouan BOUABDA, Patrick SIARRY and Abdelwaheb REBAÏ
1.1. Introduction 1
1.2. Mathematical formulation 3
1.3. Estimation of distribution algorithms 5
1.4. The proposed estimation of distribution algorithm 8
1.5. Iterated local search algorithm 10
1.6. Experimental results 11
1.7. Conclusion 15
1.8. Bibliography 15
Chapter 2. Genetic Algorithms for Solving Flexible Job Shop Scheduling Problems 19
Imed KACEM
2.1. Introduction 19
2.2. Flexible job shop scheduling problems 19
2.3. Genetic algorithms for some related sub-problems 25
2.4. Genetic algorithms for the flexible job shop problem 31
2.5. Comparison of codings 42
2.6. Conclusion 43
2.7. Bibliography 43
Chapter 3. A Hybrid GRASP-Differential Evolution Algorithm for Solving Flow Shop Scheduling Problems with No-Wait Constraints 45
Hanen AKROUT, Bassem JARBOUI, Patrick SIARRY and Abdelwaheb REBAÏ
3.1. Introduction 45
3.2. Overview of the literature 47
3.3. Deillegalscription of the problem 50
3.4. GRASP 52
3.5. Differential evolution 53
3.6. Iterative local search 55
3.7. Overview of the NEW-GRASP-DE algorithm 55
3.8. Experimental results 57
3.9. Conclusion 62
3.10. Bibliography 64
Chapter 4. A Comparison of Local Search Metaheuristics for a Hierarchical Flow Shop Optimization Problem with Time Lags 69
Emna DHOUIB, Jacques TEGHEM, Daniel TUYTTENS and Taïcir LOUKIL
4.1. Introduction 69
4.2. Deillegalscription of the problem 70
4.3. The proposed metaheuristics 73
4.4. Tests 82
4.5. Conclusion 94
4.6. Bibliography 94
Chapter 5. Neutrality in Flow Shop Scheduling Problems: Landscape Structure and Local Search 97
Marie-Eléonore MARMION
5.1. Introduction 97
5.2. Neutrality in a combinatorial optimization problem 98
5.3. Study of neutrality in the flow shop problem 106
5.4. Local search exploiting neutrality to solve the flow shop problem 112
5.5. Conclusion 122
5.6. Bibliography 123
Chapter 6. Evolutionary Metaheuristic Based on Genetic Algorithm: Application to Hybrid Flow Shop Problem with Availability Constraints 127
Nadia CHAABEN, Racem MELLOULI and Faouzi MASMOUDI
6.1. Introduction 127
6.2. Overview of the literature 128
6.3. Overview of the problem and notations used 131
6.4. Mathematical formulations 133
6.5. A genetic algorithm: model and methodology 139
6.6. Verification and validation of the genetic algorithm 145
6.7. Conclusion 148
6.8. Bibliography 148
Chapter 7. Models and Methods in Graph Coloration for Various Production Problems 153
Nicolas ZUFFEREY
7.1. Introduction 153
7.2. Minimizing the makespan 155
7.3. Maximizing the number of completed tasks 160
7.4. Precedence constraints 165
7.5. Incompatibility costs 171
7.6. Conclusion 178
7.7. Bibliography 179
Chapter 8. Mathematical Programming and Heuristics for Scheduling Problems with Early and Tardy Penalties 183
Mustapha RATLI, Rachid BENMANSOUR, Rita MACEDO, Saïd HANAFI, Christophe WILBAUT
8.1. Introduction 183
8.2. Properties and particular cases 185
<
Inhaltsverzeichnis
Introduction and Presentation xv
Bassem JARBOUI, Patrick SIARRY and Jacques TEGHEM
Chapter 1. An Estimation of Distribution Algorithm for Solving Flow Shop Scheduling Problems with Sequence-dependent Family Setup Times 1
Mansour EDDALY, Bassem JARBOUI, Radhouan BOUABDA, Patrick SIARRY and Abdelwaheb REBAÏ
1.1. Introduction 1
1.2. Mathematical formulation 3
1.3. Estimation of distribution algorithms 5
1.4. The proposed estimation of distribution algorithm 8
1.5. Iterated local search algorithm 10
1.6. Experimental results 11
1.7. Conclusion 15
1.8. Bibliography 15
Chapter 2. Genetic Algorithms for Solving Flexible Job Shop Scheduling Problems 19
Imed KACEM
2.1. Introduction 19
2.2. Flexible job shop scheduling problems 19
2.3. Genetic algorithms for some related sub-problems 25
2.4. Genetic algorithms for the flexible job shop problem 31
2.5. Comparison of codings 42
2.6. Conclusion 43
2.7. Bibliography 43
Chapter 3. A Hybrid GRASP-Differential Evolution Algorithm for Solving Flow Shop Scheduling Problems with No-Wait Constraints 45
Hanen AKROUT, Bassem JARBOUI, Patrick SIARRY and Abdelwaheb REBAÏ
3.1. Introduction 45
3.2. Overview of the literature 47
3.3. Deillegalscription of the problem 50
3.4. GRASP 52
3.5. Differential evolution 53
3.6. Iterative local search 55
3.7. Overview of the NEW-GRASP-DE algorithm 55
3.8. Experimental results 57
3.9. Conclusion 62
3.10. Bibliography 64
Chapter 4. A Comparison of Local Search Metaheuristics for a Hierarchical Flow Shop Optimization Problem with Time Lags 69
Emna DHOUIB, Jacques TEGHEM, Daniel TUYTTENS and Taïcir LOUKIL
4.1. Introduction 69
4.2. Deillegalscription of the problem 70
4.3. The proposed metaheuristics 73
4.4. Tests 82
4.5. Conclusion 94
4.6. Bibliography 94
Chapter 5. Neutrality in Flow Shop Scheduling Problems: Landscape Structure and Local Search 97
Marie-Eléonore MARMION
5.1. Introduction 97
5.2. Neutrality in a combinatorial optimization problem 98
5.3. Study of neutrality in the flow shop problem 106
5.4. Local search exploiting neutrality to solve the flow shop problem 112
5.5. Conclusion 122
5.6. Bibliography 123
Chapter 6. Evolutionary Metaheuristic Based on Genetic Algorithm: Application to Hybrid Flow Shop Problem with Availability Constraints 127
Nadia CHAABEN, Racem MELLOULI and Faouzi MASMOUDI
6.1. Introduction 127
6.2. Overview of the literature 128
6.3. Overview of the problem and notations used 131
6.4. Mathematical formulations 133
6.5. A genetic algorithm: model and methodology 139
6.6. Verification and validation of the genetic algorithm 145
6.7. Conclusion 148
6.8. Bibliography 148
Chapter 7. Models and Methods in Graph Coloration for Various Production Problems 153
Nicolas ZUFFEREY
7.1. Introduction 153
7.2. Minimizing the makespan 155
7.3. Maximizing the number of completed tasks 160
7.4. Precedence constraints 165
7.5. Incompatibility costs 171
7.6. Conclusion 178
7.7. Bibliography 179
Chapter 8. Mathematical Programming and Heuristics for Scheduling Problems with Early and Tardy Penalties 183
Mustapha RATLI, Rachid BENMANSOUR, Rita MACEDO, Saïd HANAFI, Christophe WILBAUT
8.1. Introduction 183
8.2. Properties and particular cases 185
8.3. Mathematical models 188
8.4. Heuristics 203
8.5. Metaheuristics 211
8.6. Conclusion 217
8.7. Acknowledgments 218
8.8. Bibliography 218
Chapter 9. Metaheuristics for Biobjective Flow Shop Scheduling 225
Matthieu BASSEUR and Arnaud LIEFOOGHE
9.1. Introduction 225
9.2. Metaheuristics for multiobjective combinatorial optimization 226
9.3. Multiobjective flow shop scheduling problems 238
9.4. Application to the biobjective flow shop 243
9.5. Conclusion 249
9.6. Bibliography 250
Chapter 10. Pareto Solution Strategies for the Industrial Car Sequencing Problem 253
Caroline GAGNÉ, Arnaud ZINFLOU and Marc GRAVEL
10.1. Introduction 253
10.2. Industrial car sequencing problem 255
10.3. Pareto strategies for solving the CSP 260
10.4. Numerical experiments 268
10.5. Results and discussion 271
10.6. Conclusion 279
10.7. Bibliography 280
Chapter 11. Multi-Objective Metaheuristics for the Joint Scheduling of Production and Maintenance 283
Ali BERRICHI and Farouk YALAOUI
11.1. Introduction 283
11.2. State of the art on the joint problem 285
11.3. Integrated modeling of the joint problem 287
11.4. Concepts of multi-objective optimization 291
11.5. The particle swarm optimization method 292
11.6. Implementation of MOPSO algorithms 294
11.7. Experimental results 302
11.8. Conclusion 310
11.9. Bibliography 311
Chapter 12. Optimization via a Genetic Algorithm Parametrizing the AHP Method for Multicriteria Workshop Scheduling 315
Fouzia OUNNAR, Patrick PUJO and Afef DENGUIR
12.1. Introduction 315
12.2. Methods for solving multicriteria scheduling 316
12.3. Presentation of the AHP method 320
12.4. Evaluation of metaheuristics for the configuration of AHP 322
12.5. Choice of metaheuristic 326
12.6. AHP optimization by a genetic algorithm 330
12.7. Evaluation of G-AHP 336
12.8. Conclusions 343
12.9. Bibliography 344
Chapter 13. A Multicriteria Genetic Algorithm for the Resource-constrained Task Scheduling Problem 349
Olfa DRIDI, Saoussen KRICHEN and Adel GUITOUNI
13.1. Introduction 349
13.2. Deillegalscription and formulation of the problem 350
13.3. Literature review 353
13.4. A multicriteria genetic algorithm for the MMSAP 356
13.5. Experimental study 361
13.6. Conclusion 369
13.7. Bibliography 369
Chapter 14. Metaheuristics for the Solution of Vehicle Routing Problems in a Dynamic Context 373
Tienté HSU, Gilles GONÇALVES and Rémy DUPAS
14.1. Introduction 373
14.2. Dynamic vehicle route management 375
14.3. Platform for the solution of the DVRPTW 382
14.4. Treating uncertainties in the orders 386
14.5. Treatment of traffic information 392
14.6. Conclusion 397
14.7. Bibliography 398
Chapter 15. Combination of a Metaheuristic and a Simulation Model for the Scheduling of Resource-constrained Transport Activities 401
Virginie ANDRÉ, Nathalie GRANGEON and Sylvie NORRE
15.1. Knowledge model 403
15.2. Solution procedure 410
15.3. Proposed approach 413
15.4. Implementation and results 422
15.5. Conclusion 430
15.6. Bibliography 431
Chapter 16. Vehicle Routing Problems with Scheduling Constraints 433
Rahma LAHYANI, Frédéric SEMET and Benoît TROUILLET
16.1. Introduction 433
16.2. Definition, complexity and classification 435
16.3. Time-constrained vehicle routing problems 438
16.4. Vehicle routing problems with resource availability constraints 448
16.5. Conclusion 452
16.6. Bibliography 453
Chapter 17. Metaheuristics for Job Shop Scheduling with Transportation 465
Qiao ZHANG, Hervé MANIER, Marie-Ange MANIER
17.1. General flexible job shop scheduling problems 466
17.2. State of the art on job shop scheduling with transportation resources 468
17.3. GTSB procedure 474
17.4. Conclusion 491
17.5. Bibliography 491
List of Authors 495
Index 499
Klappentext
This book describes the potentialities of metaheuristics for solving production scheduling problems and the relationship between these two fields.
For the past several years, there has been an increasing interest in using metaheuristic methods to solve scheduling problems. The main reasons for this are that such problems are generally hard to solve to optimality, as well as the fact that metaheuristics provide very good solutions in a reasonable time. The first part of the book presents eight applications of metaheuristics for solving various mono-objective scheduling problems. The second part is itself split into two, the first section being devoted to five multi-objective problems to which metaheuristics are adapted, while the second tackles various transportation problems related to the organization of production systems.
Many real-world applications are presented by the authors, making this an invaluable resource for researchers and students in engineering, economics, mathematics and computer science.
Contents
1. An Estimation of Distribution Algorithm for Solving Flow Shop Scheduling Problems with Sequence-dependent Family Setup Times, Mansour Eddaly, Bassem Jarboui, Radhouan Bouabda, Patrick Siarry and Abdelwaheb Rebaï.
2. Genetic Algorithms for Solving Flexible Job Shop Scheduling Problems, Imed Kacem.
3. A Hybrid GRASP-Differential Evolution Algorithm for Solving Flow Shop Scheduling Problems with No-Wait Constraints, Hanen Akrout, Bassem Jarboui, Patrick Siarry and Abdelwaheb Rebaï.
4. A Comparison of Local Search Metaheuristics for a Hierarchical Flow Shop Optimization Problem with Time Lags, Emna Dhouib, Jacques Teghem, Daniel Tuyttens and Taïcir Loukil.
5. Neutrality in Flow Shop Scheduling Problems: Landscape Structure and Local Search, Marie-Eléonore Marmion.
6. Evolutionary Metaheuristic Based on Genetic Algorithm: Application to Hybrid Flow Shop Problem with Availability Constraints, Nadia Chaaben, Racem Mellouli and Faouzi Masmoudi.
7. Models and Methods in Graph Coloration for Various Production Problems, Nicolas Zufferey.
8. Mathematical Programming and Heuristics for Scheduling Problems with Early and Tardy Penalties, Mustapha Ratli, Rachid Benmansour, Rita Macedo, Saïd Hanafi, Christophe Wilbaut.
9. Metaheuristics for Biobjective Flow Shop Scheduling, Matthieu Basseur and Arnaud Liefooghe.
10. Pareto Solution Strategies for the Industrial Car Sequencing Problem, Caroline Gagné, Arnaud Zinflou and Marc Gravel.
11. Multi-Objective Metaheuristics for the Joint Scheduling of Production and Maintenance, Ali Berrichi and Farouk Yalaoui.
12. Optimization via a Genetic Algorithm Parametrizing the AHP Method for Multicriteria Workshop Scheduling, Fouzia Ounnar, Patrick Pujo and Afef Denguir.
13. A Multicriteria Genetic Algorithm for the Resource-constrained Task Scheduling Problem, Olfa Dridi, Saoussen Krichen and Adel Guitouni.
14. Metaheuristics for the Solution of Vehicle Routing Problems in a Dynamic Context, Tienté Hsu, Gilles Gonçalves and Rémy Dupas.
15. Combination of a Metaheuristic and a Simulation Model for the Scheduling of Resource-constrained Transport Activities, Virginie André, Nathalie Grangeon and Sylvie Norre.
16. Vehicle Routing Problems with Scheduling Constraints, Rahma Lahyani, Frédéric Semet and Benoît Trouillet.
17. Metaheuristics for Job Shop Scheduling with Transportation, Qiao Zhang, Hervé Manier, Marie-Ange Manier.
About the Authors
Bassem Jarboui is Professor at the University of Sfax, Tunisia.
Patrick Siarry is Professor at the Laboratoire Images, Signaux et Systèmes Intelligents (LISSI), University of Paris-Est Créteil, France.
Jacques Teghem is Professor at the University of Mons, Belgium.
