Contents
1 Multiobjective Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 General Structure of a Genetic Algorithm . . . . . . . . . . . . . . . . 2
1.1.2 Exploitation and Exploration . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.3 Population-based Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.4 Major Advantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Implementation of Genetic Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 GA Vocabulary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.2 Encoding Issue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.3 Fitness Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.4 Genetic Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.5 Handling Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3 Hybrid Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3.1 Genetic Local Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3.2 Parameter Adaptation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.4 Multiobjective Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.4.1 Basic Concepts of Multiobjective Optimizations . . . . . . . . . . 26
1.4.2 Features and Implementation of Multiobjective GA . . . . . . . . 29
1.4.3 Fitness Assignment Mechanism . . . . . . . . . . . . . . . . . . . . . . . . 30
1.4.4 Performance Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2 Basic Network Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.1.1 Shortest Path Model: Node Selection and Sequencing . . . . . . 50
2.1.2 Spanning Tree Model: Arc Selection . . . . . . . . . . . . . . . . . . . . 51
2.1.3 Maximum Flow Model: Arc Selection and Flow Assignment 52
2.1.4 Representing Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.1.5 Algorithms and Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.1.6 NP-Complete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.1.7 List of NP-complete Problems in Network Design . . . . . . . . . 56
2.2 Shortest Path Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
2.2.1 Mathematical Formulation of the SPP Models . . . . . . . . . . . . 58
2.2.2 Priority-based GA for SPP Models . . . . . . . . . . . . . . . . . . . . . . 60
2.2.3 Computational Experiments and Discussions . . . . . . . . . . . . . 72
2.3 Minimum Spanning Tree Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
2.3.1 Mathematical Formulation of the MST Models . . . . . . . . . . . 83
2.3.2 PrimPred-based GA for MST Models . . . . . . . . . . . . . . . . . . . 85
2.3.3 Computational Experiments and Discussions . . . . . . . . . . . . . 96
2.4 Maximum Flow Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
2.4.1 Mathematical Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
2.4.2 Priority-based GA for MXF Model . . . . . . . . . . . . . . . . . . . . . 100
2.4.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
2.5 Minimum Cost Flow Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
2.5.1 Mathematical Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
2.5.2 Priority-based GA for MCF Model . . . . . . . . . . . . . . . . . . . . . 110
2.5.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
2.6 Bicriteria MXF/MCF Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
2.6.1 Mathematical Formulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
2.6.2 Priority-based GA for bMXF/MCF Model . . . . . . . . . . . . . . . 119
2.6.3 i-awGA for bMXF/MCF Model . . . . . . . . . . . . . . . . . . . . . . . . 123
2.6.4 Experiments and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
3 Logistics Network Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
3.2 Basic Logistics Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
3.2.1 Mathematical Formulation of the Logistics Models . . . . . . . . 139
3.2.2 Pr¨ufer Number-based GA for the Logistics Models . . . . . . . . 146
3.2.3 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
3.3 Location Allocation Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
3.3.1 Mathematical Formulation of the Logistics Models . . . . . . . . 156
3.3.2 Location-based GA for the Location Allocation Models . . . . 159
3.3.3 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
3.4 Multi-stage Logistics Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
3.4.1 Mathematical Formulation of the Multi-stage Logistics . . . . 176
3.4.2 Priority-based GA for the Multi-stage Logistics . . . . . . . . . . . 185
3.4.3 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
3.5 Flexible Logistics Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
3.5.1 Mathematical Formulation of the Flexible Logistics Model . 196
3.5.2 Direct Path-based GA for the Flexible Logistics Model . . . . 202
3.5.3 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
3.6 Integrated Logistics Model with Multi-time Period and Inventory . . 208
3.6.1 Mathematical Formulation of the Integrated Logistics
Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
3.6.2 Extended Priority-based GA for the Integrated Logistics
Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
3.6.3 Local Search Technique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
3.6.4 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
3.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
4 Communication Network Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
4.2 Centralized Network Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
4.2.1 Capacitated Multipoint Network Models . . . . . . . . . . . . . . . . . 235
4.2.2 Capacitated QoS Network Model . . . . . . . . . . . . . . . . . . . . . . . 242
4.3 Backbone Network Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
4.3.1 Pierre and Legault’s Approach . . . . . . . . . . . . . . . . . . . . . . . . . 248
4.3.2 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
4.3.3 Konak and Smith’s Approach . . . . . . . . . . . . . . . . . . . . . . . . . . 253
4.3.4 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
4.4 Reliable Network Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
4.4.1 Reliable Backbone Network Model . . . . . . . . . . . . . . . . . . . . . 259
4.4.2 Reliable Backbone Network Model with Multiple Goals . . . 269
4.4.3 Bicriteria Reliable Network Model of LAN . . . . . . . . . . . . . . 274
4.4.4 Bi-level Network Design Model . . . . . . . . . . . . . . . . . . . . . . . . 283
4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
5 Advanced Planning and Scheduling Models . . . . . . . . . . . . . . . . . . . . . . . 297
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
5.2 Job-shop Scheduling Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
5.2.1 Mathematical Formulation of JSP . . . . . . . . . . . . . . . . . . . . . . 304
5.2.2 Conventional Heuristics for JSP . . . . . . . . . . . . . . . . . . . . . . . . 305
5.2.3 Genetic Representations for JSP . . . . . . . . . . . . . . . . . . . . . . . . 316
5.2.4 Gen-Tsujimura-Kubota’s Approach . . . . . . . . . . . . . . . . . . . . . 325
5.2.5 Cheng-Gen-Tsujimura’s Approach . . . . . . . . . . . . . . . . . . . . . . 326
5.2.6 Gonc¸alves-Magalhacs-Resende’s Approach . . . . . . . . . . . . . . 330
5.2.7 Experiment on Benchmark Problems . . . . . . . . . . . . . . . . . . . . 335
5.3 Flexible Job-shop Scheduling Model . . . . . . . . . . . . . . . . . . . . . . . . . . 337
5.3.1 Mathematical Formulation of fJSP . . . . . . . . . . . . . . . . . . . . . . 338
5.3.2 Genetic Representations for fJSP . . . . . . . . . . . . . . . . . . . . . . . 340
5.3.3 Multistage Operation-based GA for fJSP . . . . . . . . . . . . . . . . 344
5.3.4 Experiment on Benchmark Problems . . . . . . . . . . . . . . . . . . . . 353
5.4 Integrated Operation Sequence and Resource Selection Model . . . . . 355
5.4.1 Mathematical Formulation of iOS/RS . . . . . . . . . . . . . . . . . . . 358
5.4.2 Multistage Operation-based GA for iOS/RS . . . . . . . . . . . . . . 363
5.4.3 Experiment and Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
5.5 Integrated Scheduling Model with Multi-plant . . . . . . . . . . . . . . . . . . 376
5.5.1 Integrated Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
5.5.2 Mathematical Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
5.5.3 Multistage Operation-based GA . . . . . . . . . . . . . . . . . . . . . . . . 383
5.5.4 Numerical Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389
5.6 Manufacturing and Logistics Model with Pickup and Delivery . . . . . 395
5.6.1 Mathematical Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
5.6.2 Multiobjective Hybrid Genetic Algorithm . . . . . . . . . . . . . . . . 399
5.6.3 Numerical Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
5.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412
6 Project Scheduling Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419
6.2 Resource-constrained Project Scheduling Model . . . . . . . . . . . . . . . . . 421
6.2.1 Mathematical Formulation of rc-PSP Models . . . . . . . . . . . . . 422
6.2.2 Hybrid GA for rc-PSP Models . . . . . . . . . . . . . . . . . . . . . . . . . 426
6.2.3 Computational Experiments and Discussions . . . . . . . . . . . . . 434
6.3 Resource-constrained Multiple Project Scheduling Model . . . . . . . . . 438
6.3.1 Mathematical Formulation of rc-mPSP Models . . . . . . . . . . . 440
6.3.2 Hybrid GA for rc-mPSP Models . . . . . . . . . . . . . . . . . . . . . . . . 444
6.3.3 Computational Experiments and Discussions . . . . . . . . . . . . . 451
6.4 Resource-constrained Project Scheduling Model with Multiple
Modes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
6.4.1 Mathematical Formulation of rc-PSP/mM Models . . . . . . . . . 457
6.4.2 Adaptive Hybrid GA for rc-PSP/mM Models . . . . . . . . . . . . . 461
6.4.3 Numerical Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470
6.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472
7 Assembly Line Balancing Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
7.2 Simple Assembly Line Balancing Model . . . . . . . . . . . . . . . . . . . . . . . 480
7.2.1 Mathematical Formulation of sALB Models . . . . . . . . . . . . . . 480
7.2.2 Priority-based GA for sALB Models . . . . . . . . . . . . . . . . . . . . 484
7.2.3 Computational Experiments and Discussions . . . . . . . . . . . . . 492
7.3 U-shaped Assembly Line Balancing Model . . . . . . . . . . . . . . . . . . . . . 493
7.3.1 Mathematical Formulation of uALB Models . . . . . . . . . . . . . 495
7.3.2 Priority-based GA for uALB Models . . . . . . . . . . . . . . . . . . . . 499
7.3.3 Computational Experiments and Discussions . . . . . . . . . . . . . 505
7.4 Robotic Assembly Line Balancing Model . . . . . . . . . . . . . . . . . . . . . . 505
7.4.1 Mathematical Formulation of rALB Models . . . . . . . . . . . . . . 509
7.4.2 Hybrid GA for rALB Models . . . . . . . . . . . . . . . . . . . . . . . . . . 512
7.4.3 Computational Experiments and Discussions . . . . . . . . . . . . . 523
7.5 Mixed-model Assembly Line Balancing Model . . . . . . . . . . . . . . . . . 526
7.5.2 Hybrid GA for mALB Models . . . . . . . . . . . . . . . . . . . . . . . . . 532
7.5.3 Rekiek and Delchambre’s Approach . . . . . . . . . . . . . . . . . . . . 542
7.5.4 Ozmehmet Tasan and Tunali’s Approach . . . . . . . . . . . . . . . . 543
7.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546
8 Tasks Scheduling Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 551
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 551
8.1.1 Hard Real-time Task Scheduling . . . . . . . . . . . . . . . . . . . . . . . 553
8.1.2 Soft Real-time Task Scheduling . . . . . . . . . . . . . . . . . . . . . . . . 557
8.2 Continuous Task Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 562
8.2.1 Continuous Task Scheduling Model on Uniprocessor
8.2.2 Continuous Task Scheduling Model on Multiprocessor
System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575
8.3 Real-time Task Scheduling in Homogeneous Multiprocessor . . . . . . 583
8.3.1 Soft Real-time Task Scheduling Problem (sr-TSP) and
Mathematical Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584
8.3.2 Multiobjective GA for srTSP . . . . . . . . . . . . . . . . . . . . . . . . . . 586
8.3.3 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 592
8.4 Real-time Task Scheduling in Heterogeneous Multiprocessor
8.4.1 Soft Real-time Task Scheduling Problem (sr-TSP) and
Mathematical Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595
8.4.2 SA-based Hybrid GA Approach . . . . . . . . . . . . . . . . . . . . . . . . 597
8.4.3 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 601
8.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 602
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604
9 Advanced Network Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 607
9.1 Airline Fleet Assignment Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 607
9.1.1 Fleet Assignment Model with Connection Network . . . . . . . . 613
9.1.2 Fleet Assignment Model with Time-space Network . . . . . . . . 624
9.2 Container Terminal Network Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 636
9.2.1 Berth Allocation Planning Model . . . . . . . . . . . . . . . . . . . . . . . 639
9.2.2 Multi-stage Decision-based GA . . . . . . . . . . . . . . . . . . . . . . . . 643
9.2.3 Numerical Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646
9.3 AGV Dispatching Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 651
9.3.1 Network Modeling and Mathematical Formulation . . . . . . . . 652
9.3.2 Random Key-based GA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 658
9.3.3 Numerical Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664
9.4 Car Navigation Routing Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 666
9.4.1 Data Analyzing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 682
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 687
9.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 681
9.4.2 Mathematical Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 670
9.4.3 Improved Fixed Length-based GA . . . . . . . . . . . . . . . . . . . . . . 672
9.4.4 Numerical Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 677
Another Genetic Algorithm Books
Download
No comments:
Post a Comment