Metaheuristics for Production Scheduling

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  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