Improved repair-based CSP algorithm for reheating furnaces scheduling

Computer Engineering and Applications ›› 2012, Vol. 48 ›› Issue (18): 23-26.

Previous Articles Next Articles

Improved repair-based CSP algorithm for reheating furnaces scheduling

ZHAO Yanyan1，2, LI Tieke1，2, WANG Bailin1，2

1.Dongling School of Economics and Management, University of Science & Technology Beijing, Beijing 100083, China
2.Engineering Research Center of MES Technology for Iron & Steel Production, MoE, Beijing 100083, China

Online:2012-06-21 Published:2012-06-20

求解加热炉调度的改进修复式约束满足算法

赵艳艳1，2，李铁克1，2，王柏琳1，2

1.北京科技大学东凌经济管理学院，北京 100083
2.钢铁生产制造执行系统技术教育部工程研究中心，北京 100083

Abstract

Abstract: The parallel reheating furnaces scheduling problem with capacity constraint in steel production is studied. A multi-objective mathematical model is made to minimize makespan and total process time. As the NP-hard feature, an improved repair-based CSP algorithm is proposed. The algorithm relaxes the capacity constraint and an initial schedule is got. By testing conflict variables constantly, a new one is re-assigned from the replaceable furnaces set according to the rule of minimizing deviation of starting time, and a feasible solution without conflicts is got. The experiments show that the algorithm is feasible and effective.

Key words: scheduling, capacity constraint, repair-based constraint satisfaction, Multiple Traveling Salesman Problem（MTSP）

摘要： 针对钢铁生产中加热炉调度问题，考虑炉容受限的情况，以最小化板坯的Makespan和最小化总在炉加工时间为目标建立问题的多目标优化模型，将其归结为多旅行商问题。针对问题的NP-难特性，提出一种改进的修复式约束满足算法求解。松弛炉容约束得到初始调度，在检测冲突变量并构造冲突板坯的可替换加热炉集合的基础上，以开工时间偏移最小规则为冲突板坯重新指派加热炉，得到可行的调度方案。数据实验验证了模型和算法的可行性和有效性。

关键词: 调度, 炉容约束, 修复式约束满足, 多旅行商

ZHAO Yanyan1，2, LI Tieke1，2, WANG Bailin1，2. Improved repair-based CSP algorithm for reheating furnaces scheduling[J]. Computer Engineering and Applications, 2012, 48(18): 23-26.

赵艳艳1，2，李铁克1，2，王柏琳1，2. 求解加热炉调度的改进修复式约束满足算法[J]. 计算机工程与应用, 2012, 48(18): 23-26.

[1]	XIE Ruiqiang, ZHANG Huizhen. Two-Vector Wolf Pack Algorithm for Flexible Job Shop Scheduling Problem [J]. Computer Engineering and Applications, 2021, 57(7): 251-256.
[2]	WANG Yuncheng, ZHOU Chunhua, CHEN Chuxiang, WU Shanming, CHEN Bing. Extensible Intelligent Scheduling System Based on Two Fork Knowledge Tree Reasoning [J]. Computer Engineering and Applications, 2021, 57(5): 251-257.
[3]	ZHANG Chi, WANG Yuxin, FENG Zhen, GUO He. Energy-Efficient Task Scheduling Algorithm in Two-Layer Virtualized Cloud Architecture [J]. Computer Engineering and Applications, 2021, 57(3): 103-111.
[4]	LI Baoshuai, YE Chunming. Job Shop Scheduling Problem Based on Deep Reinforcement Learning [J]. Computer Engineering and Applications, 2021, 57(23): 248-254.
[5]	CAO Lijia, LIU Yang. Recent Advances in Scheduling Optimization of Automated Guided Vehicles in Manufacturing Workshops [J]. Computer Engineering and Applications, 2021, 57(21): 59-67.
[6]	MA Yanfang, LI Baoyu, YANG Yifu, FENG Cuiying. Two-Echelon Capacitated Vehicle Routing Model and Algorithm for Fresh Products Distribution with Customer Classification [J]. Computer Engineering and Applications, 2021, 57(20): 287-298.
[7]	TIAN Zhuojing, HUANG Zhenchun, ZHANG Yinong. Review of Task Scheduling Methods in Cloud Computing Environment [J]. Computer Engineering and Applications, 2021, 57(2): 1-11.
[8]	ZHOU Yamin, YANG Yongsheng, ZHONG Meisu, WANG Yusheng, XU Xueqian. Scheduling of Crossing Double ASC in Yard of Automated Terminals [J]. Computer Engineering and Applications, 2021, 57(2): 251-256.
[9]	SHI Yuqiang, TIAN Yongzheng, ZHANG Yuqi, SHI Xiaoqiu. Solving FJSP by Multi-population Genetic Algorithms with Complex Network Structure [J]. Computer Engineering and Applications, 2021, 57(2): 257-266.
[10]	ZHOU Yuanling, HU Xiaobing, JIANG Daiyu, LI Hang. Research on Optimization Algorithm of Workshop Scheduling Based on Improved NSGA-II [J]. Computer Engineering and Applications, 2021, 57(19): 274-281.
[11]	DAI Jiangtao, HAN Xiaolong. Coordinated Scheduling of Equipment in Container Terminals Considering Energy Consumption Under Different Job Status [J]. Computer Engineering and Applications, 2021, 57(19): 290-298.
[12]	GUO Jiali, WANG Qiuping, WANG Xiaofeng. Hybrid Moth Flame Algorithm with Learning Strategy and Neighboring Search [J]. Computer Engineering and Applications, 2021, 57(12): 170-179.
[13]	LI Yuxin, LI Yueyue. Multi-objective Vehicle Scheduling Problem for JIT Procurement [J]. Computer Engineering and Applications, 2021, 57(12): 263-272.
[14]	LIANG Chengji, HUANG Shuai. Scheduling Optimization of Multiple Container Blocks with Multiple Yard Cranes at Container Terminal Based on Time Window [J]. Computer Engineering and Applications, 2020, 56(8): 226-232.
[15]	YANG Yajie, CHANG Daofang, YU Fang. Multi-Resource Coordinated Scheduling of Automated Terminals Considering AGV Collision Avoidance [J]. Computer Engineering and Applications, 2020, 56(6): 246-253.

Improved repair-based CSP algorithm for reheating furnaces scheduling

求解加热炉调度的改进修复式约束满足算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics