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

计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (18): 23-26.

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

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

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

出版日期:2012-06-21 发布日期:2012-06-20

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

摘要/Abstract

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

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

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）

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

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]	谢锐强，张惠珍. 求解柔性作业车间调度问题的两段式狼群算法[J]. 计算机工程与应用, 2021, 57(7): 251-256.
[2]	张驰，王宇新，冯振，郭禾. 双层虚拟化云架构下任务调度能耗优化算法[J]. 计算机工程与应用, 2021, 57(3): 103-111.
[3]	许德刚，李凡，王露，郭奕欣，邢奎杰，梁腾翔. 优化烟花算法在医疗物资应急调度中的应用[J]. 计算机工程与应用, 2021, 57(24): 249-258.
[4]	李宝帅，叶春明. 深度强化学习算法求解作业车间调度问题[J]. 计算机工程与应用, 2021, 57(23): 248-254.
[5]	曹立佳，刘洋. 制造车间自动导引车调度新进展[J]. 计算机工程与应用, 2021, 57(21): 59-67.
[6]	田倬璟，黄震春，张益农. 云计算环境任务调度方法研究综述[J]. 计算机工程与应用, 2021, 57(2): 1-11.
[7]	周亚民，杨勇生，仲美稣，王宇生，许学谦. 自动化码头堆场穿越式双ASC调度[J]. 计算机工程与应用, 2021, 57(2): 251-256.
[8]	石宇强，田永政，张雨琦，石小秋. 运用含复杂网络结构的多种群遗传算法求解FJSP[J]. 计算机工程与应用, 2021, 57(2): 257-266.
[9]	代江涛，韩晓龙. 考虑作业状态能耗的集装箱码头设备协调调度[J]. 计算机工程与应用, 2021, 57(19): 290-298.
[10]	李荣，贺兴时，杨新社. 基于差分进化的飞蛾算法在电力调度中的应用[J]. 计算机工程与应用, 2021, 57(13): 258-268.
[11]	李雨鑫，李悦悦. 面向JIT采购的多目标车辆调度[J]. 计算机工程与应用, 2021, 57(12): 263-272.
[12]	郭佳丽，王秋萍，王晓峰. 融合学习策略和邻域搜索的飞蛾火焰算法[J]. 计算机工程与应用, 2021, 57(12): 170-179.
[13]	梁承姬，黄帅. 考虑时间窗的集装箱港口场桥全局调度优化[J]. 计算机工程与应用, 2020, 56(8): 226-232.
[14]	杨雅洁，苌道方，余芳. 考虑AGV避碰的自动化码头多资源协同调度[J]. 计算机工程与应用, 2020, 56(6): 246-253.
[15]	秦琴，梁承姬. 自动化码头考虑缓冲区的设备协调调度优化[J]. 计算机工程与应用, 2020, 56(6): 262-270.