加工时间不确定的炼钢-连铸区间多目标优化调度

doi:10.16381/j.cnki.issn1003-207x.2021.2590

摘要/Abstract

摘要：

加工时间不确定是炼钢-连铸生产中普遍存在且具有代表性的一类不确定因素。针对其调度问题，采用三参数区间数描述加工时间不确定性信息，建立了以炉次总等待时间和浇次开浇时间提前/拖期总惩罚最小化为优化目标的区间多目标混合整数规划模型，并结合问题特征，设计了一种基于分类进化策略的改进快速非支配排序区间多目标遗传算法。在算法中，融合区间数相关操作提出了区间意义下的逆序并行倒推解码法和基于机器选择规则的种群初始化混合策略，设计了基于个体拥挤距离的交叉变异算子分类进化策略，并提出对种群中重复个体执行再变异操作，以维持种群多样性。基于实际生产数据的仿真实验验证了区间多目标优化算法在求解质量和求解效率方面的有效性。

关键词: 炼钢-连铸, 生产调度, 加工时间不确定, 区间多目标优化, 遗传算法

Abstract:

Due to the complex physical changes and chemical reactions in the process of the steelmaking-continuous casting （SCC）， the uncertainty of processing time is a common and representative uncertainty factor. Therefore， it is necessary to consider the uncertain processing time before scheduling， to enhance the robustness of schedules and reduce the repair frequency of dynamic scheduling.For SCC scheduling problem with processing time uncertainty， the processing time is described by a three-parameter interval. A multi-objective optimization model with interval-valued is established to minimize the total waiting time and the total earliness/tardiness of casting time. To solve this problem， an improved fast elitist non-dominated sorting genetic algorithm （NSGAII+） based on a classification evolution strategy is presented.Firstly， a decoding scheme considering the reverse order and a hybrid population initialization based on machine rules are proposed combining interval number operation. Then a classification evolution strategy is adopted to determine the crossover and mutation operators according to the crowding distance. The re-mutation of repeated individuals is proposed to maintain the diversity of the population. Finally， the results of the experiments based on actual SCC production data shows the effectiveness of the proposed NSGAII+ in solving quality and efficiency.Note that if the upper and lower limits and intermediate parameter of all three parameter intervals are the same， the problem is transferred into a static scheduling based on standard processing time. If two of the upper and lower limits and intermediate parameters of all three parameter intervals have the same value， it will degenerate into a two-parameter interval number problem. Thus， the model and algorithm proposed in this paper are also applicable to the above two problems.

Key words: steelmaking-continuous casting, production scheduling, processing time uncertainty, interval multi-objective optimization, genetic algorithm

中图分类号:

TP273

李铁克,苏艺璇,张文新,王柏琳. 加工时间不确定的炼钢-连铸区间多目标优化调度[J]. 中国管理科学, 2024, 32(8): 95-106.

Tieke Li,Yixuan Su,Wenxin Zhang,Bailin Wang. Interval Multi-objective Optimal Scheduling for Steelmaking-continuous Casting with Processing Time Uncertainty[J]. Chinese Journal of Management Science, 2024, 32(8): 95-106.

图/表 13

图1

图2

图3

表1

管线钢不同工序作业周期时间表"

钢种	工序
钢种	冶炼	精炼1	精炼2	精炼3	浇铸
管线钢	$37 \ 33,40$	$50 \ 40,55$	$26 \ 20,30$	$20 \ 12,30$	$51 \ 47,55$

表1

表2

对比算法S测度均值统计结果"

$N$	$\| I \|$	S测度
$N$	$\| I \|$	NSGAII+	MOEA	NSGAII	INSGAII	VNSGAII	GNSGAII
8	96	0.863	0.621 ^?	0.489 ^?	0.567 ^?	0.818 ^?	0.762 ^?
16	188	0.844	0.784 ^?	0.528 ^?	0.611 ^?	0.842	0.816 ^?
24	274	0.883	0.872	0.526 ^?	0.607 ^?	0.881	0.860 ^?
32	369	0.937	0.938	0.529 ^?	0.599 ^?	0.932 ^?	0.921 ^?
40	461	0.958	0.965	0.533 ^?	0.595 ^?	0.958	0.949 ^?
50	579	0.974	0.936 ^?	0.543 ^?	0.615 ^?	0.969 ^?	0.965 ^?
60	703	0.991	0.963 ^?	0.540 ^?	0.602 ^?	0.987 ^?	0.984 ^?
平均值	381	0.921	0.868	0.527	0.599	0.913	0.894

表2

表3

对比算法I测度均值统计结果"

$N$	$\| I \|$	I测度
$N$	$\| I \|$	NSGAII+	MOEA	NSGAII	INSGAII	VNSGAII	GNSGAII
8	96	0.177	0.192 ^?	0.290 ^?	0.261 ^?	0.198 ^?	0.217 ^?
16	188	0.257	0.188^?	0.393 ^?	0.341 ^?	0.254	0.263
24	274	0.211	0.158^?	0.470 ^?	0.372 ^?	0.209	0.217 ^?
32	369	0.157	0.143	0.520 ^?	0.412 ^?	0.159	0.166 ^?
40	461	0.132	0.129	0.544 ^?	0.443 ^?	0.134	0.139 ^?
50	579	0.121	0.130	0.584 ^?	0.446 ^?	0.128 ^?	0.126 ^?
60	703	0.104	0.123	0.581 ^?	0.449 ^?	0.107	0.111 ^?
平均值	381	0.166	0.152	0.483	0.389	0.170	0.177

表3

表4

对比算法IC测度均值统计结果"

$N$	$\| I \|$	NSGAII+(A)Vs MOEA(B)		NSGAII+(A)Vs NSGAII(C)		NSGAII+(A)Vs INSGAII(D)		NSGAII+(A)Vs VNSGAII(E)		NSGAII+(A)Vs GNSGAII(F)
$N$	$\| I \|$	C(A,B)	C(B,A)	C(A,C)	C(C,A)	C(A,D)	C(D,A)	C(A,E)	C(E,A)	C(A,F)	C(F,A)
8	96	0.995	0.081 ^?	1.000	0.035 ^?	1.000	0.040 ^?	0.657	0.546 ^?	0.826	0.370 ^?
16	188	0.990	0.083 ^?	1.000	0.040 ^?	1.000	0.057 ^?	0.640	0.585	0.915	0.271 ^?
24	274	0.995	0.200 ^?	1.000	0.033 ^?	1.000	0.059 ^?	0.691	0.673	0.914	0.421 ^?
32	369	0.656	0.623	1.000	0.014 ^?	1.000	0.052 ^?	0.797	0.704	0.954	0.550 ^?
40	461	0.783	0.682	1.000	0.009 ^?	1.000	0.014 ^?	0.810	0.772	0.904	0.634 ^?
50	579	0.995	0.343 ^?	1.000	0.001 ^?	1.000	0.011 ^?	0.830	0.751 ^?	0.909	0.618 ^?
60	703	0.956	0.395 ^?	1.000	0.002 ^?	1.000	0.005 ^?	0.844	0.768	0.926	0.701 ^?
平均值	381	0.910	0.344	1.000	0.019	1.000	0.034	0.753	0.686	0.907	0.509

表4

图4

表5

算法的CPU平均运行时间/s"

$N$	$\| I \|$	NSGAII+	MOEA	NSGAII	INSGAII	VNSGAII	GNSGAII
8	96	25.38	40.31	21.99	26.07	21.47	25.58
16	188	26.16	41.47	22.64	26.68	22.14	26.29
24	274	39.77	63.71	34.26	40.53	33.55	39.78
32	369	49.89	80.38	43.27	51.17	41.98	49.92
40	461	62.26	101.50	53.68	64.19	52.67	62.89
50	579	81.28	132.67	69.34	82.57	68.02	80.91
60	703	98.53	161.33	85.45	101.19	83.07	98.77
平均值	381	54.75	88.77	47.23	56.06	46.13	54.88

表5

图5

图6

图7

图8

参考文献 20

1	俞胜平，庞新富，柴天佑，等. 加工时间不确定的炼钢-连铸生产调度问题研究［J］. 控制与决策， 2009， 24（10）： 1467-1472.
	Yu S P， Pang X F， Chai T Y， et al. Research on production scheduling for steelmaking and continuous casting with processing time uncertainty［J］. Control and Decision， 2009， 24（10）： 1467-1472.
2	Goren S， Sabuncuoglu I. Optimization of schedule robustness and stability under random machine breakdowns and processing time variability［J］. IIE Transactions， 2009， 42（3）： 203-220.
3	刘倩，杨建平，王柏琳，等. 基于“炉-机对应”的炼钢-连铸生产调度问题遗传优化模型［J］. 工程科学学报， 2020， 42（5）： 645-653.
	Liu Q， Yang J P， Wang B L， et al. Genetic optimization model of steelmaking-continuous casting production scheduling based on the “furnace-caster coordinating” strategy［J］. Chinese Journal of Engineering， 2020， 42（5）： 645-653.
4	袁帅鹏，李铁克，王柏琳. 多目标炼钢-连铸生产调度的改进带精英策略的快速非支配排序遗传算法［J］. 计算机集成制造系统， 2019， 25（1）： 115-124.
	Yuan S P， Li T K， Wang B L. Improved fast elitist non-dominated sorting genetic algorithm for multi-objective steelmaking-continuous casting production scheduling［J］. Comput Integr Manuf Syst， 2019， 25（1）： 115-124.
5	Peng K K， Pan Q K， Zhang B. An improved artificial bee colony algorithm for steelmaking-refining- continuous casting scheduling problem ［J］. Chinese Journal of Chemical Engineering， 2018， 26（8）： 1727-1735.
6	Wang D J， Liu F， Jin Y C. A proactive scheduling approach to steel rolling process with stochastic machine breakdown［J］. Natural Computing， 2019，18（4）： 679-694.
7	Long J Y， Zheng Z， Gao X Q. Dynamic scheduling in steelmaking-continuous casting production for continuous caster break down［J］. International Journal of Production Research， 2016， 55（11）： 3197-3216.
8	Yu S P， Chai T Y， Tang Y. An effective heuristic rescheduling method for steelmaking and continuous casting production process with multirefining modes［J］. IEEE Transactions on Systems，Man， and， Cybernetics： Systems， 2016， 46（12）： 1675－1688.
9	蒋胜龙，郑忠. 考虑不确定加工时间的炼钢-连铸过程柔性调度方法［J］. 计算机集成制造系统， 2019， 25（1）： 103-114.
	Jiang S L， Zheng Z. Flexible scheduling approach for steelmaking-continuous casting process with uncertain processing times［J］. Computer Integrated Manufacturing Systems， 2019， 25（1）： 103-114.
10	Wang B L， Wang H F， Li T K. Design of a monitoring and rescheduling system for steelmaking-continuous casting production［J］. International Journal of Performability Engineering，2018， 4（12）： 3076-3086.
11	Pan Q K， Wang L， Mao K， et al. An effective artificial bee colony algorithm for a real-world hybrid flowshop problem in steelmaking process［J］. IEEE Transactions on Automation Science and Engineering， 2013， 10（2）： 307-322.
12	龚日朝，潘芬萍. 非均匀分布下区间数排序可能度计算模型及其应用［J］. 中国管理科学， 2020， 28（12）： 220-230.
	Gong R Z， Pan F P. A possibility degree model for ranking interval numbers under non-uniform distribution and its application［J］. Chinese Journal of Management Science， 2020， 28（12）： 220-230.
13	王春，王艳，纪志成.求解区间柔性作业车间调度的多目标进化算法［J］.控制与决策，2019，34（5）： 908-916.
	Wang C， Wang Y， Ji Z C. Multi-objective evolutionary algorithm to solve interval flexible job shop scheduling problem［J］. Control and Decision， 2019， 34（5）： 908-916.
14	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.
15	Pan Q K. An effective co-evolutionary artificial bee colony algorithm for steelmaking-continuous casting scheduling［J］. European Journal of Operational Research， 2016， 250（3）： 702－714.
16	赵诗奎，方水良，顾新建. 基于极限调度完工时间最小化的机器选择及FJSP求解［J］. 计算机集成制造系统， 2014， 20（4）： 854－865.
	Zhao S K， Fang S L， Gu X J. Machine selection and FJSP solution based on limit scheduling completion time minimization［J］. Computer Integrated Manufacturing Systems， 2014， 20（4）： 854-865.
17	黄辉，李梦想，严永. 考虑序列设置时间的混合流水车间多目标调度研究［J］. 运筹与管理， 2020， 29（12）：215-221.
	Huang H， Li M X， Yan Y. Research on multi-objective scheduling of hybrid flow production shop considering sequence setting time［J］. Operations Research and Management Science， 2020， 29（12）： 215－221.
18	Limbourg P， Aponte D E. An optimization algorithm for imprecise multi-objective problem functions ［C］// Proceedings of IEEE Congress on Evolutionary Computation， Edinburgh， UK， Sept. 2-5， 2005.
19	张勇，巩敦卫，郝国生，等.含区间参数多目标系统的微粒群优化算法［J］.自动化学报，2008， 34（8）： 921-928.
	Zhang Y， Gong D W， Hao G S， et al. Particle swarm optimization for multi-objective systems with interval parameters［J］. Acta Automatica Sinica， 2008， 34（8）： 921-928.
20	刘青，王刚，王彬，等.基于产品结构的炼钢-连铸区段产能解析［J］. 重庆大学学报， 2014， 37（1）： 75-83.
	Liu Q， Wang G， Wang B， et al. Capacity analysis of steelmaking-continuous casting section based on different products mixes［J］. Journal of Chongqing University， 2014， 37（1）： 75-83.

[1]	初梓豪,徐哲,刘东宁. 带有活动重叠的随机调度问题建模与算法研究[J]. 中国管理科学, 2024, 32(7): 84-94.
[2]	张玲,高鹏飞,张琳. 基于剥夺成本的应急疏散与物资调配问题研究[J]. 中国管理科学, 2024, 32(5): 187-195.
[3]	马祖军, 王一然. 考虑生鲜农产品“最先一公里”损耗的预冷站选址定容[J]. 中国管理科学, 2024, 32(2): 315-323.
[4]	张歆悦,靳鹏,胡笑旋,朱默宁. 时间依赖型多配送中心带时间窗的开放式车辆路径问题研究[J]. 中国管理科学, 2024, 32(1): 146-157.
[5]	崔维伟,刘新波. 多源供电模式下企业生产运作与能源管理集成优化研究[J]. 中国管理科学, 2023, 31(8): 173-183.
[6]	陈晓红, 周明辉, 唐湘博. 城市空气质量目标约束下冬季污染物减排最优控制策略研究[J]. 中国管理科学, 2023, 31(3): 1-9.
[7]	马志强, 徐小峰, 何正文, 王能民. 复杂不确定环境下活动可拆分的项目资源鲁棒性调度优化[J]. 中国管理科学, 2022, 30(3): 117-130.
[8]	范厚明, 田攀俊, 吕迎春, 张跃光, 任晓雪. 越库配送下考虑时空距离的库门分配与车辆调度优化[J]. 中国管理科学, 2022, 30(2): 137-149.
[9]	浦徐进, 李秀峰. 基于电商承诺送达机制的多目标低碳MDVRP优化研究[J]. 中国管理科学, 2021, 29(8): 57-66.
[10]	崔维伟, 谭欣林. 分时电价下关注能耗成本的生产问题建模及算法[J]. 中国管理科学, 2021, 29(5): 147-156.
[11]	夏杰, 马新, 吴文青. 基于Simpson公式改进的FAGM(1,1)模型及其应用研究[J]. 中国管理科学, 2021, 29(5): 240-248.
[12]	彭武良, 马小菁. 一种策略层项目计划的双目标优化方法[J]. 中国管理科学, 2021, 29(2): 69-77.
[13]	徐贤浩, 王倩, 曾款, 彭红霞. 延迟支付条件下易逝品的最优订货决策研究[J]. 中国管理科学, 2021, 29(2): 108-116.
[14]	熊浩, 鄢慧丽. 考虑多种安全库存策略的选址-库存问题研究[J]. 中国管理科学, 2021, 29(1): 72-81.
[15]	项寅. 不对称信息下反恐阻止网络设计[J]. 中国管理科学, 2020, 28(9): 188-198.