运筹与模糊学  >> Vol. 5 No. 1 (February 2015)

基于EDA-GA的置换流水车间调度算法
A Hybrid EDA with GA for the Permutation Flow Shop Scheduling Problem

DOI: 10.12677/ORF.2015.51002, PDF, HTML, XML, 下载: 2,296  浏览: 9,110  国家自然科学基金支持

作者: 刘祝智, 王 恺:武汉大学经济与管理学院,湖北 武汉

关键词: 置换流水车间调度分布估计算法遗传算法模糊逻辑控制Permutation Flow Shop Scheduling Problem Estimation of Distribution Algorithm Genetic Algorithm Fuzzy Logic Controller

摘要: 置换流水车间调度问题是工业工程中经典的组合优化问题,一般采用智能优化算法来求解该问题。作为一种新颖的优化算法,分布估计算法主要使用统计学习的方法指导搜索过程。然而,这种算法容易陷入到局部最优而出现过早收敛的现象。本文将分布估计算法与遗传算法结合,通过模糊逻辑控制来调节两种算法生成个体的比例。该算法有利于保持种群的多样性,避免了过早收敛。以Car类和Rec类算例进行测试,实验结果证实了本文所提出的混合算法的有效性。
Abstract: The permutation flow shop scheduling problem is a classical combinatorial optimization in indus-trial engineering. Population-based evolutionary algorithms (EA) are the common methods to solve this problem. As a novel EA, estimation of distribution algorithm (EDA) directs the algorithm search towards good solutions by statistical learning. However, this algorithm may trap into the local optimal and lead to the premature convergence. To overcome the drawback of EDA, this paper incorporates EDA with GA to address the PFSP. The participation rates of EDA and GA are adaptively regulated by fuzzy logic controller. The experiment results on the benchmarks validate the efficiency of the proposed algorithm.

文章引用: 刘祝智, 王恺. 基于EDA-GA的置换流水车间调度算法[J]. 运筹与模糊学, 2015, 5(1): 6-13. http://dx.doi.org/10.12677/ORF.2015.51002

参考文献

[1] Pan, Q.-K., Suganhan, P.N., Tasgetiren, M.F. and Chua, T.J. (2011) A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem. Information Sciences, 181, 2455-2468.
[2] Johnson, S.M. (1954) Op-timal two-and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1, 61-68.
[3] Zhang, Y. and Li, X. (2011) Estimation of distribution algorithm for permutation flow shops with total flow time minimization. Computers & Industrial Engineering, 60, 706-718.
[4] 周驰, 高亮, 高海兵 (2006) 基于 PSO 的置换流水车间调度算法. 电子学报, 34, 2008-2011.
[5] Larranaga, P. and Lozano, J.A. (2002) Estimation of distribution algorithms: A new tool for evolutionary computation. Springer, Berlin.
[6] 叶宝林, 高慧敏, 王筱萍, 等 (2011) 基于分布估计算法的二阶段置换流水车间调度算法. 计算机应用研究, 10, 3702-3706.
[7] Chen, S.H., Chen, M.C., Chang, P.C., et al. (2010) Guidelines for developing effective estimation of distribution algorithms in solving single machine scheduling problems. Expert Systems with Applications, 37, 6441-6451.
[8] Chan, F.T.S., Prakash, A. and Mishra, N. (2013) Priority-based scheduling in flexible system using AIS with FLC approach. Interna-tional Journal of Production Research, 51, 4880-4895.
[9] Nawaz, M., Enscore Jr., E.E. and Ham, I. (1983) A heu-ristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11, 91-95.
[10] 王圣尧, 王凌, 许烨, 等 (2012) 求解混合流水车间调度问题的分布估计算法. 自动化学报, 3, 437-443.
[11] Wang, S., Wang, L., Liu, M., et al. (2013) An effective estimation of distribution algorithm for solving the distributed permutation flow-shop scheduling problem. International Journal of Production Economics, 145, 387-396.
[12] 何宏, 钱锋 (2006) 遗传算法参数自适应控制的新方法. 华东理工大学学报(自然科学版), 5, 601-606.
[13] Kim, K.W., Gen, M. and Yamazaki, G. (2003) Hybrid genetic algorithm with fuzzy logic for resource-constrained project scheduling. Applied Soft Computing, 2, 174-188.
[14] Kim, K.W., Yun, Y.S., Yoon, J.M., et al. (2005) Hybrid genetic algorithm with adaptive abilities for resource-con- strained multiple project scheduling. Computers in Industry, 56, 143-160.