Metaheuristics for Production Scheduling

Inbunden, Engelska, 2013

2 567 kr

Beställningsvara. Skickas inom 11-20 vardagar. Fri frakt över 249 kr.

Beskrivning

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.

Produktinformation

Utgivningsdatum:2013-05-14
Mått:163 x 241 x 32 mm
Vikt:907 g
Format:Inbunden
Språk:Engelska
Antal sidor:528
Förlag:ISTE Ltd and John Wiley & Sons Inc
ISBN:9781848214972

Utforska kategorier

Mer om författaren

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.

Innehållsförteckning

Introduction and Presentation xvBassem JARBOUI, Patrick SIARRY and Jacques TEGHEMChapter 1. An Estimation of Distribution Algorithm for Solving Flow Shop Scheduling Problems with Sequence-dependent Family Setup Times 1Mansour EDDALY, Bassem JARBOUI, Radhouan BOUABDA, Patrick SIARRY and Abdelwaheb REBAÏ1.1. Introduction 11.2. Mathematical formulation 31.3. Estimation of distribution algorithms 51.3.1. Estimation of distribution algorithms proposed in the literature 61.4. The proposed estimation of distribution algorithm 81.4.1. Encoding scheme and initial population 81.4.2. Selection 91.4.3. Probability estimation 91.5. Iterated local search algorithm 101.6. Experimental results 111.7. Conclusion 151.8. Bibliography 15Chapter 2. Genetic Algorithms for Solving Flexible Job Shop Scheduling Problems 19Imed KACEM2.1. Introduction 192.2. Flexible job shop scheduling problems 192.3. Genetic algorithms for some related sub-problems 252.4. Genetic algorithms for the flexible job shop problem 312.4.1. Codings 312.4.2. Mutation operators 342.4.3. Crossover operators 382.5. Comparison of codings 422.6. Conclusion 432.7. Bibliography 43Chapter 3. A Hybrid GRASP-Differential Evolution Algorithm for Solving Flow Shop Scheduling Problems with No-Wait Constraints 45Hanen AKROUT, Bassem JARBOUI, Patrick SIARRY and Abdelwaheb REBAÏ3.1. Introduction 453.2. Overview of the literature 473.2.1. Single-solution metaheuristics 473.2.2. Population-based metaheuristics 493.2.3. Hybrid approaches 493.3. Description of the problem 503.4. GRASP 523.5. Differential evolution 533.6. Iterative local search 553.7. Overview of the NEW-GRASP-DE algorithm 553.7.1. Constructive phase 563.7.2. Improvement phase 573.8. Experimental results 573.8.1. Experimental results for the Reeves and Heller instances 583.8.2. Experimental results for the Taillard instances 603.9. Conclusion 623.10. Bibliography 64Chapter 4. A Comparison of Local Search Metaheuristics for a Hierarchical Flow Shop Optimization Problem with Time Lags 69Emna DHOUIB, Jacques TEGHEM, Daniel TUYTTENS and Taïcir LOUKIL4.1. Introduction 694.2. Description of the problem 704.2.1. Flowshop with time lags 704.2.2. A bicriteria hierarchical flow shop problem 714.3. The proposed metaheuristics 734.3.1. A simulated annealing metaheuristics 744.3.2. The GRASP metaheuristics 774.4. Tests 824.4.1. Generated instances 824.4.2. Comparison of the results 834.5. Conclusion 944.6. Bibliography 94Chapter 5. Neutrality in Flow Shop Scheduling Problems: Landscape Structure and Local Search 97Marie-Eléonore MARMION5.1. Introduction 975.2. Neutrality in a combinatorial optimization problem 985.2.1. Landscape in a combinatorial optimization problem 995.2.2. Neutrality and landscape 1025.3. Study of neutrality in the flow shop problem 1065.3.1. Neutral degree 1065.3.2. Structure of the neutral landscape 1085.4. Local search exploiting neutrality to solve the flow shop problem 1125.4.1. Neutrality-based iterated local search 1135.4.2. NILS on the flow shop problem 1165.5. Conclusion 1225.6. Bibliography 123Chapter 6. Evolutionary Metaheuristic Based on Genetic Algorithm: Application to Hybrid Flow Shop Problem with Availability Constraints 127Nadia CHAABEN, Racem MELLOULI and Faouzi MASMOUDI6.1. Introduction 1276.2. Overview of the literature 1286.3. Overview of the problem and notations used 1316.4. Mathematical formulations 1336.4.1. First formulation (MILP1) 1336.4.2. Second formulation (MILP2) 1356.4.3. Third formulation (MILP3) 1376.5. A genetic algorithm: model and methodology 1396.5.1. Coding used for our algorithm 1396.5.2. Generating the initial population 1406.5.3. Selection operator 1426.5.4. Crossover operator 1426.5.5. Mutation operator 1446.5.6. Insertion operator 1446.5.7. Evaluation function: fitness 1446.5.8. Stop criterion 1456.6. Verification and validation of the genetic algorithm 1456.6.1. Description of benchmarks 1456.6.2. Tests and results 1466.7. Conclusion 1486.8. Bibliography 148Chapter 7. Models and Methods in Graph Coloration for Various Production Problems 153Nicolas ZUFFEREY7.1. Introduction 1537.2. Minimizing the makespan 1557.2.1. Tabu algorithm 1557.2.2. Hybrid genetic algorithm 1577.2.3. Methods prior to GH 1587.2.4. Extensions 1597.3. Maximizing the number of completed tasks 1607.3.1. Tabu algorithm 1617.3.2. The ant colony algorithm 1627.3.3. Extension of the problem 1647.4. Precedence constraints 1657.4.1. Tabu algorithm 1687.4.2. Variable neighborhood search method 1697.5. Incompatibility costs 1717.5.1. Tabu algorithm 1737.5.2. Adaptive memory method 1757.5.3. Variations of the problem 1777.6. Conclusion 1787.7. Bibliography 179Chapter 8. Mathematical Programming and Heuristics for Scheduling Problems with Early and Tardy Penalties 183Mustapha RATLI, Rachid BENMANSOUR, Rita MACEDO, Saïd HANAFI, Christophe WILBAUT8.1. Introduction 1838.2. Properties and particular cases 1858.3. Mathematical models 1888.3.1. Linear models with precedence variables 1888.3.2. Linear models with position variables 1928.3.3. Linear models with time-indexed variables 1948.3.4. Network flow models 1978.3.5. Quadratic models 1978.3.6. A comparative study 1998.4. Heuristics 2038.4.1. Properties 2078.4.2. Evaluation 2098.5. Metaheuristics 2118.6. Conclusion 2178.7. Acknowledgments 2188.8. Bibliography 218Chapter 9. Metaheuristics for Biobjective Flow Shop Scheduling 225Matthieu BASSEUR and Arnaud LIEFOOGHE9.1. Introduction 2259.2. Metaheuristics for multiobjective combinatorial optimization 2269.2.1. Main concepts 2279.2.2. Some methods 2299.2.3. Performance analysis 2329.2.4. Software and implementation 2379.3. Multiobjective flow shop scheduling problems 2389.3.1. Flow shop problems 2399.3.2. Permutation flow shop with due dates 2409.3.3. Different objective functions 2419.3.4. Sets of data 2419.3.5. Analysis of correlations between objectives functions 2429.4. Application to the biobjective flow shop 2439.4.1. Model 2449.4.2. Solution methods 2469.4.3. Experimental analysis 2469.5. Conclusion 2499.6. Bibliography 250Chapter 10. Pareto Solution Strategies for the Industrial Car Sequencing Problem 253Caroline GAGNÉ, Arnaud ZINFLOU and Marc GRAVEL10.1. Introduction 25310.2. Industrial car sequencing problem 25510.3. Pareto strategies for solving the CSP 26010.3.1. PMSMO 26010.3.2. GISMOO 26410.4. Numerical experiments 26810.4.1. Test sets 26910.4.2. Performance metrics 27010.5. Results and discussion 27110.6. Conclusion 27910.7. Bibliography 280Chapter 11. Multi-Objective Metaheuristics for the Joint Scheduling of Production and Maintenance 283Ali BERRICHI and Farouk YALAOUI11.1. Introduction 28311.2. State of the art on the joint problem 28511.3. Integrated modeling of the joint problem 28711.4. Concepts of multi-objective optimization 29111.5. The particle swarm optimization method 29211.6. Implementation of MOPSO algorithms 29411.6.1. Representation and construction of the solutions 29411.6.2. Solution Evaluation 29511.6.3. The proposed MOPSO algorithms 29811.6.4. Updating the velocities and positions 29911.6.5. Hybridization with local searches 30011.7. Experimental results 30211.7.1. Choice of test problems and configurations 30211.7.2. Experiments and analysis of the results 30311.8. Conclusion 31011.9. Bibliography 311Chapter 12. Optimization via a Genetic Algorithm Parametrizing the AHP Method for Multicriteria Workshop Scheduling 315Fouzia OUNNAR, Patrick PUJO and Afef DENGUIR12.1. Introduction 31512.2. Methods for solving multicriteria scheduling 31612.2.1. Optimization methods 31612.2.2. Multicriteria decision aid methods 31812.2.3. Choice of the multicriteria decision aid method 31912.3. Presentation of the AHP method 32012.3.1. Phase 1: configuration 32012.3.2. Phase 2: exploitation 32112.4. Evaluation of metaheuristics for the configuration of AHP 32212.4.1. Local search methods 32312.4.2. Population-based methods 32412.4.3. Advanced metaheuristics 32612.5. Choice of metaheuristic 32612.5.1. Justification of the choice of genetic algorithms 32612.5.2. Genetic algorithms 32812.6. AHP optimization by a genetic algorithm 33012.6.1. Phase 0: configuration of the structure of the problem 33112.6.2. Phase 1: preparation for automatic configuration 33212.6.3. Phase 2: automatic configuration 33412.6.4. Phase 3: preparation of the exploitation phase 33512.7. Evaluation of G-AHP 33612.7.1. Analysis of the behavior of G-AHP 33612.7.2. Analysis of the results obtained by G-AHP 34212.8. Conclusions 34312.9. Bibliography 344Chapter 13. A Multicriteria Genetic Algorithm for the Resource-constrained Task Scheduling Problem 349Olfa DRIDI, Saoussen KRICHEN and Adel GUITOUNI13.1. Introduction 34913.2. Description and formulation of the problem 35013.3. Literature review 35313.3.1. Exact methods 35413.3.2. Approximate methods 35513.4. A multicriteria genetic algorithm for the MMSAP 35613.4.1. Encoding variables 35713.4.2. Genetic operators 35813.4.3. Parameter settings 35913.4.4. The GA 36013.5. Experimental study 36113.5.1. Diversification of the approximation set based on the diversity indicators 36413.6. Conclusion 36913.7. Bibliography 369Chapter 14. Metaheuristics for the Solution of Vehicle Routing Problems in a Dynamic Context 373Tienté HSU, Gilles GONÇALVES and Rémy DUPAS14.1. Introduction 37314.2. Dynamic vehicle route management 37514.2.1. The vehicle routing problem with time windows 37714.3. Platform for the solution of the DVRPTW 38214.3.1. Encoding a chromosome 38414.4. Treating uncertainties in the orders 38614.5. Treatment of traffic information 39214.6. Conclusion 39714.7. Bibliography 398Chapter 15. Combination of a Metaheuristic and a Simulation Model for the Scheduling of Resource-constrained Transport Activities 401Virginie ANDRÉ, Nathalie GRANGEON and Sylvie NORRE15.1. Knowledge model 40315.1.1. Fixed resources and mobile resources 40315.1.2. Modelling the activities in steps 40415.1.3. The problem to be solved 40615.1.4. Illustrative example 40715.2. Solution procedure 41015.3. Proposed approach 41315.3.1. Metaheuristics 41415.3.2. Simulation model 42115.4. Implementation and results 42215.4.1. Impact on the work mode 42315.4.2. Results of the set of modifications to the teaching hospital 42515.4.3. Preliminary study of the choice of shifts 42815.5. Conclusion 43015.6. Bibliography 431Chapter 16. Vehicle Routing Problems with Scheduling Constraints 433Rahma LAHYANI, Frédéric SEMET and Benoît TROUILLET16.1. Introduction 43316.2. Definition, complexity and classification 43516.2.1. Definition and complexity 43516.2.2. Classification 43616.3. Time-constrained vehicle routing problems 43816.3.1. Vehicle routing problems with time windows 43816.3.2. Period vehicle routing problems 44116.3.3. Vehicle routing problem with cross-docking 44316.4. Vehicle routing problems with resource availability constraints 44816.4.1. Multi-trip vehicle routing problem 44816.4.2. Vehicle routing problem with crew scheduling 45016.5. Conclusion 45216.6. Bibliography 453Chapter 17. Metaheuristics for Job Shop Scheduling with Transportation 465Qiao ZHANG, Hervé MANIER, Marie-Ange MANIER17.1. General flexible job shop scheduling problems 46617.2. State of the art on job shop scheduling with transportation resources 46817.3. GTSB procedure 47417.3.1. A hybrid metaheuristic algorithm for the GFJSSP 47417.3.2. Tests and results 48017.3.3. Conclusion for GTSB 48917.4. Conclusion 49117.5. Bibliography 491List of Authors 495Index 499