An Estimation of Distribution Algorithm for Solving Hybrid Flow-shop Scheduling Problem
-
摘要: 针对混合流水车间调度问题(Hybrid flow-shop scheduling problem, HFSP)的特点, 设计了基于排列的编码和解码方法, 建立了描述问题解空间的概率模型, 进而提出了一种有效的分布估计算法(Estimation of distribution algorithm, EDA). 该算法基于概率模型通过采样产生新个体, 并基于优势种群更新概率模型的参数. 同时, 通过实验设计方法对算法参数设置进行了分析并确定了有效的参数组合. 最后, 通过基于实例的数值仿真以及与已有算法的比较验证了所提算法的有效性和鲁棒性.Abstract: According to the characteristics of the hybrid flow-shop scheduling problem (HFSP), the permutation based encoding and decoding schemes are designed and a probability model for describing the distribution of the solution space is built to propose an effective estimation of distribution algorithm (EDA) in this paper. It generates new individuals by sampling based on the probability model and updates the parameters of the probability model with the superior population. Moreover, the influence of parameter setting is investigated based on design of experiment and suitable parameter values are suggested. Simulation results based on some instances and comparisons with some existing algorithms demonstrate the effectiveness and robustness of the proposed algorithm.
-
[1] Wang Ling. Shop Scheduling with Genetic Algorithms. Beijing: Tsinghua University Press, 2003. 138-145(王凌. 车间调度及其遗传算法. 北京: 清华大学出版社, 2003. 138-145)[2] Wang Ling, Zhou Gang, Xu Ye, Jin Yi-Hui. Advances in the study on hybrid flow-shop scheduling. Control and Instrument in Chemical Industry, 2011, 38(1): 1-8(王凌, 周刚, 许烨, 金以慧. 混合流水线调度研究进展. 化工自动化及仪表, 2011, 38(1): 1-8)[3] Hoogeveen J A, Lenstra J K, Veltman B. Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard. European Journal of Operational Research, 1996, 89(1): 172-175[4] Portmann M C, Vignier A, Dardilhac D, Dezalay D. Branch and bound crossed with GA to solve hybrid flowshops. European Journal of Operational Research, 1998, 107(2): 389-400[5] Soewandi H, Elmaghraby S E. Sequencing on two-stage hybrid flowshops with uniform machines to minimize makespan. IIE Transactions, 2003, 35(5): 467-477[6] Figielska E. A genetic algorithm and a simulated annealing algorithm combined with column generation technique for solving the problem of scheduling in the hybrid flowshop with additional resources. Computers and Industrial Engineering, 2009, 56(1): 142-151[7] Xuan Hua, Tang Li-Xin. Lagrangian relaxation algorithm for real-time hybrid flow-shop scheduling with no-wait in process. Control and Decision, 2006, 21(4): 376-380(轩华, 唐立新. 实时无等待HFS调度的一种拉格朗日松弛算法. 控制与决策, 2006, 21(4): 376-380)[8] Riane F, Artiba A, Elmaghraby S E. Sequencing a hybrid two-stage flowshop with dedicated machines. International Journal of Production Research, 2002, 40(17): 4353-4380[9] Zhou Hui-Ren, Tang Wan-Sheng, Wei Ying-Hui. Optimize flexible flow-shop scheduling using genetic algorithm. Computer Engineering and Applications, 2009, 45(30): 224-226(周辉仁, 唐万生, 魏颖辉. 柔性Flow-Shop调度的遗传算法优化. 计算机工程与应用, 2009, 45(30): 224-226)[10] Low C. Simulated annealing heuristic for flow shop scheduling problems with unrelated parallel machines. Computers and Operations Research, 2005, 32(8): 2013-2025[11] Wang X, Tang L. A tabu search heuristic for the hybrid flowshop scheduling with finite intermediate buffers. Computers and Operations Research, 2009, 36(3): 907-918[12] Alaykyran K, Engin O, Doyen A. Using ant colony optimization to solve hybrid flow shop scheduling problems. The International Journal of Advanced Manufacturing Technology, 2007, 35(5-6): 541-550[13] Tseng C T, Liao C J. A particle swarm optimization algorithm for hybrid flow-shop scheduling with multiprocessor tasks. International Journal of Production Research, 2008, 46(17): 4655-4670[14] Liu F, Zhang X P, Zou F X, Zeng L L. Immune clonal selection algorithm for hybrid flow-shop scheduling problem. In: Proceedings of the Chinese Control and Decision Conference. Guilin, China: IEEE, 2009. 2605-2609[15] Xu Y, Wang L, Zhou G, Wang S Y. An effective shuffled frog leaping algorithm for solving hybrid flow-shop scheduling problem. In: Proceedings of the International Conference on Intelligent Computing. Zhengzhou, China: Springer, 2011. 560-567[16] Muhlenbein H, Paass G. From recombination of genes to the estimation of distributions I. binary parameters. In: Proceedings of the 4th International Conference on Parallel Problem Solving from Nature. Berlin, Germany: Springer, 1996. 178-187[17] Baluja S. Population-Based Incremental Learning: a Method for Integrating Genetic Search Based Function Optimization and Competitive Learning, Technical Report CMU-CS-94-163, Computer Science Department, Carnegie Mellon University, USA, 1994[18] Zhou Shu-De, Sun Zeng-Qi. A survey on estimation of distribution algorithms. Acta Automatica Sinica, 2007, 33(2): 113-124(周树德, 孙增圻. 分布估计算法综述. 自动化学报, 2007, 33(2): 113-124)[19] Brah S A, Luan L L. Heuristics for scheduling in a flow shop with multiple processors. European Journal of Operational Research, 1999, 113(1): 113-122[20] Cui Jian-Shuang, Li Tie-Ke, Zhang Wen-Xin. Hybrid flowshop scheduling model and its genetic algorithm. Journal of University of Science and Technology Beijing, 2005, 27(5): 623-626(崔建双, 李铁克, 张文新. 混合流水车间调度模型及其遗传算法. 北京科技大学学报, 2005, 27(5): 623-626)[21] Montgomery D C. Design and Analysis of Experiments (Sixth Edition). Hoboken: John Wiley and Sons, 2005
点击查看大图
计量
- 文章访问数: 2376
- HTML全文浏览量: 64
- PDF下载量: 1963
- 被引次数: 0