Details
Metaheuristics for Production Scheduling
1. Aufl.
CHF 157.00 |
|
Verlag: | Wiley |
Format: | EPUB |
Veröffentl.: | 12.06.2013 |
ISBN/EAN: | 9781118731567 |
Sprache: | englisch |
Anzahl Seiten: | 528 |
DRM-geschütztes eBook, Sie benötigen z.B. Adobe Digital Editions und eine Adobe ID zum Lesen.
Beschreibungen
<p>This book describes the potentialities of metaheuristics for solving production scheduling problems and the relationship between these two fields.<br /> 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.<br /> 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.</p> <p>Contents</p> <p>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ï.<br /> 2. Genetic Algorithms for Solving Flexible Job Shop Scheduling Problems, Imed Kacem.<br /> 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ï.<br /> 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.<br /> 5. Neutrality in Flow Shop Scheduling Problems: Landscape Structure and Local Search, Marie-Eléonore Marmion.<br /> 6. Evolutionary Metaheuristic Based on Genetic Algorithm: Application to Hybrid Flow Shop Problem with Availability Constraints, Nadia Chaaben, Racem Mellouli and Faouzi Masmoudi.<br /> 7. Models and Methods in Graph Coloration for Various Production Problems, Nicolas Zufferey.<br /> 8. Mathematical Programming and Heuristics for Scheduling Problems with Early and Tardy Penalties, Mustapha Ratli, Rachid Benmansour, Rita Macedo, Saïd Hanafi, Christophe Wilbaut.<br /> 9. Metaheuristics for Biobjective Flow Shop Scheduling, Matthieu Basseur and Arnaud Liefooghe.<br /> 10. Pareto Solution Strategies for the Industrial Car Sequencing Problem, Caroline Gagné, Arnaud Zinflou and Marc Gravel.<br /> 11. Multi-Objective Metaheuristics for the Joint Scheduling of Production and Maintenance, Ali Berrichi and Farouk Yalaoui.<br /> 12. Optimization via a Genetic Algorithm Parametrizing the AHP Method for Multicriteria Workshop Scheduling, Fouzia Ounnar, Patrick Pujo and Afef Denguir.<br /> 13. A Multicriteria Genetic Algorithm for the Resource-constrained Task Scheduling Problem, Olfa Dridi, Saoussen Krichen and Adel Guitouni.<br /> 14. Metaheuristics for the Solution of Vehicle Routing Problems in a Dynamic Context, Tienté Hsu, Gilles Gonçalves and Rémy Dupas.<br /> 15. Combination of a Metaheuristic and a Simulation Model for the Scheduling of Resource-constrained Transport Activities, Virginie André, Nathalie Grangeon and Sylvie Norre.<br /> 16. Vehicle Routing Problems with Scheduling Constraints, Rahma Lahyani, Frédéric Semet and Benoît Trouillet.<br /> 17. Metaheuristics for Job Shop Scheduling with Transportation, Qiao Zhang, Hervé Manier, Marie-Ange Manier.<br /> <br /> </p> <p>About the Authors</p> <p>Bassem Jarboui is Professor at the University of Sfax, Tunisia.<br /> Patrick Siarry is Professor at the Laboratoire Images, Signaux et Systèmes Intelligents (LISSI), University of Paris-Est Créteil, France.<br /> Jacques Teghem is Professor at the University of Mons, Belgium.</p>
<p>Introduction and Presentation xv<br /> <i>Bassem JARBOUI, Patrick SIARRY and Jacques TEGHEM</i></p> <p><b>Chapter 1. An Estimation of Distribution Algorithm for Solving Flow Shop Scheduling Problems with Sequence-dependent Family Setup Times 1</b><br /> <i>Mansour EDDALY, Bassem JARBOUI, Radhouan BOUABDA, Patrick SIARRY and Abdelwaheb REBAÏ</i></p> <p>1.1. Introduction 1</p> <p>1.2. Mathematical formulation 3</p> <p>1.3. Estimation of distribution algorithms 5</p> <p>1.3.1. Estimation of distribution algorithms proposed in the literature 6</p> <p>1.4. The proposed estimation of distribution algorithm 8</p> <p>1.4.1. Encoding scheme and initial population 8</p> <p>1.4.2. Selection 9</p> <p>1.4.3. Probability estimation 9</p> <p>1.5. Iterated local search algorithm 10</p> <p>1.6. Experimental results 11</p> <p>1.7. Conclusion 15</p> <p>1.8. Bibliography 15</p> <p><b>Chapter 2. Genetic Algorithms for Solving Flexible Job Shop Scheduling Problems 19</b><br /> <i>Imed KACEM</i></p> <p>2.1. Introduction 19</p> <p>2.2. Flexible job shop scheduling problems 19</p> <p>2.3. Genetic algorithms for some related sub-problems 25</p> <p>2.4. Genetic algorithms for the flexible job shop problem 31</p> <p>2.4.1. Codings 31</p> <p>2.4.2. Mutation operators 34</p> <p>2.4.3. Crossover operators 38</p> <p>2.5. Comparison of codings 42</p> <p>2.6. Conclusion 43</p> <p>2.7. Bibliography 43</p> <p><b>Chapter 3. A Hybrid GRASP-Differential Evolution Algorithm for Solving Flow Shop Scheduling Problems with No-Wait Constraints 45</b><br /> <i>Hanen AKROUT, Bassem JARBOUI, Patrick SIARRY and Abdelwaheb REBAÏ</i></p> <p>3.1. Introduction 45</p> <p>3.2. Overview of the literature 47</p> <p>3.2.1. Single-solution metaheuristics 47</p> <p>3.2.2. Population-based metaheuristics 49</p> <p>3.2.3. Hybrid approaches 49</p> <p>3.3. Description of the problem 50</p> <p>3.4. GRASP 52</p> <p>3.5. Differential evolution 53</p> <p>3.6. Iterative local search 55</p> <p>3.7. Overview of the NEW-GRASP-DE algorithm 55</p> <p>3.7.1. Constructive phase 56</p> <p>3.7.2. Improvement phase 57</p> <p>3.8. Experimental results 57</p> <p>3.8.1. Experimental results for the Reeves and Heller instances 58</p> <p>3.8.2. Experimental results for the Taillard instances 60</p> <p>3.9. Conclusion 62</p> <p>3.10. Bibliography 64</p> <p><b>Chapter 4. A Comparison of Local Search Metaheuristics for a Hierarchical Flow Shop Optimization Problem with Time Lags 69</b><br /> <i>Emna DHOUIB, Jacques TEGHEM, Daniel TUYTTENS and Taïcir LOUKIL</i></p> <p>4.1. Introduction 69</p> <p>4.2. Description of the problem 70</p> <p>4.2.1. Flowshop with time lags 70</p> <p>4.2.2. A bicriteria hierarchical flow shop problem 71</p> <p>4.3. The proposed metaheuristics 73</p> <p>4.3.1. A simulated annealing metaheuristics 74</p> <p>4.3.2. The GRASP metaheuristics 77</p> <p>4.4. Tests 82</p> <p>4.4.1. Generated instances 82</p> <p>4.4.2. Comparison of the results 83</p> <p>4.5. Conclusion 94</p> <p>4.6. Bibliography 94</p> <p><b>Chapter 5. Neutrality in Flow Shop Scheduling Problems: Landscape Structure and Local Search 97</b><br /> <i>Marie-Eléonore MARMION</i></p> <p>5.1. Introduction 97</p> <p>5.2. Neutrality in a combinatorial optimization problem 98</p> <p>5.2.1. Landscape in a combinatorial optimization problem 99</p> <p>5.2.2. Neutrality and landscape 102</p> <p>5.3. Study of neutrality in the flow shop problem 106</p> <p>5.3.1. Neutral degree 106</p> <p>5.3.2. Structure of the neutral landscape 108</p> <p>5.4. Local search exploiting neutrality to solve the flow shop problem 112</p> <p>5.4.1. Neutrality-based iterated local search 113</p> <p>5.4.2. NILS on the flow shop problem 116</p> <p>5.5. Conclusion 122</p> <p>5.6. Bibliography 123</p> <p><b>Chapter 6. Evolutionary Metaheuristic Based on Genetic Algorithm: Application to Hybrid Flow Shop Problem with Availability Constraints 127</b><br /> <i>Nadia CHAABEN, Racem MELLOULI and Faouzi MASMOUDI</i></p> <p>6.1. Introduction 127</p> <p>6.2. Overview of the literature 128</p> <p>6.3. Overview of the problem and notations used 131</p> <p>6.4. Mathematical formulations 133</p> <p>6.4.1. First formulation (MILP1) 133</p> <p>6.4.2. Second formulation (MILP2) 135</p> <p>6.4.3. Third formulation (MILP3) 137</p> <p>6.5. A genetic algorithm: model and methodology 139</p> <p>6.5.1. Coding used for our algorithm 139</p> <p>6.5.2. Generating the initial population 140</p> <p>6.5.3. Selection operator 142</p> <p>6.5.4. Crossover operator 142</p> <p>6.5.5. Mutation operator 144</p> <p>6.5.6. Insertion operator 144</p> <p>6.5.7. Evaluation function: fitness 144</p> <p>6.5.8. Stop criterion 145</p> <p>6.6. Verification and validation of the genetic algorithm 145</p> <p>6.6.1. Description of benchmarks 145</p> <p>6.6.2. Tests and results 146</p> <p>6.7. Conclusion 148</p> <p>6.8. Bibliography 148</p> <p><b>Chapter 7. Models and Methods in Graph Coloration for Various Production Problems 153</b><br /> <i>Nicolas ZUFFEREY</i></p> <p>7.1. Introduction 153</p> <p>7.2. Minimizing the makespan 155</p> <p>7.2.1. Tabu algorithm 155</p> <p>7.2.2. Hybrid genetic algorithm 157</p> <p>7.2.3. Methods prior to GH 158</p> <p>7.2.4. Extensions 159</p> <p>7.3. Maximizing the number of completed tasks 160</p> <p>7.3.1. Tabu algorithm 161</p> <p>7.3.2. The ant colony algorithm 162</p> <p>7.3.3. Extension of the problem 164</p> <p>7.4. Precedence constraints 165</p> <p>7.4.1. Tabu algorithm 168</p> <p>7.4.2. Variable neighborhood search method 169</p> <p>7.5. Incompatibility costs 171</p> <p>7.5.1. Tabu algorithm 173</p> <p>7.5.2. Adaptive memory method 175</p> <p>7.5.3. Variations of the problem 177</p> <p>7.6. Conclusion 178</p> <p>7.7. Bibliography 179</p> <p><b>Chapter 8. Mathematical Programming and Heuristics for Scheduling Problems with Early and Tardy Penalties 183</b><br /> <i>Mustapha RATLI, Rachid BENMANSOUR, Rita MACEDO, Saïd HANAFI, Christophe WILBAUT</i></p> <p>8.1. Introduction 183</p> <p>8.2. Properties and particular cases 185</p> <p>8.3. Mathematical models 188</p> <p>8.3.1. Linear models with precedence variables 188</p> <p>8.3.2. Linear models with position variables 192</p> <p>8.3.3. Linear models with time-indexed variables 194</p> <p>8.3.4. Network flow models 197</p> <p>8.3.5. Quadratic models 197</p> <p>8.3.6. A comparative study 199</p> <p>8.4. Heuristics 203</p> <p>8.4.1. Properties 207</p> <p>8.4.2. Evaluation 209</p> <p>8.5. Metaheuristics 211</p> <p>8.6. Conclusion 217</p> <p>8.7. Acknowledgments 218</p> <p>8.8. Bibliography 218</p> <p><b>Chapter 9. Metaheuristics for Biobjective Flow Shop Scheduling 225</b><br /> <i>Matthieu BASSEUR and Arnaud LIEFOOGHE</i></p> <p>9.1. Introduction 225</p> <p>9.2. Metaheuristics for multiobjective combinatorial optimization 226</p> <p>9.2.1. Main concepts 227</p> <p>9.2.2. Some methods 229</p> <p>9.2.3. Performance analysis 232</p> <p>9.2.4. Software and implementation 237</p> <p>9.3. Multiobjective flow shop scheduling problems 238</p> <p>9.3.1. Flow shop problems 239</p> <p>9.3.2. Permutation flow shop with due dates 240</p> <p>9.3.3. Different objective functions 241</p> <p>9.3.4. Sets of data 241</p> <p>9.3.5. Analysis of correlations between objectives functions 242</p> <p>9.4. Application to the biobjective flow shop 243</p> <p>9.4.1. Model 244</p> <p>9.4.2. Solution methods 246</p> <p>9.4.3. Experimental analysis 246</p> <p>9.5. Conclusion 249</p> <p>9.6. Bibliography 250</p> <p><b>Chapter 10. Pareto Solution Strategies for the Industrial Car Sequencing Problem 253</b><br /> <i>Caroline GAGNÉ, Arnaud ZINFLOU and Marc GRAVEL</i></p> <p>10.1. Introduction 253</p> <p>10.2. Industrial car sequencing problem 255</p> <p>10.3. Pareto strategies for solving the CSP 260</p> <p>10.3.1. PMSMO 260</p> <p>10.3.2. GISMOO 264</p> <p>10.4. Numerical experiments 268</p> <p>10.4.1. Test sets 269</p> <p>10.4.2. Performance metrics 270</p> <p>10.5. Results and discussion 271</p> <p>10.6. Conclusion 279</p> <p>10.7. Bibliography 280</p> <p><b>Chapter 11. Multi-Objective Metaheuristics for the Joint Scheduling of Production and Maintenance 283</b><br /> <i>Ali BERRICHI and Farouk YALAOUI</i></p> <p>11.1. Introduction 283</p> <p>11.2. State of the art on the joint problem 285</p> <p>11.3. Integrated modeling of the joint problem 287</p> <p>11.4. Concepts of multi-objective optimization 291</p> <p>11.5. The particle swarm optimization method 292</p> <p>11.6. Implementation of MOPSO algorithms 294</p> <p>11.6.1. Representation and construction of the solutions 294</p> <p>11.6.2. Solution Evaluation 295</p> <p>11.6.3. The proposed MOPSO algorithms 298</p> <p>11.6.4. Updating the velocities and positions 299</p> <p>11.6.5. Hybridization with local searches 300</p> <p>11.7. Experimental results 302</p> <p>11.7.1. Choice of test problems and configurations 302</p> <p>11.7.2. Experiments and analysis of the results 303</p> <p>11.8. Conclusion 310</p> <p>11.9. Bibliography 311</p> <p><b>Chapter 12. Optimization via a Genetic Algorithm Parametrizing the AHP Method for Multicriteria Workshop Scheduling 315</b><br /> <i>Fouzia OUNNAR, Patrick PUJO and Afef DENGUIR</i></p> <p>12.1. Introduction 315</p> <p>12.2. Methods for solving multicriteria scheduling 316</p> <p>12.2.1. Optimization methods 316</p> <p>12.2.2. Multicriteria decision aid methods 318</p> <p>12.2.3. Choice of the multicriteria decision aid method 319</p> <p>12.3. Presentation of the AHP method 320</p> <p>12.3.1. Phase 1: configuration 320</p> <p>12.3.2. Phase 2: exploitation 321</p> <p>12.4. Evaluation of metaheuristics for the configuration of AHP 322</p> <p>12.4.1. Local search methods 323</p> <p>12.4.2. Population-based methods 324</p> <p>12.4.3. Advanced metaheuristics 326</p> <p>12.5. Choice of metaheuristic 326</p> <p>12.5.1. Justification of the choice of genetic algorithms 326</p> <p>12.5.2. Genetic algorithms 328</p> <p>12.6. AHP optimization by a genetic algorithm 330</p> <p>12.6.1. Phase 0: configuration of the structure of the problem 331</p> <p>12.6.2. Phase 1: preparation for automatic configuration 332</p> <p>12.6.3. Phase 2: automatic configuration 334</p> <p>12.6.4. Phase 3: preparation of the exploitation phase 335</p> <p>12.7. Evaluation of G-AHP 336</p> <p>12.7.1. Analysis of the behavior of G-AHP 336</p> <p>12.7.2. Analysis of the results obtained by G-AHP 342</p> <p>12.8. Conclusions 343</p> <p>12.9. Bibliography 344</p> <p><b>Chapter 13. A Multicriteria Genetic Algorithm for the Resource-constrained Task Scheduling Problem 349</b><br /> <i>Olfa DRIDI, Saoussen KRICHEN and Adel GUITOUNI</i></p> <p>13.1. Introduction 349</p> <p>13.2. Description and formulation of the problem 350</p> <p>13.3. Literature review 353</p> <p>13.3.1. Exact methods 354</p> <p>13.3.2. Approximate methods 355</p> <p>13.4. A multicriteria genetic algorithm for the MMSAP 356</p> <p>13.4.1. Encoding variables 357</p> <p>13.4.2. Genetic operators 358</p> <p>13.4.3. Parameter settings 359</p> <p>13.4.4. The GA 360</p> <p>13.5. Experimental study 361</p> <p>13.5.1. Diversification of the approximation set based on the diversity indicators 364</p> <p>13.6. Conclusion 369</p> <p>13.7. Bibliography 369</p> <p><b>Chapter 14. Metaheuristics for the Solution of Vehicle Routing Problems in a Dynamic Context 373</b><br /> <i>Tienté HSU, Gilles GONÇALVES and Rémy DUPAS</i></p> <p>14.1. Introduction 373</p> <p>14.2. Dynamic vehicle route management 375</p> <p>14.2.1. The vehicle routing problem with time windows 377</p> <p>14.3. Platform for the solution of the DVRPTW 382</p> <p>14.3.1. Encoding a chromosome 384</p> <p>14.4. Treating uncertainties in the orders 386</p> <p>14.5. Treatment of traffic information 392</p> <p>14.6. Conclusion 397</p> <p>14.7. Bibliography 398</p> <p><b>Chapter 15. Combination of a Metaheuristic and a Simulation Model for the Scheduling of Resource-constrained Transport Activities 401</b><br /> <i>Virginie ANDRÉ, Nathalie GRANGEON and Sylvie NORRE</i></p> <p>15.1. Knowledge model 403</p> <p>15.1.1. Fixed resources and mobile resources 403</p> <p>15.1.2. Modelling the activities in steps 404</p> <p>15.1.3. The problem to be solved 406</p> <p>15.1.4. Illustrative example 407</p> <p>15.2. Solution procedure 410</p> <p>15.3. Proposed approach 413</p> <p>15.3.1. Metaheuristics 414</p> <p>15.3.2. Simulation model 421</p> <p>15.4. Implementation and results 422</p> <p>15.4.1. Impact on the work mode 423</p> <p>15.4.2. Results of the set of modifications to the teaching hospital 425</p> <p>15.4.3. Preliminary study of the choice of shifts 428</p> <p>15.5. Conclusion 430</p> <p>15.6. Bibliography 431</p> <p><b>Chapter 16. Vehicle Routing Problems with Scheduling Constraints 433</b><br /> <i>Rahma LAHYANI, Frédéric SEMET and Benoît TROUILLET</i></p> <p>16.1. Introduction 433</p> <p>16.2. Definition, complexity and classification 435</p> <p>16.2.1. Definition and complexity 435</p> <p>16.2.2. Classification 436</p> <p>16.3. Time-constrained vehicle routing problems 438</p> <p>16.3.1. Vehicle routing problems with time windows 438</p> <p>16.3.2. Period vehicle routing problems 441</p> <p>16.3.3. Vehicle routing problem with cross-docking 443</p> <p>16.4. Vehicle routing problems with resource availability constraints 448</p> <p>16.4.1. Multi-trip vehicle routing problem 448</p> <p>16.4.2. Vehicle routing problem with crew scheduling 450</p> <p>16.5. Conclusion 452</p> <p>16.6. Bibliography 453</p> <p><b>Chapter 17. Metaheuristics for Job Shop Scheduling with Transportation 465</b><br /> <i>Qiao ZHANG, Hervé MANIER, Marie-Ange MANIER</i></p> <p>17.1. General flexible job shop scheduling problems 466</p> <p>17.2. State of the art on job shop scheduling with transportation resources 468</p> <p>17.3. GTSB procedure 474</p> <p>17.3.1. A hybrid metaheuristic algorithm for the GFJSSP 474</p> <p>17.3.2. Tests and results 480</p> <p>17.3.3. Conclusion for GTSB 489</p> <p>17.4. Conclusion 491</p> <p>17.5. Bibliography 491</p> <p>List of Authors 495</p> <p>Index 499</p>
<p><strong>Bassem Jarboui</strong>, Laboratoire MODILS, University of Sfax, Tunisia. <p><strong>Patrick Siarry</strong>, Laboratoire LiSSi, University of Paris-Est Créteil, France. <p><strong>Jacques Teghem</strong>, MathRO / Polytechnic Faculty of Mons, Belgium.
Diese Produkte könnten Sie auch interessieren:
Neutron Applications in Earth, Energy and Environmental Sciences
von: Liyuan Liang, Romano Rinaldi, Helmut Schober
CHF 177.00
Nanobioelectronics - for Electronics, Biology, and Medicine
von: Andreas Offenhäusser, Ross Rinaldi
CHF 118.00