期刊
IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING
卷 9, 期 3, 页码 578-595出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TASE.2012.2192729
关键词
Flow shops; genetic algorithm; makespan; sequence-dependent setup time; weighted tardiness
资金
- National Natural Science Foundation of China [60973073, 61070160]
- Program for New Century Excellent Talents in University [NCET-09-0290]
In this paper, adaptive hybrid genetic algorithms (AHA(0) similar to AHA(3)) are proposed for the sequence-dependent setup times permutation flow shop scheduling problem with the objectives to minimize makespan and total weighted tardiness, both of which will be considered separately. Each job is assigned an introduced inheriting factor, which indicates the probability that the job is copied to the same position of the offspring individual during crossover and is dynamically updated. Good genes and bad genes can be mined by inheriting factors. Probability-based Multi-Point Crossover (PMPC) is constructed to inherit good genes with high probabilities to the offspring and destroy bad genes with high probabilities. Inheriting factors determine such probabilities and the genetic algorithm evolves adaptively and is denoted as AHA(0). Three local search methods (LS1, LS2, and LS3) are separately integrated with AHA(0) and three hybrid algorithms AHA(1) similar to AHA(3) are developed. Compared with GA_RMA and CPSO (effective algorithms without integrating any local search), AHA(0) is the most effective. Another six hybrid algorithms are extended from IG_RS (the current best algorithm for the two considered problems) and CPSO by integrating with the three local search methods and they are compared with AHA(1) similar to AHA(3) comprehensively. Experimental results show that for the two considered problems, AHA(1) outperforms the other algorithms on small setup-time instances and AHA(3) is the most effective algorithm among the compared ones on big setup-time instances, while the computation time of AHA(1) is moderate among the LS1 integrated algorithms, so is AHA(3). The effects of the key factors or parameters on algorithms are analyzed as well.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据