ISBN-10:
1848214979
ISBN-13:
9781848214972
Pub. Date:
06/10/2013
Publisher:
Wiley
Metaheuristics for Production Scheduling / Edition 1

Metaheuristics for Production Scheduling / Edition 1

Current price is , Original price is $212.0. You

Temporarily Out of Stock Online

Please check back later for updated availability.

Product Details

ISBN-13: 9781848214972
Publisher: Wiley
Publication date: 06/10/2013
Series: ISTE Series
Pages: 528
Product dimensions: 6.00(w) x 9.30(h) x 1.40(d)

About the Author

Bassem Jarboui, Laboratoire MODILS, University of Sfax, Tunisia.

Patrick Siarry, Laboratoire LiSSi, University of Paris-Est Créteil, France.

Jacques Teghem, MathRO / Polytechnic Faculty of Mons, Belgium.

Table of Contents

Introduction and Presentation  xv
Bassem JARBOUI, Patrick SIARRY and Jacques TEGHEM

Chapter 1. An Estimation of Distribution Algorithm forSolving Flow Shop Scheduling Problems with Sequence-dependentFamily Setup Times   1
Mansour EDDALY, Bassem JARBOUI, Radhouan BOUABDA, Patrick SIARRYand Abdelwaheb REBAÏ

1.1. Introduction   1

1.2. Mathematical formulation   3

1.3. Estimation of distribution algorithms  5

1.3.1. Estimation of distribution algorithms proposed in theliterature  6

1.4. The proposed estimation of distribution algorithm 8

1.4.1. Encoding scheme and initial population  8

1.4.2. Selection 9

1.4.3. Probability estimation    9

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 ShopScheduling 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.4.1. Codings 31

2.4.2. Mutation operators  34

2.4.3. Crossover operators  38

2.5. Comparison of codings 42

2.6. Conclusion  43

2.7. Bibliography   43

Chapter 3. A Hybrid GRASP-Differential Evolution Algorithmfor Solving Flow Shop Scheduling Problems with No-WaitConstraints   45
Hanen AKROUT, Bassem JARBOUI, Patrick SIARRY and AbdelwahebREBAÏ

3.1. Introduction   45

3.2. Overview of the literature   47

3.2.1. Single-solution metaheuristics 47

3.2.2. Population-based metaheuristics  49

3.2.3. Hybrid approaches  49

3.3. Description 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.7.1. Constructive phase  56

3.7.2. Improvement phase  57

3.8. Experimental results   57

3.8.1. Experimental results for the Reeves and Hellerinstances  58

3.8.2. Experimental results for the Taillard instances 60

3.9. Conclusion  62

3.10. Bibliography  64

Chapter 4. A Comparison of Local Search Metaheuristics for aHierarchical Flow Shop Optimization Problem with TimeLags    69
Emna DHOUIB, Jacques TEGHEM, Daniel TUYTTENS and TaïcirLOUKIL

4.1. Introduction   69

4.2. Description of the problem   70

4.2.1. Flowshop with time lags    70

4.2.2. A bicriteria hierarchical flow shop problem  71

4.3. The proposed metaheuristics    73

4.3.1. A simulated annealing metaheuristics   74

4.3.2. The GRASP metaheuristics   77

4.4. Tests   82

4.4.1. Generated instances  82

4.4.2. Comparison of the results 83

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.2.1. Landscape in a combinatorial optimization problem 99

5.2.2. Neutrality and landscape    102

5.3. Study of neutrality in the flow shop problem 106

5.3.1. Neutral degree   106

5.3.2. Structure of the neutral landscape 108

5.4. Local search exploiting neutrality to solve the flow shopproblem   112

5.4.1. Neutrality-based iterated local search  113

5.4.2. NILS on the flow shop problem  116

5.5. Conclusion    122

5.6. Bibliography   123

Chapter 6. Evolutionary Metaheuristic Based on GeneticAlgorithm: Application to Hybrid Flow Shop Problem withAvailability 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.4.1. First formulation (MILP1) 133

6.4.2. Second formulation (MILP2) 135

6.4.3. Third formulation (MILP3)   137

6.5. A genetic algorithm: model and methodology  139

6.5.1. Coding used for our algorithm 139

6.5.2. Generating the initial population 140

6.5.3. Selection operator  142

6.5.4. Crossover operator  142

6.5.5. Mutation operator  144

6.5.6. Insertion operator 144

6.5.7. Evaluation function: fitness   144

6.5.8. Stop criterion   145

6.6. Verification and validation of the genetic algorithm 145

6.6.1. Description of benchmarks  145

6.6.2. Tests and results   146

6.7. Conclusion  148

6.8. Bibliography   148

Chapter 7. Models and Methods in Graph Coloration for VariousProduction Problems  153
Nicolas ZUFFEREY

7.1. Introduction   153

7.2. Minimizing the makespan   155

7.2.1. Tabu algorithm   155

7.2.2. Hybrid genetic algorithm    157

7.2.3. Methods prior to GH   158

7.2.4. Extensions  159

7.3. Maximizing the number of completed tasks 160

7.3.1. Tabu algorithm   161

7.3.2. The ant colony algorithm    162

7.3.3. Extension of the problem    164

7.4. Precedence constraints 165

7.4.1. Tabu algorithm   168

7.4.2. Variable neighborhood search method  169

7.5. Incompatibility costs   171

7.5.1. Tabu algorithm   173

7.5.2. Adaptive memory method 175

7.5.3. Variations of the problem    177

7.6. Conclusion 178

7.7. Bibliography   179

Chapter 8. Mathematical Programming and Heuristics forScheduling Problems with Early and Tardy Penalties 183
Mustapha RATLI, Rachid BENMANSOUR, Rita MACEDO, SaïdHANAFI, Christophe WILBAUT

8.1. Introduction   183

8.2. Properties and particular cases    185

8.3. Mathematical models   188

8.3.1. Linear models with precedence variables  188

8.3.2. Linear models with position variables 192

8.3.3. Linear models with time-indexed variables  194

8.3.4. Network flow models   197

8.3.5. Quadratic models 197

8.3.6. A comparative study   199

8.4. Heuristics  203

8.4.1. Properties  207

8.4.2. Evaluation  209

8.5. Metaheuristics 211

8.6. Conclusion  217

8.7. Acknowledgments   218

8.8. Bibliography   218

Chapter 9. Metaheuristics for Biobjective Flow ShopScheduling  225
Matthieu BASSEUR and Arnaud LIEFOOGHE

9.1. Introduction   225

9.2. Metaheuristics for multiobjective combinatorialoptimization  226

9.2.1. Main concepts   227

9.2.2. Some methods   229

9.2.3. Performance analysis   232

9.2.4. Software and implementation 237

9.3. Multiobjective flow shop scheduling problems  238

9.3.1. Flow shop problems   239

9.3.2. Permutation flow shop with due dates   240

9.3.3. Different objective functions   241

9.3.4. Sets of data 241

9.3.5. Analysis of correlations between objectivesfunctions  242

9.4. Application to the biobjective flow shop  243

9.4.1. Model   244

9.4.2. Solution methods  246

9.4.3. Experimental analysis    246

9.5. Conclusion   249

9.6. Bibliography   250

Chapter 10. Pareto Solution Strategies for the Industrial CarSequencing 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.3.1. PMSMO  260

10.3.2. GISMOO  264

10.4. Numerical experiments  268

10.4.1. Test sets 269

10.4.2. Performance metrics   270

10.5. Results and discussion  271

10.6. Conclusion   279

10.7. Bibliography  280

Chapter 11. Multi-Objective Metaheuristics for the JointScheduling 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.6.1. Representation and construction of the solutions 294

11.6.2. Solution Evaluation   295

11.6.3. The proposed MOPSO algorithms   298

11.6.4. Updating the velocities and positions  299

11.6.5. Hybridization with local searches   300

11.7. Experimental results   302

11.7.1. Choice of test problems and configurations  302

11.7.2. Experiments and analysis of the results  303

11.8. Conclusion   310

11.9. Bibliography  311

Chapter 12. Optimization via a Genetic AlgorithmParametrizing the AHP Method for Multicriteria Workshop Scheduling315
Fouzia OUNNAR, Patrick PUJO and Afef DENGUIR

12.1. Introduction 315

12.2. Methods for solving multicriteria scheduling  316

12.2.1. Optimization methods    316

12.2.2. Multicriteria decision aid methods   318

12.2.3. Choice of the multicriteria decision aid method 319

12.3. Presentation of the AHP method   320

12.3.1. Phase 1: configuration    320

12.3.2. Phase 2: exploitation    321

12.4. Evaluation of metaheuristics for the configuration ofAHP  322

12.4.1. Local search methods    323

12.4.2. Population-based methods   324

12.4.3. Advanced metaheuristics  326

12.5. Choice of metaheuristic  326

12.5.1. Justification of the choice of genetic algorithms326

12.5.2. Genetic algorithms   328

12.6. AHP optimization by a genetic algorithm  330

12.6.1. Phase 0: configuration of the structure of theproblem  331

12.6.2. Phase 1: preparation for automatic configuration 332

12.6.3. Phase 2: automatic configuration   334

12.6.4. Phase 3: preparation of the exploitation phase 335

12.7. Evaluation of G-AHP 336

12.7.1. Analysis of the behavior of G-AHP   336

12.7.2. Analysis of the results obtained by G-AHP  342

12.8. Conclusions 343

12.9. Bibliography 344

Chapter 13. A Multicriteria Genetic Algorithm for theResource-constrained Task Scheduling Problem  349
Olfa DRIDI, Saoussen KRICHEN and Adel GUITOUNI

13.1. Introduction 349

13.2. Description and formulation of the problem  350

13.3. Literature review  353

13.3.1. Exact methods   354

13.3.2. Approximate methods    355

13.4. A multicriteria genetic algorithm for the MMSAP 356

13.4.1. Encoding variables   357

13.4.2. Genetic operators  358

13.4.3. Parameter settings  359

13.4.4. The GA 360

13.5. Experimental study   361

13.5.1. Diversification of the approximation set based on thediversity indicators    364

13.6. Conclusion   369

13.7. Bibliography  369

Chapter 14. Metaheuristics for the Solution of VehicleRouting Problems in a Dynamic Context   373
Tienté HSU, Gilles GONÇALVES and RémyDUPAS

14.1. Introduction  373

14.2. Dynamic vehicle route management  375

14.2.1. The vehicle routing problem with time windows 377

14.3. Platform for the solution of the DVRPTW  382

14.3.1. Encoding a chromosome  384

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 SimulationModel for the Scheduling of Resource-constrained TransportActivities 401
Virginie ANDRÉ, Nathalie GRANGEON and Sylvie NORRE

15.1. Knowledge model   403

15.1.1. Fixed resources and mobile resources  403

15.1.2. Modelling the activities in steps 404

15.1.3. The problem to be solved  406

15.1.4. Illustrative example   407

15.2. Solution procedure   410

15.3. Proposed approach   413

15.3.1. Metaheuristics   414

15.3.2. Simulation model  421

15.4. Implementation and results    422

15.4.1. Impact on the work mode  423

15.4.2. Results of the set of modifications to the teachinghospital   425

15.4.3. Preliminary study of the choice of shifts  428

15.5. Conclusion   430

15.6. Bibliography 431

Chapter 16. Vehicle Routing Problems with SchedulingConstraints 433
Rahma LAHYANI, Frédéric SEMET and BenoîtTROUILLET

16.1. Introduction 433

16.2. Definition, complexity and classification  435

16.2.1. Definition and complexity   435

16.2.2. Classification   436

16.3. Time-constrained vehicle routing problems 438

16.3.1. Vehicle routing problems with time windows 438

16.3.2. Period vehicle routing problems 441

16.3.3. Vehicle routing problem with cross-docking 443

16.4. Vehicle routing problems with resource availabilityconstraints  448

16.4.1. Multi-trip vehicle routing problem   448

16.4.2. Vehicle routing problem with crew scheduling 450

16.5. Conclusion   452

16.6. Bibliography 453

Chapter 17. Metaheuristics for Job Shop Scheduling withTransportation 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 withtransportation resources    468

17.3. GTSB procedure  474

17.3.1. A hybrid metaheuristic algorithm for the GFJSSP 474

17.3.2. Tests and results 480

17.3.3. Conclusion for GTSB    489

17.4. Conclusion   491

17.5. Bibliography 491

List of Authors    495

Index  499

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews