计算机科学 ›› 2020, Vol. 47 ›› Issue (12): 239-244.doi: 10.11896/jsjkx.191100042
董海1, 徐晓鹏2, 谢谢3
DONG Hail1, XU Xiao- peng2, XIE Xie3
摘要: 针对车间调度中存在的机器柔性、工人柔性和并行工序柔性文中用优先级间的加工顺序替代单独工件间的顺序约束来表示并行工序柔性建立了以最小化最大完成时间、总耗能和平均完成时间为目标的多柔性作业车间调度模型设计了一种四染色体编码方法及对应的交叉和变异算子并用两条染色体来编码加工顺序.结合入侵肿瘤生长优化算法的算法结构和NSGAIII算法中对解的筛选机制提出一种多目标优化算法求解模型.该算法使用快速非支配排序方法和基于特征点的选择方法对细胞进行分类和转化设计替代重复细胞的机制并基于交叉和变异算子重新设计了细胞的生长和入侵机制.最后求解数值实例用超体积、延展度和分布度对比所提算法和其他多种智能算法得到的解集结果证明所提算法收敛更快且所得解集分布更均匀.
中图分类号:
[1] JOHNSON S.Optimal Two-and-Three Stage Production Sche-dules With Setup Times Included[J].Naval Research Logistics Quarterly,1954,1(1):61-68. [2] BRUCKER P,SCHLIE R.Job-Shop Scheduling with Multi-Purpose Machines[J].Computing,1991,45(4):369-375. [3] ZHONGY J,YANG H C,MO R,et al.Optimization Method of Flexible Job-Shop Scheduling Problem Based on Niching and Particle Swarm Optimization Algorithms[J].Computer Integrated Manufacturing Systems,2015,21(12):3231-3238. [4] ZHAO B X,GAO J M,CHEN K.Two-Stage Hybrid Pareto Ant Colony Algorithm for Multi-Objective Flexible Job ShopSche-duling[J].Journal of Xi'an Jiaotong University,2016,50(7):145-151. [5] ZHANG Z Q,WANG K P,ZHU L X,et al.Pareto Hybrid Ant Colony and Genetic Algorithm for Multi-Objective U-Shaped Disassembly Line Balancing Problem[J].Journal of Xi'an Jiaotong University,2018,53(3):628-637. [6] GONG G L,DENG Q W,GONG X R,et al.A New DoubleFlexible Job-Shop Scheduling Problem Integrating Processing Time,Green Production,and Human Factor Indicators[J].Journal of Cleaner Production,2018,174(10):560-576. [7] CAO L,YE C M,HUANG X.Multi-Objective Flexible Job-Shop Scheduling Based on Learning Effect[J].Computer Integrated Manufacturing Systems,2018,24(8):2023-2034. [8] HUANG X W,MA X L,CAO D M.Improved Generic Algorithm for Job-Shop Scheduling Problem with Process Sequence Flexibility[J].Operations Research and Management Science,2013,22(1):65-70. [9] HUANG X W,ZHAO X W,YU W Q,et al.Description and Measurement of Key Flexibility in Jobshop Manufacturing System[J].CIMS,2015,21(12):3153-3165. [10] HUANG X W,SUN N,SUN R.Operation Sequence Flexibility Description Model[J].CIMS,2016,22(10):2275-2283. [11] CUI Q,WU X L,YU J J.Improved Genetic Algorithm Variable Neighborhood Search for Solving Hybrid Flow Shop Scheduling Problem[J].CIMS,2017,23(9):1917-1927. [12] TANG D,DONG S,JIANG Y,et al.ITGO:Invasive TumorGrowth Optimization Algorithm[J].Applied Soft Computing 2015,36 (Supplement C):670-698. [13] TANG D,DONG S,HE I,et al.Intrusive Tumor Optimization Algorithm for Data Clustering Growth[J].Neural Computing and Applications,2016,27(2):349-374. [14] ZHOU J,DONG S B,TANG D Y.Task Scheduling Algorithm in Cloud Computing Based on Invasive Tumor Growth Optimization[J].Chinese Journal of Computers,2018,41(6):1140-1155. [15] DEB K,PRATAP A,AGARWAL S,et al.A Fast and Elitist Multiobjective Genetic Algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197. [16] DEB K,JAIN H.An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach,Part I:Solving Problems with Box Constraints[J].IEEE Transactions on Evolutionary Computation,2013,18(4):577-601. [17] JAIN H,DEB K.An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point Based Nondominated Sorting Approach,Part II:Handling Constraints And Extending to an Adaptive Approach[J].IEEE Transactions on Evolutionary Computation,2013,18(4):602-622. [18] ZITZLER E.Evolutionary Algorithms Multiobjective Optimization:Methods and Applications[D].Zurich:Swiss Federal Institute of Technology ,1999. [19] SCHOOT J R.Fault Tolerant Design Using Single and Multicriteria Genetic Algorithms Optimization[D].Cambridge:Massachusetts Institute of Technology ,1995. [20] ZITZLER E,DEB K,THIELE L.Comparison of Multiobjective Evolutionary Algorithms:Empirical Results[J].Evolutionary Computation,2008,8(2):173-195. [21] ZHANG Q,LI H.MOEA/D:A Multiobjective Evolutionary Algorithm Based on Decomposition[J].IEEE Transactions onevo-lutionary computation,2007,11(6):712-731. [22] SHAO X,LIU W,LIU Q,et al.Hybrid Discrete Particle Swarm Optimization for Multi-Objective Flexible Job-Shop Scheduling Problem[J].The International Journal of Advanced Manufacturing Technology ,2013,67(9-12):2885-2901. [23] ZITHER E,LAUMANNS M,THIELE L.SPEA2:Improvingthe Strength Pareto Evolutionary Algorithm[C]//Proc.of Int.Conf.on Evolutionary Method for Design,Optimization and Control with Applications to Industrial Problems.Berlin:Springer,2002:95-100. |
[1] | 左益,公茂果,曾久琳,焦李成. 混合多目标算法用于柔性作业车间调度问题 Hybrid Multi-objective Algorithm for Solving Flexible Job Shop Scheduling Problem 计算机科学, 2015, 42(9): 220-225. https://doi.org/10.11896/j.issn.1002-137X.2015.09.042 |
|