计算机科学 ›› 2020, Vol. 47 ›› Issue (12): 239-244.doi: 10.11896/jsjkx.191100042

• 人工智能 • 上一篇    下一篇

多目标优化算法求解多柔性作业车间调度问题

董海1, 徐晓鹏2, 谢谢3   

  1. 1 沈阳大学应用技术学院 沈阳 110044
    2 沈阳大学机械工程学院 沈阳 110044
    3 沈阳大学信息工程学院 沈阳 110044
  • 收稿日期:2019-11-06 修回日期:2020-01-27 发布日期:2020-12-17
  • 通讯作者: 徐晓鹏( xpinworld@ sina.cn)
  • 作者简介:13898802977@163.com
  • 基金资助:
    国家自然科学基金(71672117)

Solving Multi-flexible Job-shop Scheduling by Multi-objective Algorithm

DONG Hail1, XU Xiao- peng2, XIE Xie3   

  1. 1 School of Applied Technology Shenyang University Shenyang 110044,China
    2 School of Mechanical Engineering Shenyang University Shenyang 110044,China
    3 School of Information Engineering Shenyang University Shenyang 110044,China
  • Received:2019-11-06 Revised:2020-01-27 Published:2020-12-17
  • About author:DONG Hai,born in 1971 Ph.D professor.His main research interests include the modeling optimization and control of ad-vanced production system the process op-timization of manufacturing enterprise lo-gistics and supply chain.management.
    XU Xiao-peng ,born in 1991postgraduate.His main research interests include the moc deling optimization and control of ad-vanced production system application and improvement of intelligent algorithms and the application of machine learning.

摘要: 针对车间调度中存在的机器柔性、工人柔性和并行工序柔性文中用优先级间的加工顺序替代单独工件间的顺序约束来表示并行工序柔性建立了以最小化最大完成时间、总耗能和平均完成时间为目标的多柔性作业车间调度模型设计了一种四染色体编码方法及对应的交叉和变异算子并用两条染色体来编码加工顺序.结合入侵肿瘤生长优化算法的算法结构和NSGAIII算法中对解的筛选机制提出一种多目标优化算法求解模型.该算法使用快速非支配排序方法和基于特征点的选择方法对细胞进行分类和转化设计替代重复细胞的机制并基于交叉和变异算子重新设计了细胞的生长和入侵机制.最后求解数值实例用超体积、延展度和分布度对比所提算法和其他多种智能算法得到的解集结果证明所提算法收敛更快且所得解集分布更均匀.

关键词: NSGAIlI, 并行工序柔性, 工人柔性, 入侵肿瘤生长优化算法, 作业车间调度问题

Abstract: In view of machine flexibilityworker flexibility and parallel operation flexibility in the job- shop schedulingthis paper denotes the parallel operation flexibility by replacing sequence constraints between individual operations with sequence constraints between prioritiesand proposes a multi-flexible job- shop scheduling model with objectives of minimizing the maximum comple-tion timetotal energy consumption and average completion time.A four -chromosome coding method and corresponding crossover and mutation operators are designedin which two chromosomes are used to encode the processing sequence.A multi- objective optimization algorithm is proposedbased on the combination of the structure of the invasive tumor growth optimization and the screening mechanism of NSGAI.The algorithm uses a fast non- dominant sorting method and a feature- based selection method to classify and transform cells.A mechanism is designed to replace duplicate cells.Finallythe proposed algorithm is compared with several intelligent algorithms in calculation examples by hypervolumedistribution and extensibilitywhich prove its effectiveness and feasibility.

Key words: Invasive tumor growth optimization al-gorithm, Parallel operation flexibility, Worker flexibility, Job- shop scheduling problem, NSGAIlI

中图分类号: 

  • TH165
[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
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!