考虑订单扰动因素的热轧重调度分布估计算法

doi:10.11772/j.issn.1001-9081.2021061106

《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (8): 2628-2636.DOI: 10.11772/j.issn.1001-9081.2021061106

• 前沿与综合应用 • 上一篇

考虑订单扰动因素的热轧重调度分布估计算法

王一荻¹^,², 李志伟³, 张文新¹^,²(), 李铁克¹^,², 王柏琳¹^,²

^1.北京科技大学经济管理学院, 北京 100083
^2.钢铁生产制造执行系统技术教育部工程研究中心(北京科技大学), 北京 100083
^3.宁波钢铁有限公司, 浙江宁波 315807

收稿日期:2021-06-28 修回日期:2021-12-23 接受日期:2022-01-04 发布日期:2022-01-25 出版日期:2022-08-10
通讯作者: 张文新
作者简介:王一荻（1996—），女，辽宁沈阳人，硕士研究生，主要研究方向：生产计划与调度、先进制造管理；
李志伟（1979—），男，山东潍坊人，高级工程师，硕士，主要研究方向：生产管理、钢铁企业智能制造技术；
张文新（1966—），男，河北保定人，副教授，博士，主要研究方向：先进制造管理、电子商务；
李铁克（1958—），男，吉林长春人，教授，博士，主要研究方向：先进制造管理、生产计划与调度；
王柏琳（1983—），女，河北石家庄人，副教授，博士，主要研究方向：生产调度优化。
基金资助:
国家自然科学基金资助项目(71701016);教育部人文社会科学研究青年基金资助项目(17YJC630143);北京市自然科学基金资助项目(9174038);中央高校基本科研业务费专项资金资助项目(FRF-BD-20-16A)

Estimation of distribution algorithm for hot rolling rescheduling with order disturbance

Yidi WANG¹^,², Zhiwei LI³, Wenxin ZHANG¹^,²(), Tieke LI¹^,², Bailin WANG¹^,²

^1.School of Economics and Management，University of Science and Technology Beijing，Beijing 100083，China
^2.Engineering Research Center of MES Technology for Iron and Steel Production，Ministry of Education （University of Science and Technology Beijing），Beijing 100083，China
^3.Ningbo Iron and Steel Company Limited，Ningbo Zhejiang 315807，China

Received:2021-06-28 Revised:2021-12-23 Accepted:2022-01-04 Online:2022-01-25 Published:2022-08-10
Contact: Wenxin ZHANG
About author:WANG Yidi， born in 1996， M. S. candidate. Her research interests include production planning and scheduling， advanced manufacturing management.
LI Zhiwei， born in 1979， M. S.， senior engineer. His research interests include production management， intelligent manufacturing technology for iron and steel enterprises.
ZHANG Wenxin， born in 1966， Ph. D.， associate professor. His research interests include advanced manufacturing management， electronic commerce.
LI Tieke， born in 1958， Ph. D.， professor. His research interests include advanced manufacturing management， production planning and scheduling.
WANG Bailin， born in 1983， Ph. D.， associate professor. Her research interests include production scheduling optimization.
Supported by:
National Natural Science Foundation of China(71701016);Humanity and Social Science Youth Foundation of Ministry of Education of China(17YJC630143);Beijing Natural Science Foundation(9174038);Fundamental Research Funds for Central Universities(FRF-BD-20-16A)

摘要/Abstract

摘要：

热轧工序作为钢铁生产的核心环节，具有严格的生产连续性和复杂的产品工艺要求，而紧急订单的随机到达和紧急交货期要求会对生产连续性和质量稳定性产生不利影响。针对这类紧急订单插入的动态事件，提出一种热轧重调度优化方法。首先，分析了订单扰动因素对调度方案的影响，并以最小化订单拖期惩罚和板坯跳跃惩罚加权和为优化目标，建立了热轧重调度问题的数学模型。然后，设计了热轧重调度分布估计算法（EDA）。该算法针对紧急订单的插入式处理方式，提出一种基于插入位置的整数编码方案；结合模型特征设计了概率模型；并综合考虑目标与约束，定义了基于惩罚值的适应度函数。通过实际生产数据进行仿真实验，验证了模型和算法的可行性和有效性。

关键词: 重调度, 热轧, 订单插入扰动, 分布估计算法, 拖期

Abstract:

As the core of steel production， hot rolling process has demands of strict production continuity and complex production technology. The random arrival of rush orders and urgent delivery requirements have adverse impacts on production continuity and quality stability. Aiming at those kind of dynamic events of rush order insertion， a hot rolling rescheduling optimization method was proposed. Firstly， the influence of order disturbance factor on the scheduling scheme was analyzed， and a mathematical model of hot rolling rescheduling was established with the optimization objective of minimizing the weighted sum of tardiness of orders and jump penalty of slabs. Then， an Estimation of Distribution Algorithm （EDA） for hot rolling rescheduling was designed. In this algorithm， aiming at the insertion processing of rush orders， an integer encoding scheme was proposed based on the insertion position， the probability model based on the characteristics of the model was designed， and the fitness function based on the penalty value was defined by considering the targets and constraints comprehensively. The feasibility and validity of the model and the algorithm were verified by the simulation experiment on the actual production data.

Key words: rescheduling, hot rolling, order insertion disturbance, Estimation of Distribution Algorithm (EDA), tardiness

中图分类号:

TP205

王一荻, 李志伟, 张文新, 李铁克, 王柏琳. 考虑订单扰动因素的热轧重调度分布估计算法[J]. 计算机应用, 2022, 42(8): 2628-2636.

Yidi WANG, Zhiwei LI, Wenxin ZHANG, Tieke LI, Bailin WANG. Estimation of distribution algorithm for hot rolling rescheduling with order disturbance[J]. Journal of Computer Applications, 2022, 42(8): 2628-2636.

图/表 11

参考文献 19

1	杨业建，姜泽毅，张欣欣.板坯热轧批量计划数学模型及求解算法［J］.北京科技大学学报， 2012， 34（4）： 457-463.
	YANG Y J， JIANG Z Y， ZHANG X X. Mathematical model and solving algorithm for the lot planning of slab hot rolling［J］. Journal of University of Science and Technology Beijing， 2012， 34（4）： 457-463.
2	李铁克，郭冬芬.基于约束满足的热轧批量计划模型与算法［J］.控制与决策， 2007， 22（4）： 389-393， 398. 10.3321/j.issn:1001-0920.2007.04.006
	LI T K， GUO D F. Model and algorithm for hot-rolling batch plan based on constraint satisfaction［J］. Control and Decision， 2007， 22（4）： 389-393， 398. 10.3321/j.issn:1001-0920.2007.04.006
3	PAN Q K， CHEN Q D， MENG T， et al. A mathematical model and two-stage heuristic for hot rolling scheduling in compact strip production［J］. Applied Mathematical Modelling， 2017， 48： 516-533. 10.1016/j.apm.2017.03.067
4	CHEN Q D， PAN Q K， ZHANG B， et al. Effective hot rolling batch scheduling algorithms in compact strip production［J］. IEEE Transactions on Automation Science and Engineering， 2019， 16（4）： 1933-1951. 10.1109/tase.2019.2914925
5	刘健，王彬，王柏琳，等.板坯热轧计划编制的优化模型与算法［J］.计算机集成制造系统， 2015， 21（12）： 3263-3270. JournalArticle/5b3b4a39c095d70f0069c4d9
	LIU J， WANG B， WANG B L， et al. Optimization model and algorithm for slab hot rolling planning problem［J］. Computer Integrated Manufacturing Systems， 2015， 21（12）： 3263-3270. JournalArticle/5b3b4a39c095d70f0069c4d9
6	张涛，王梦光，杨建夏.不确定计划数的轧制批量计划的模型和算法［J］.系统工程学报， 2000， 15（1）： 54-60. 10.3969/j.issn.1000-5781.2000.01.009
	ZHANG T， WANG M G， YANG J X. The model and algorithm for the hot-milling batch planning with uncertain number［J］. Journal of Systems Engineering， 2000， 15（1）： 54-60. 10.3969/j.issn.1000-5781.2000.01.009
7	TANG L X， HUANG L. Optimal and near-optimal algorithms to rolling batch scheduling for seamless steel tube production［J］. International Journal of Production Economics， 2007， 105（2）： 357-371. 10.1016/j.ijpe.2004.04.011
8	吴子轩，李铁克，张文新，等.考虑交货因素的热轧无缝钢管订单排程模型与算法［J］.中国管理科学， 2018， 26（5）： 129-137.
	WU Z X， LI T K， ZHANG W X， et al. Order scheduling model and algorithm for hot-rolled seamless steel tube with delivery requirements［J］. Chinese Journal of Management Science， 2018， 26（5）： 129-137.
9	柏亮，李铁克，王柏琳，等.基于变邻域搜索的热轧圆钢批量调度多目标优化方法［J］.工程科学学报， 2015， 37（1）： 111-117. 10.13374/j.issn2095-9389.2015.01.017
	BAI L， LI T K， WANG B L， et al. Variable neighborhood search based multi-objective optimization method for batch scheduling of hot-rolled bars［J］. Chinese Journal of Engineering， 2015， 37（1）： 111-117. 10.13374/j.issn2095-9389.2015.01.017
10	SUH M S， LEE A， LEE Y J， et al. Evaluation of ordering strategies for constraint satisfaction reactive scheduling［J］. Decision Support Systems， 1998， 22（2）： 187-197. 10.1016/s0167-9236(97)00052-3
11	潘瑞林，胡邦国，曹建华，等.基于仿真优化的加热炉—热轧区间重调度［J］.计算机集成制造系统， 2014， 20（6）： 1405-1415.
	PAN R L， HU B G， CAO J H， et al. Heating furnace and hot rolling interval rescheduling based on simulation optimization［J］. Computer Integrated Manufacturing Systems， 2014， 20（6）： 1405-1415.
12	郭延欣，李铁克，张文学.基于人机交互的热轧动态调度［J］.计算机工程与设计， 2012， 33（1）： 367-371. 10.3969/j.issn.1000-7024.2012.01.072
	GUO Y X， LI T K， ZHANG W X. Dynamic scheduling of hot rolling based on human-computer interaction［J］. Computer Engineering and Design， 2012， 33（1）： 367-371. 10.3969/j.issn.1000-7024.2012.01.072
13	刘乐.单机最大延迟重调度的和声变邻域搜索算法［J］.计算机集成制造系统， 2016， 22（8）： 1977-1991. 10.13196/j.cims.2016.08.016
	LIU L. Harmony variable neighborhood search algorithm for single-machine maximum lateness rescheduling［J］. Computer Integrated Manufacturing Systems， 2016， 22（8）： 1977-1991. 10.13196/j.cims.2016.08.016
14	TIGHAZOUI A， SAUVEY C， SAUER N. Predictive-reactive strategy for flowshop rescheduling problem： minimizing the total weighted waiting times and instability［J］. Journal of Systems Science and Systems Engineering， 2021， 30（3）： 253-275. 10.1007/s11518-021-5490-8
15	PENG K K， DENG X D， ZHANG C J， et al. An improved imperialist competitive algorithm for hybrid flowshop rescheduling in steelmaking-refining-continuous casting process［J］. Measurement and Control， 2020， 53（9/10）： 1920-1928. 10.1177/0020294020960187
16	GUO Y D， HUANG M， WANG Q， et al. Single-machine rework rescheduling to minimize maximum waiting-times with fixed sequence of jobs and ready times［J］. Computers and Industrial Engineering， 2016， 91： 262-273. 10.1016/j.cie.2015.11.021
17	CALDEIRA R H， GNANAVELBABU A， VAIDYANATHAN T. An effective backtracking search algorithm for multi-objective flexible job shop scheduling considering new job arrivals and energy consumption［J］. Computers and Industrial Engineering， 2020， 149： No.106863. 10.1016/j.cie.2020.106863
18	王圣尧，王凌，方晨，等.分布估计算法研究进展［J］.控制与决策， 2012， 27（7）： 961-966， 974.
	WANG S Y， WANG L， FANG C， et al. Advances in estimation of distribution algorithms［J］. Control and Decision， 2012， 27（7）： 961-966， 974.
19	KOSIBA E D， WRIGHT J R， COBBS A E. Discrete event sequencing as a traveling problem［J］. Computers in Industry， 1992， 19（3）： 317-327. 10.1016/0166-3615(92)90069-y

下跳/mm	惩罚值	反跳/mm	惩罚值
［0，50）	1	［0，50）	2
［50，100）	3	［50，100）	6
［100，150）	20	［100，150）	40
［150，200）	50	［150，200）	100
［200，250）	100	［200，250）	200
［250，300）	200

下跳/mm	惩罚值	反跳/mm	惩罚值
［0，50）	1	［0，50）	2
［50，100）	3	［50，100）	6
［100，150）	20	［100，150）	40
［150，200）	50	［150，200）	100
［200，250）	100	［200，250）	200
［250，300）	200

上跳/mm	惩罚值	下跳/mm	惩罚值
［0.00，0.30）	3	［0.00，0.30）	6
［0.30，0.60）	10	［0.30，0.60）	20
［0.60，0.90）	20	［0.60，0.90）	40
［0.90，1.20）	50	［0.90，1.20）	100
［1.20，1.50）	90	［1.20，1.50）	180
［1.50，1.80）	150	［1.50，1.80）	300
［1.80，2.10）	300	［1.80，2.10）	600

上跳/mm	惩罚值	下跳/mm	惩罚值
［0.00，0.30）	3	［0.00，0.30）	6
［0.30，0.60）	10	［0.30，0.60）	20
［0.60，0.90）	20	［0.60，0.90）	40
［0.90，1.20）	50	［0.90，1.20）	100
［1.20，1.50）	90	［1.20，1.50）	180
［1.50，1.80）	150	［1.50，1.80）	300
［1.80，2.10）	300	［1.80，2.10）	600

t	n₂	EDA		TGA		PGA		ANOVA （γ = 0.05）
t	n₂	avg	Std	avg	Std	avg	Std	F	P-value/10^-3
200	50	23.80	4.21	42.60	10.69	47.00	13.32	7.36	8.21
	100	72.50	19.62	158.80	45.03	136.80	27.29	9.53	3.32
	150	235.60	41.38	391.20	66.17	316.40	63.04	11.78	1.48
	200	428.70	50.53	686.80	96.08	592.00	91.74	12.32	1.23
1 020	50	47.60	8.32	41.40	5.98	64.65	12.58	8.22	5.65
	100	128.00	17.26	254.40	63.62	185.62	50.87	8.66	4.69
	150	302.90	44.65	534.20	93.49	488.00	92.48	11.66	1.54
	200	525.60	61.20	803.20	106.52	795.00	104.50	14.39	0.66
1 370	50	69.80	18.17	174.40	48.26	71.45	37.57	11.88	1.43
	100	215.50	26.03	435.40	99.08	397.00	91.96	10.92	1.99
	150	404.30	49.66	650.60	96.18	589.80	91.47	13.35	0.89
	200	670.60	72.19	987.20	126.97	933.10	109.97	14.71	0.59
平均		260.41	34.44	430.02	71.51	384.74	65.57	11.23	2.64

考虑订单扰动因素的热轧重调度分布估计算法

Estimation of distribution algorithm for hot rolling rescheduling with order disturbance

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 19

相关文章 8

编辑推荐

Metrics

t	n₂	不同算法的CPU时间/s
t	n₂	EDA	TGA	PGA
200	50	106.67	2.43	3.29
	100	217.53	2.49	3.68
	150	329.27	2.69	3.45
	200	449.44	3.91	4.02
1 020	50	63.64	1.93	2.17
	100	116.19	2.96	3.09
	150	185.39	2.49	2.78
	200	250.51	2.58	2.79
1 370	50	45.93	1.94	2.07
	100	92.97	1.96	2.55
	150	138.75	2.25	2.18
	200	179.56	2.56	3.27
平均		181.32	2.52	2.95

[1]	王永航, 张天宇, 郑红星. 考虑恶劣天气的班轮多阶段重调度方法[J]. 计算机应用, 2021, 41(1): 286-294.
[2]	蔡芸, 刘朋青, 熊禾根. 基于量子遗传混合算法的泊位联合调度[J]. 计算机应用, 2020, 40(3): 897-901.
[3]	周伟平刘兵兵. 解灰色非线性规划问题的随机搜索算法[J]. 计算机应用, 2013, 33(10): 2819-2821.
[4]	侯雪梅刘伟高飞李志博王婧. 基于群智能的模糊多目标软件可靠性冗余分配[J]. 计算机应用, 2013, 33(04): 1142-145.
[5]	杨开兵刘晓冰. 流水车间成组工件调度问题的多目标优化算法[J]. 计算机应用, 2012, 32(12): 3343-3346.
[6]	侯东亮李铁克. 基于动态约束满足的炼钢连铸重调度算法[J]. 计算机应用, 2012, 32(12): 3553-3557.
[7]	杨森孟晨王成. 电子系统健康状态监测数据优化算法[J]. 计算机应用, 2012, 32(10): 2927-2930.
[8]	罗小川，王成恩. 单机序列相关Setup最小化最大拖期算法[J]. 计算机应用, 2005, 25(08): 1829-1832.

上跳/下跳	惩罚值
0	0
1	20
2	60

上跳/下跳	惩罚值
0	0
1	20
2	60