基于区块进化算法求解置换流水车间调度问题

doi:10.16182/j.issn1004731x.joss.201808043

系统仿真学报 ›› 2018, Vol. 30 ›› Issue (8): 3170-3178.doi: 10.16182/j.issn1004731x.joss.201808043

基于区块进化算法求解置换流水车间调度问题

裴小兵, 赵衡

天津理工大学管理学院,天津 300384

收稿日期:2017-01-06 出版日期:2018-08-10 发布日期:2019-01-08
作者简介:裴小兵(1965-),男,内蒙古呼和浩特,蒙古族,博士,教授,研究方向为生产调度、系统仿真;赵衡(1992-),男,山东德州,硕士生,研究方向为系统仿真,智能算法。
基金资助:
天津市社科项目(TJYY17-013)

Block-based Evolutionary Algorithm for Permutation Flow-shop Scheduling Problem

Pei Xiaobing, Zhao Heng

College of Management, Tianjin University of Technology, Tianjin 300384, China

Received:2017-01-06 Online:2018-08-10 Published:2019-01-08

摘要/Abstract

摘要： 针对置换流水车间调度问题,提出了一种混合区块模型的全局进化算法。通过对优秀染色体的统计与采样构建位置矩阵概率模型,并依关联规则挖掘出具有优势信息的连续或不连续基因组成优势区块,结合优势区块与概率模型组合出高适应度的人造解;依劣势染色体构建突变概率模型,指导后期的基因突变操作。提出基于位置概率交换与NEH插入两种高效局部搜索方法,以进一步筛选优势解。通过对Reeves和Taillard标准测试集的仿真测试和算法比较验证了所提出算法出色的搜寻能力和有效性。

关键词: 置换流水车间调度, 组合区块, 概率模型, 人造解

Abstract: To solve the permutation flow-shop scheduling problem(PFSP), an effective new global evolutionary algorithm based on block model is developed. The probability model is built based on the information of job position through sample and statistic on the good chromosomes, and the association rule is applied to extract continuous or discontinuous blocks which contain job information respectively. The superiority blocks with position probability model for artificial chromosome combinations are integrated. The disadvantage gene is excavated according to the inferior chromosome and used for the later mutation operation. Two efficient local search methods called position model-based interchange and NEH-based insertion are proposed to further filter the dominant solution. Simulation results on Reeves and Taillard suites and comparisons with other well-known algorithms validate its excellent searching ability and efficiency of the proposed algorithm.

Key words: permutation flow-shop scheduling, combination blocks, probability model, artificial chromosome

中图分类号:

TP301

裴小兵, 赵衡. 基于区块进化算法求解置换流水车间调度问题[J]. 系统仿真学报, 2018, 30(8): 3170-3178.

Pei Xiaobing, Zhao Heng. Block-based Evolutionary Algorithm for Permutation Flow-shop Scheduling Problem[J]. Journal of System Simulation, 2018, 30(8): 3170-3178.

参考文献

[1] Garey M R, Graham R L, Johnson D S.Some NP- complete geometric problems[C]// Proceedings of the eighth annual ACM symposium on Theory of computing. ACM, 1976: 10-22.
[2] Chung C S, Flynn J, Kirca O.A branch and bound algorithm to minimize the total flow time for m-machine permutation flow shop problems[J]. International Journal of Production Economics (S0925-5273), 2002, 79(3): 185-196.
[3] Framinan J M, Gupta J N D, leisten R. A review and classification of heuristics for permutation flow-shop scheduling with makespan objective[J]. Journal of the Operational Research Society (S0160-5682), 2004, 55(12): 1243-1255.
[4] Lima C F, Pelikan M, Lobo F G, et al.Loopy sub-structural local search for the Bayesian optimization algorithm[C]// International Workshop on Engineering Stochastic Local Search Algorithms. Springer Berlin Heidel-berg, 2009: 61-75.
[5] Ceberio J, Irurozki E, Mendiburu A, et al.A review on estimation of distribution algorithms in permutation based combinatorial optimization problems[J]. Progress in Artificial Intelligence (S2192-6352), 2012, 1(1): 103-117.
[6] Liu H, Gao L, Pan Q.A hybrid particle swarm optimization with estimation of distribution algorithm for solving permutation flowshop scheduling problem[J]. Expert Systems with Applications (S0957-4174), 2011, 38(4): 4348-4360.
[7] Tzeng Y R, Chen C L, Chen C L.A hybrid EDA with ACS for solving permutation flow shop scheduling[J]. The International Journal of Advanced Manufacturing Technology (S0268-3768), 2012, 60(9/12): 1139-1147.
[8] Chang P C, Huang W H, Wu J L, et al.A block mining and re-combination enhanced genetic algorithm for the permutation flowshop scheduling problem[J]. International Journal of Production Economics (S0925-5273), 2013, 141(1): 45-55.
[9] Chang P C, Chen M H.A block based estimation of distribution algorithm using bivariate model for scheduling problems[J]. Soft Computing (S1432-7643), 2014, 18(6): 1177-1188.
[10] Ruiz R, Maroto C, Alcaraz J.Two new robust genetic algorithms for the flowshop scheduling problem[J]. Omega (S0305-0483), 2006, 34(5): 461-476.
[11] Hsu C Y, Chang P C, Chen M H.A linkage mining in block-based evolutionary algorithm for permutation flowshop scheduling problem[J]. Computers & Industrial Engineering (S0360-8352), 2015, 83(C): 159-171.
[12] Tizhoosh H R.Opposition-Based Learning: A New Scheme for Machine Intelligence[C]// CIMCA/ IAWTIC. 2005: 695-701.
[13] McNicholas P D, Murphy T B, O’Regan M. Standardising the lift of an association rule[J]. Computational Statistics & Data Analysis(S0167-9473), 2008, 52(10): 4712-4721.
[14] Nawaz M, Enscore E E, Ham I.A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem[J]. Omega(S0305-0483), 1983, 11(1): 91-95.
[15] 刘延风, 刘三阳. 基于混合电磁算法求解置换流水车间调度问题[J]. 系统仿真学报, 2012, 24(3): 603-607.
Liu Yanfeng, Liu Sanyang.Hybrid Eletro-magnetism- based Algorithm for Permutation Flow Shop Scheduling[J]. Journal of System Simulatiom, 2012, 24(3): 603-607.
[16] Chen Y M, Chen M C, Chang P C, et al.Extended artificial chromosomes genetic algorithm for permutation flowshop scheduling problems[J]. Computers & Industrial Engineering (S0360-8352), 2012, 62(2): 536-545.
[17] 张先超, 周泓. 变参数量子进化算法及其在求解置换流水车间调度问题中的应用[J]. 计算机集成制造系统, 2016, 22(3): 774-781.
Zhang Xianchao, Zhou Hong.Variable paramenters quantum-inspired evolutionary algorithm and its application in permutation flow-shop scheduling problem[J]. Computer Integrated Manu- facturing Systems, 2016, 22(3): 774-781.
[18] Lian Z, Gu X, Jiao B.A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan[J]. Applied Mathematics and Computation (S0096-3003), 2006, 175(1): 773-785.
[19] Chang P C, Huang W H, Ting C J.A hybrid genetic-immune algorithm with improved lifespan and elite antigen for flow-shop scheduling problems[J]. International Journal of Production Research (S0020-7543), 2011, 49(17): 5207-5230.

基于区块进化算法求解置换流水车间调度问题

Block-based Evolutionary Algorithm for Permutation Flow-shop Scheduling Problem

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价

[1]	张其文, 张斌. 基于教学优化算法求解置换流水车间调度问题[J]. 系统仿真学报, 2022, 34(5): 1054-1063.
[2]	张守刚, 吴龙成, 王艳, 纪志成. 基于分布估计算法的硫化车间调度[J]. 系统仿真学报, 2017, 29(9): 2182-2189.