Details

Metaheuristics for Production Scheduling


Metaheuristics for Production Scheduling


1. Aufl.

von: Bassem Jarboui, Patrick Siarry, Jacques Teghem

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
Neutron Applications in Earth, Energy and Environmental Sciences
von: Liyuan Liang, Romano Rinaldi, Helmut Schober
PDF ebook
CHF 177.00
Nanobioelectronics - for Electronics, Biology, and Medicine
Nanobioelectronics - for Electronics, Biology, and Medicine
von: Andreas Offenhäusser, Ross Rinaldi
PDF ebook
CHF 118.00
Autonomous Robots
Autonomous Robots
von: Farbod Fahimi
PDF ebook
CHF 136.00