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

• 博士论坛 • 上一篇    下一篇

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

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

  1. 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. 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

摘要: 针对钢铁生产中加热炉调度问题,考虑炉容受限的情况,以最小化板坯的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)