基于混合教学优化算法的多车间协作综合调度

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

摘要/Abstract

摘要： 目前在处理加工属性类似的多车间协作综合调度问题时，几乎都是采用调度规则，对产品加工工艺结构的依赖度过高，降低了算法对同一类问题不同实例的适应性，并且对大型实例的求解结果普遍欠佳，为此提出了一种混合教学优化算法。该算法在基本教学优化算法的基础上加入采用变异操作模拟的自学习阶段，提高其局部搜索能力，并且在教学、互学和自学三个阶段均按照模拟退火算法中Metropolis准则计算的概率，随机接受学生群体中某一个较差个体作为新个体，进一步提高算法跳出局部最优解的能力；教学、互学和自学三个阶段设计的变换操作均考虑综合调度问题中各虚拟工序之间的顺序约束关系，保证生成的解均是可行解。通过测试以往该类问题实例，得到的结果验证了所提算法的可行性和有效性。

关键词: 多车间协作, 综合调度, 教学优化算法, 自学习, Metropolis准则

Abstract: Aiming at the current integrated scheduling problems of multi-workshop collaborations with similar processing properties, where almost using the scheduling rules, relying too heavily on the processing structures of the products, reducing the algorithm adaptability to different instances on the same type of problems, and the poor results of solving large instances, a hybrid teaching-learning-based optimization algorithm was proposed. A self-learning phase was added, the mutation operators were executed in the individual self-learning phase to improve the local search ability. In the three phases of teaching, mutual-learning and self-learning, the probability calculated by the Metropolis procedure in the simulated annealing algorithm was adopted to accept randomly a bad individual as a new one, further improving the ability of running away from local optima. The transformation operations designed in the three phases taken into account the sequential constraint relations among the virtual processes in the integrated scheduling problems and ensure that the solutions generated were all feasible solutions. The feasibility and validity of the proposed algorithm were verified by testing the previous examples.

Key words: multi-workshop collaboration, integrated scheduling, teaching-learning-based optimization algorithm, self-learning, Metropolis procedure

中图分类号:

TH186

廖不凡1;雷琦1;吴文烈2;宋豫川1;郭伟飞1. 基于混合教学优化算法的多车间协作综合调度[J]. 中国机械工程, DOI: 10.3969/j.issn.1004-132X.2020.16.006.

LIAO Bufan1;LEI Qi1;WU Wenlie2;SONG Yuchuan1;GUO Weifei1. Hybrid Teaching-learning-based Optimization Algorithms for Integrated Scheduling of Multi-workshop Collaborations[J]. China Mechanical Engineering, DOI: 10.3969/j.issn.1004-132X.2020.16.006.

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

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

http://www.cmemo.org.cn/CN/Y2020/V31/I16/1940

参考文献

[1]钟祾充，钱斌，胡蓉，等. 混合布谷鸟算法求解绿色流水车间调度问题[J]. 中国机械工程, 2018, 29(22)：2674-2681.
ZHONG Lingchong, QIAN Bin, HU Rong, et al. HCS Algorithm for Multi-objective Flow Shop Scheduling Problems with Energy Consumption[J] China Mechanical Engineering, 2018, 29(22)：2674-2681.
[2]朱传军，邱文，张超勇，等. 多目标柔性作业车间稳健性动态调度研究[J]. 中国机械工程, 2017, 28(2)：173-182.
ZHU Chuanjun, QIU Wen, ZHANG Chaoyong, et al. Multi-objective Flexible Job Shop Dynamic Scheduling Strategy Aiming at Scheduling Stability and Robustness[J]. China Mechanical Engineering, 2017, 28(2)：173-182.
[3]谢志强. 工件间有约束的复杂产品工序调度研究[D].哈尔滨：哈尔滨理工大学,2009.
XIE Zhiqiang. Study on Operation Scheduling of Complex Product with Constraint among Jobs[D]. Harbin：Harbin University of Science and Technology, 2009.
[4]谢志强，桂忠艳，杨静. 基于设备驱动和实质路径的动态并行综合柔性调度算法[J]. 机械工程学报, 2014, 50(18)：203-212.
XIE Zhiqiang, GUI Zhongyan, YANG Jing. Dynamic Parallel Integrated Flexible Scheduling Algorithm Based on Device Driver and Essential Path[J]. Journal of Mechanical Engineering, 2014, 50(18)：203-212.
[5]于晓义，孙树栋，褚崴. 基于并行协同进化遗传算法的多协作车间计划调度[J]. 计算机集成制造系统, 2008,14(5)：991-1000.
YU Xiaoyi, SUN Shudong, CHU Wei, et al. Parallel Collaborative Evolutionary Genetic Algorithm for Multi-workshop Planning and Scheduling Problems [J]. Computer Integrated Manufacturing Systems, 2008,14(5)：991-1000.
[6]谢志强，郭禾，苏文秀，等. 存在多工序同时结束的多车间逆序综合调度算法[J]. 吉林大学学报(工学版), 2018, 48(2)：578-587.
XIE Zhiqiang, GUO He, SU Wenxiu, et al. Reversal Sequence Integrated Scheduling Algorithm of Multiple Workshop with Multi-procedures Ended Together[J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(2)：578-587.
[7]谢志强，于洁，陈德运，等. 基于邻域渲染的二车间综合调度算法[J]. 机械工程学报, 2016, 52(1)：149-159.
XIE Zhiqiang, YU Jie, CHEN Deyun, et al. Integrated Scheduling Algorithm of Two Workshops Based on the Principle of the Neighborhood Rendering[J]. Journal of Mechanical Engineering, 2016, 52(1)：149-159.
[8]张晓欢，谢志强，辛宇，等. 基于择时的二车间综合调度算法[J]. 计算机集成制造系统, 2017, 23(9)：1938-1949.
ZHANG Xiaohuan, XIE Zhiqiang, XIN Yu, et al. Integrated Scheduling Algorithm of Two Workshops Based on Optimal Time[J] Computer Integrated Manufacturing Systems, 2017, 23(9)：1938-1949.
[9]RAO R V, SAVSANI V J, VAKHARIA D P. Teaching-learning-based Optimization：a Novel Method for Constrained Mechanical Design Optimization Problems[J]. Computer-Aided Design, 2011, 43(3)：303-315.
[10]LIN W W, YU D Y, ZHANG C Y, et al. A Multi-objective Teaching-learning-based Optimization Algorithm to Scheduling in Turning Processes for Minimizing Makespan and Carbon Footprint[J]. Journal of Cleaner Production， 2015, 101：337-347.
[11]DOKEROGLU T. Hybrid Teaching-learning-based Optimization Algorithms for the Quadratic Assignment Problem[J]. Computers & Industrial Engineering， 2015, 85：86-101.
[12]李瑞国，张宏立，范文慧，等. 基于改进教学优化算法的Hermite正交基神经网络混沌时间序列预测[J]. 物理学报, 2015, 64(20)：108-120.
LI Ruiguo, ZHANG Hongli, FAN Wenhui, et al. Hermite Orthogonal Basis Neural Network Based on Improved Teaching-learning-based Optimization Algorithm for Chaotic Time Series Prediction[J]Acta Physica Sinica, 2015, 64(20)：108-120.
[13]潘全科，王文宏，朱剑英. 一类解决Job Shop问题的改进遗传算法[J]. 中国机械工程, 2006,17(8)：866-869.
PAN Quanke, WANG Wenhong, ZHU Jianying. An Enhanced Genetic Algorithm for Job Shop Scheduling[J]. China Mechanical Engineering, 2006,17(8)：866-869.
[14]杨婷婷,吕海利,董明望,等. 一种装配产品调度问题的粒子群算法实现[J]. 武汉理工大学学报,2015,37(11):93-100.
YANG Tingting, LYU Haili, DONG Mingwang, et al. Realization of Assembly Job Shop Scheduling Problem with Particle Swarm Optimization Algorithm[J]. Journal of Wuhan University of Technology, 2015, 37(11)：93-100.

[15]吴秀丽，孙树栋，杨展，等. 多目标柔性Job Shop调度问题的技术现状和发展趋势[J]. 计算机应用研究, 2007, 24(3)：1-5.
WU Xiuli, SUN Shudong, YANG Zhan, et al. Survey on Multi-objective Flexible Job-shop Scheduling Problem[J]. Application Research of Computers, 2007, 24(3)：1-5.
[16]赵诗奎，韩青，王桂从. 基于虚拟零部件级别分区编码的产品综合调度算法[J]. 计算机集成制造系统, 2015, 20(9)：2435-2445.
ZHAO Shikui, HAN Qing, WANG Guicong. Product Comprehensive Scheduling Algorithm Based on Virtual Component Level Division Coding[J]. Computer Integrated Manufacturing Systems, 2015, 20(9)：2435-2445.
[17]谢志强，刘长海，杨静. 考虑后续工序且批处理工序数为2的批综合调度算法[J]. 上海交通大学学报, 2012, 46(11)：1746-1752.
XIE Zhiqiang, LIU Changhai, YANG Jing. Batch Integrated Scheduling Algorithm Considering Posterior Operations and with Constraint of 2 Operations Batches Processing[J]. Journal of Shanghai Jiao Tong University, 2012, 46(11)：1746-1752.

[18]PERL M. STEINER M. 3-D Stress Intensity Factors due to Full Autofrettage for Inner Radial or Coplanar Crack Arrays and Ring Cracks in a Spherical PressureVessel[J]. Engineering Fracture Mechanics, 2015, 138：233-249.
[19]REN Y P, ZHANG C Y, ZHAO F, et al. An Asynchronous Parallel Disassembly Planning Based on Genetic Algorithm[J]. European Journal of Operational Research, 2018, 269(2)：647-660.
[20]谢志强，郑付萍，朱天浩，等. 两车间可调度工序均衡处理的综合调度算法[J]. 计算机工程, 2014, 40(1)：295-300.
XIE Zhiqiang, ZHENG Fuping, ZHU Tianhao, et al. Integrated Scheduling Algorithm with Equalization Processing of Schedulable Processes in Two Workshops[J]. Computer Engineering, 2014, 40(1)：295-300.
[21]谢志强，周含笑，桂忠艳，等. 基于拟关键路径的二车间综合调度算法[J]. 计算机科学, 2013, 40(4)：193-198.
XIE Zhiqiang, ZHOU Hanxiao, GUI Zhongyan, et al. Integrated Scheduling Algorithm of Two Workshop Based on ACPM[J]. Computer Science, 2013, 40(4)：193-198.