结合混合进化算法和知识的多目标车间调度

doi:10.3969/j.issn.1004-132X.2020.24.012

摘要/Abstract

摘要： 提出了一种结合混合进化算法和知识的新型多目标车间调度方法，在有限的时间或迭代次数下可以得到更好的非支配Pareto解以服务于生产调度。由优化目标和属性归纳演绎法确定了知识挖掘的工件属性，通过优先级权重得到了规则初始种群。所提出的增减排序方法通过重新局部排序初始种群中工序的位置来克服优先级下工序不足或过饱和的问题。最后由一标准案例和非支配排序遗传算法-Ⅱ（NSGA-Ⅱ）混合模拟退火算法对所提调度方法进行了验证，得到的结果无论是优化目标值还是解集的分布在不同迭代次数和初始种群尺寸下都要优于传统随机进化方法。

关键词: 多目标车间调度, 知识挖掘, 初始种群, 进化算法

Abstract: A new multi-objective job shop scheduling method was proposed based on hybrid evolutionary algorithm and knowledge, the better non-dominant Pareto solutions might be obtained for production scheduling with limited time or iterations. The knowledge mining attributes were determined by the optimized objects and attribute-oriented induction and deduction method. Then, the rule-based initial population was acquired by the priority weight. The proposed addition-deletion sorting method overcame the problems of insufficient or oversaturated operations by re-assigning the positions in the initial population locally. Finally, a benchmark and non-dominated sorted genetic algorithm-Ⅱ (NSGA-Ⅱ) hybrid simulated annealing algorithm were used to verify the proposed scheduling method. The results obtained are superior to the traditional stochastic evolutionary method in terms of the optimized function values or the distribution of solution set under different iterations and initial population sizes.

Key words: multi-objective job shop scheduling, knowledge mining, initial population, evolutionary algorithm

中图分类号:

TP391.9

仇永涛1;吉卫喜1,2;张朝阳1,2. 结合混合进化算法和知识的多目标车间调度[J]. 中国机械工程, DOI: 10.3969/j.issn.1004-132X.2020.24.012.

QIU Yongtao1;JI Weixi1,2;ZHANG Chaoyang1,2. Multi-objective Job Shop Scheduling Based on Hybrid Evolutionary Algorithm and Knowledge[J]. China Mechanical Engineering, DOI: 10.3969/j.issn.1004-132X.2020.24.012.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.cmemo.org.cn/CN/10.3969/j.issn.1004-132X.2020.24.012

http://www.cmemo.org.cn/CN/Y2020/V31/I24/2979

参考文献

［1］张洁,汪俊亮,吕佑龙,等.大数据驱动的智能制造［J］.中国机械工程,2019,30(2):127-133.
ZHANG Jie, WANG Junliang, LYU Youlong, et al. Big Data on Intelligent Manufacturing［J］. China Mechanical Engineering， 2019, 30(2):127-133.
［2］林诗洁,董晨,陈明志,等.新型群智能优化算法综述［J］. 计算机工程与应用. 2018,54(12):1-9.
LIN Shijie, DONG Chen, CHEN Mingzhi, et al. Summary of New Group Intelligent Optimization Algorithm［J］. Computer Engineering and Applications， 2018, 54(12):1-9.
［3］HUANG Xiaobo, YANG Lixi. A Hybrid Genetic Algorithm for Multi-objective Flexible Job Shop Scheduling Problem Considering Transportation Time［J］. International Journal of Intelligent Computing and Cybernetics, 2019, 12(2):154-174.
［4］SOUIER M, DAHANE M, MALIKI F. An NSGA-Ⅱ-based Multiobjective Approach for Real-time Routing Selection in a Flexible Manufacturing System under Uncertainty and Reliability Constraints［J］. The International Journal of Advanced Manufacturing Technology, 2019, 100(9/12):2813-2829.
［5］ZHANG R, CHINONG R. Solving the Energy-efficient Job Shop Scheduling Problem:a Multi-objective Genetic Algorithm with Enhanced Local Search for Minimizing the Total Weighted Tardiness and Total Energy Consumption［J］. Journal of Cleaner Production, 2016, 112:3361-3375.
［6］SHEIKHALISHAHI M, ESKANDARI N, MAS-HAYEKHI A, et al. Multi-objective Open Shop Scheduling by Considering Human Error and Preventive Maintenance［J］. Applied Mathematical Modelling, 2019, 67:573-587.
［7］LU Chao, GAO Liang, PAN Quanke, et al. A Multi-objective Cellular Grey Wolf Optimizer for Hybrid Flowshop Scheduling Problem Considering Noise Pollution［J］. Applied Soft Computing, 2019, 75:728-749.
［8］QIN Hongbin, FAN Pengfei, TANG Hongtao, et al. An Effective Hybrid Discrete Grey Wolf Optimizer for the Casting Production Scheduling Problem with Multi-objective and Multi-constraint［J］. Computers & Industrial Engineering, 2019, 128:458-476.
［9］ZHOU Yong, YANG Jianjun, ZHENG Lianyu. Multi-agent Based Hyper-heuristics for Multi-objective Flexible Job Shop Scheduling:a Case Study in an Aero-engine Blade Manufacturing Plant［J］. IEEE Access, 2019, 7:21147-21176.
［10］FU Yaping, WANG Hongfeng, HUANG Min. Integrated Scheduling for a Distributed Manufacturing System:a Stochastic Multi-objective Model［J］. Enterprise Information Systems, 2019, 13(4):557-573.
［11］LI X N, OLAFSSON S. Discovering Dispatching Rules Using Data Mining［J］. Journal of Scheduling, 2005, 8(6):515-527.
［12］JUN S, LEE S, CHUN H. Learning Dispatching Rules Using Random Forest in Flexible Job Shop Scheduling Problems［J］. International Journal of Production Research, 2019, 57(10):3290-3310.
［13］KUMAR S, RAO C S P. Application of Ant Colony, Genetic Algorithm and Data Mining-based Techniques for Scheduling［J］. Robotics and Computer-Integrated Manufacturing, 2009, 25(6):901-908.
［14］NASIRI M M, SALESI S, RAHBARI A, et al. A Data Mining Approach for Population-based Methods to Solve the JSSP［J］. Soft Computing, 2019, 23(21):11107-11122.
［15］CAI Yandong. Attribute-oriented Induction in Relational Databases, Knowledge Discovery in Databases［D］. Burnaby：Simon Fraser University, 1989.
［16］KOONCE D A, TSAI S C. Using Data Mining to Find Patterns in Genetic Algorithm Solutions to a Job Shop Schedule［J］. Computers & Industrial Engineering, 2000, 38(3):361-374.
［17］LAWRENCE S. An Experimental Investigation of Heuristic Scheduling Techniques［D］. Pittsburgh:Carnegie-Mellon University, 1984.
［18］DEB K, PRATAP A, AGARWAL S, et al. A Fast and Elitist Multiobjective Genetic Algorithm:NSGA-Ⅱ［J］. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197.
［19］KIRKPATRICK S, GELATT C D, VECCHI M P. Optimization by Simulated Annealing［J］. Science, 1983, 4598(220):671-680.
［20］ARROYO J E C, LEUNG J Y T. An Effective Iterated Greedy Algorithm for Scheduling Unrelated Parallel Batch Machines with Non-identical Capacities and Unequal Ready Times［J］. Computers & Industrial Engineering, 2017, 105:84-100.
［21］ZITZLER E, THIELE L. Multiobjective Evolutionary Algorithms:a Comparative Case Study and the Strength Pareto Approach［J］. IEEE Transactions on Evolutionary Computation, 1999, 3(4):257-271.
［22］SCHOTT J R. Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization［D］. Boston：Massachusetts Institute of Technology, 1995.
［23］COBOS C, ERAZO C, LUNA J, et al. Multi-objective Memetic Algorithm Based on NSGA-Ⅱ and Simulated Annealing for Calibrating CORSIM Micro-simulation Models of Vehicular Traffic Flow［C］∥ Conference of the Spanish Association for Artificial Intelligence.Cham:Springer, 2016:468-476.

[1]	魏书鹏, 唐红涛, 李西兴, 杨冠宇, 张健. 考虑双资源约束的柔性机械加工车间逆调度问题研究[J]. 中国机械工程, 2024, 35(03): 457-471.
[2]	谢法吾, 李玲玲, 李丽, 黄洋鹏. 基于多目标混合进化算法的作业车间混排可变分批节能调度方法[J]. 中国机械工程, 2023, 34(13): 1576-1588,1598.
[3]	刘尧, 陈改革, 刘振国, 孔宪光, 常建涛. 关联规则挖掘驱动的盾构机刀盘健康评估方法[J]. 中国机械工程, 2023, 34(11): 1326-1334,1342.
[4]	连永伟, 董钊睿, 刘琼. 跨单元调度及其车辆路径集成优化[J]. 中国机械工程, 2022, 33(06): 747-755.
[5]	吕天一, 肖守讷, 朱涛, 张敬科, 王小瑞, 李玉如, 阳光武, 杨冰. 采用多目标进化算法的列车碰撞能量配置方案优化[J]. 中国机械工程, 2021, 32(18): 2262-2267.
[6]	林文广, 赖荣燊, 肖人彬. 基于语义关联的专利有害性能知识挖掘研究[J]. 中国机械工程, 2021, 32(16): 1952-1962.
[7]	张源, 陶翼飞, 王加冕. 改进差分进化算法求解混合流水车间调度问题[J]. 中国机械工程, 2021, 32(06): 714-720.
[8]	刘元铭, 王振华, 王涛, 刘文礼, 熊晓燕. [成形质量的闭环与自适应控制技术]热轧带钢出口凸度数据驱动建模及智能化预测分析[J]. 中国机械工程, 2020, 31(22): 2728-2733.
[9]	徐亚旋;刘梁;常思勤;胡茂杨. 电磁驱动配气机构的发动机分缸工作一致性控制[J]. 中国机械工程, 2019, 30(21): 2546-2553.
[10]	金棋, 王友仁, 王俊. [设备健康管理]基于深度学习多样性特征提取与信息融合的行星齿轮箱故障诊断方法[J]. 中国机械工程, 2019, 30(02): 196-204.
[11]	杨宇;黄敏;王震宇;朱启兵. 利用有限制稳定配对策略求解双目标柔性作业车间调度问题[J]. 中国机械工程, 2018, 29(14): 1743-1750.
[12]	孙浩, 肖宏, 胡庆军. 基于有约束多目标进化算法的冷轧负荷分配分析[J]. 中国机械工程, 2017, 28(01): 93-100.
[13]	符纯明, 姜, 潮, 陈光宋, 吉磊. 基于隔代映射算子的差分进化算法[J]. 中国机械工程, 2016, 27(11): 1523-1529,1545.
[14]	白国振, 周海宁. 蜗轮减速器振动信号特征提取与状态识别[J]. 中国机械工程, 2016, 27(03): 349-354.
[15]	赵艺兵, 温秀兰, 许有熊. 基于坐标测量机和拟粒子群进化算法的圆柱度误差检测与评定[J]. 中国机械工程, 2015, 26(18): 2432-2436.