周期式退火炉作批处理机的可重入批离散机流水车间调度

doi:10.3901/JME.2020.02.220

摘要/Abstract

摘要： 针对无缝钢管冷拔生产中的周期式退火炉作批处理机的可重入批离散机流水车间调度问题，建立以总工件完工时间与批处理机总能源消耗最小化的双目标优化调度模型，设计包括多目标粒子群算法、快速非支配等级排序、拥挤度比较以及变异进化操作的多目标粒子群算法，该算法采用非支配等级排序与拥挤度比较进行最优粒子的选择策略和算法前期与后期变异相结合使用策略。试验结果表明，与带变异进化操作的多目标粒子群算法和非支配排序粒子群算法相比，该算法在两个目标函数上都找到更优的最小值，其结果平均水平更靠近Pareto解集的前沿，有效提高了算法的优化求解能力。通过Pareto解的方式该算法可得到一组综合权衡了完工时间和退火炉能源消耗两个指标的Pareto解集，能提供多种可选的调度方案，当生产时间充足，可尽量选取退火炉能源消耗较低的方案，当企业订单繁多追求生产效率时，可尽量选取完工时间较小的方案，有效地解决了此类实际问题。

关键词: 无缝钢管, 冷拔, 生产计划, 可重入生产, 周期式退火炉, Pareto

Abstract: Aiming at the flow shop scheduling problem of reentrant batch discrete machines with periodic annealing furnace as batch processor in seamless steel tube cold drawing production, a bi-objective optimal scheduling model is established, which minimizes the total work completion time and the total energy consumption of batch machines. A multi-objective particle swarm optimization algorithm, fast non-dominant ranking, congestion comparison and particle mutation operation algorithm are designed. In this algorithm, non-dominant ranking and congestion comparison are used to select the optimal particle and the combination of early and late mutation is used. The experimental results show that, compared with the Variation-Multi-Objective Particle Swarm Optimization algorithms and Non-Dominated Sorting Particle Swarm Optimization algorithms, the algorithm finds a better minimum on both objective functions, and the average level of the results is closer to the front of Pareto solution set, which effectively improves the optimization ability of the algorithm. Through Pareto solution, the algorithm can get a set of Pareto solution which comprehensively weighs the completion time and energy consumption of annealing furnace. It can provide a variety of alternative scheduling schemes. When the production time is sufficient, the scheme with lower energy consumption of annealing furnace can be selected as far as possible. When the enterprise has many orders to pursue production efficiency, the scheme with smaller completion time can be selected as far as possible to effectively solve the problem. Such practical problems have been solved.

Key words: seamless steel tube, cold-drawing, production scheduling, re-entrant lines, periodic annealing furnace, Pareto

中图分类号:

TG156

顾涛, 李苏建, 林莹璐, 吴秀丽. 周期式退火炉作批处理机的可重入批离散机流水车间调度[J]. 机械工程学报, 2020, 56(2): 220-232.

GU Tao, LI Sujian, LIN Yinglu, WU Xiuli. Research on the Re-entrant Batch Discrete Flow Shop Scheduling for Periodic Annealing Furnace as Batch Processor[J]. Journal of Mechanical Engineering, 2020, 56(2): 220-232.

参考文献

[1] GRAVES S C,MEAL H C,STEFEK D,et al. Scheduling of re-entrant flow shops[J]. Journal of Operations Management,1983,3(4):197-207.
[2] HEKMATFAR M,GHOMI S M T F,KARIMI B. Two stage reentrant hybrid flow shop with setup times and the criterion of minimizing makespan[J]. Applied Soft Computing Journal,2011,11(8):4530-4539.
[3] WATANAKICH P. Scheduling for a two-stage hybrid flow shop with machine setup time[M]. Bangkok:Kasetsart University,2001.
[4] CHOI H S,KIM H W,LEE D H,et al. Scheduling algorithms for two-stage reentrant hybrid flow shops:minimizing makespan under the maximum allowable due dates[J]. International Journal of Advanced Manufacturing Technology,2009,42(9-10):963.
[5] DUGARDIN F,AMODEO L,YALAOUI F. Multiobjective scheduling of a reentrant hybrid flowshop[C]//International Conference on Computers & Industrial Engineering,July 6-9,2009,Troyes,France. Troyes:IEEE,2009:193-195.
[6] DUGARDIN F,YALAOUI F,AMODEO L. New multi-objective method to solve reentrant hybrid flow shop scheduling problem[J]. European Journal of Operational Research,2010,203(1):22-31.
[7] 周炳海,钟臻怡. 可重入混合流水车间调度的拉格朗日松弛算法[J]. 控制理论与应用,2015,32(7):881-886. ZHOU Binghai,ZHONG Zhenyi. Lagrangian relaxation algorithm for scheduling problems of reentrant hybrid flow shops[J]. Control Theory & Applications,2015,32(7):881-886.
[8] CHALARDKID N,SOMBOONWIWAT T,KHOMPATRAPORN C. Optimal scheduling of two-stage reentrant hybrid flow shop for heat treatment process[C]//30th European Conference On Modelling And Simulation,May 31st-June 3rd,2016,Regensburg,Germany. Berlin:ECMS,2016,515-519.
[9] KIM Y D. Minimizing total tardiness of orders with reentrant lots in a hybrid flow shop[J]. International Journal of Production Research,2005,43(11):2149-2167.
[10] JIANG S,TANG L. Lagrangian relaxation algorithms for re-entrant hybrid flowshop scheduling[C]//International Conference on Information Management,Innovation Management and Industrial Engineering,December 19-21,2020,Taipei,China. New York:ICIII,2008,78-81.
[11] CHO H M,BAE S J,KIM J,et al. Bi-objective scheduling for reentrant hybrid flow shop using Pareto genetic algorithm[J]. Computers & Industrial Engineering,2011,61(3):529-541.
[12] ZHOU B H,HU L M,ZHONG Z Y. A hybrid differential evolution algorithm with estimation of distribution algorithm for reentrant hybrid flow shop scheduling problem[J]. Neural Computing & Applications,2016,30(8):1-17.
[13] IKURA Y,GIMPLE M. Scheduling algorithms for a single batch processing machine[J]. Operation Research Letters,1986,5(1):61-65.
[14] BRUCKER P,GLADKY A,HAN H,et al. Scheduling A Batching Machine[J]. Journal of Scheduling,1998,1(1):31-54.
[15] 轩华. 含串行批处理机的三阶段混合流水车间调度问题[J]. 计算机集成制造系统,2012,18(5):1006-1010. XUAN Hua. Three-stage HFS scheduling problem with serial batching machines[J]. Computer Integrated Manufacturing Systems,2012,18(5):1006-1010.
[16] 赵玉芳,唐立新. 极小化最大完工时间的单机连续型批调度问题[J]. 自动化学报,2006,32(5):730-737. ZHAO Yufang,TANG Lixin. Scheduling a single continuous batch processing machine to minimize makespan[J]. Acta Automatica Sinica,2006,32(5):730-737.
[17] VELDHUIZEN D A V,LAMONT G B. Multiobjective evolutionary algorithms:Analyzing the state-of-the-art[J]. Evolutionary Computation,2014,8(2):125-147.
[18] SIERRA M R,COELLO C A C. Improving PSO-based multi-objective optimization using crowding,mutation and ∈-dominance[J]. Lecture Notes in Computer Science,2005,3410:505-519.
[19] 陈民铀,张聪誉,罗辞勇. 自适应进化多目标粒子群优化算法[J]. 控制与决策,2009,24(12):1851-1855. CHEN Minyou,ZHANG Congyu,LUO Ciyong. Adaptive evolutionary multi-objective particle swarm optimization algorithm[J]. Control and Decision,2009,24(12):1851-1855.
[20] 周严伟. 基于快速非支配排序遗传算法的多目标流水车间调度研究[D]. 广州:华南理工大学,2015. ZHOU Yanwei. Research of mult-objective flow scheduling based on fast non-dominated sorting genetic algorithm[D]. Guangzhou:South China University of Technology,2015.
[21] 陈晓慧,张启忠,易树平,等. 基于遗传算法的可重入钢管生产优化调度[J]. 北京科技大学学报,2009,31(8):1067-1071. CHEN Xiaohui,ZHANG Qizhong,YI Shuping,et al. Optimal scheduling of steel tube re-entrant lines based on a genetic algorithm[J] Journal of University of Science and Technology Beijing,2009,31(8):1067-1071.