基于免疫算法与分散搜索的钢铁生产调度研究

摘要

生产调度是制造企业生产管理的关键,科学的制定和执行生产调度方案对提升产品质量,缩短生产周期,减少在制品库存,降低物耗和能耗,降低生产成本,提高企业竞争力有着极其重要的意义。钢铁生产调度是生产调度理论在钢铁行业特殊环境中的应用,需综合考虑钢铁工艺生产要求、计算机系统和管理方法,以通过建立合理的调度模型快速排定调度方案,使之成为钢铁生产过程的辅助决策工具。
　　 免疫算法(IA)与分散搜索(SS)都是基于种群的进化算法,具有很强的全局搜索能力,但在进化机制和搜索策略上有许多不同之处。本文主要以钢铁生产调度为背景,针对各问题的生产工艺流程及工艺约束,分析其调度需求,建立调度模型,然后根据不同问题的特点,选择适合的算法,并结合其他策略,设计求解该问题的优化算法,通过应用工业生产数据来验证算法的有效性。从而为实际钢铁生产提供有效的调度方案,为钢铁生产调度技术的进一步发展提供理论基础。本文取得的主要研究成果为:
　　 首先,本文研究了面向成本的流水作业(Flowshop)调度问题。将经济指标融入Flowshop调度问题中,提出一种面向成本的Flowshop调度问题的混合整数规划模型。该模型综合考虑了影响调度决策的各种加权指标,如生产切换费用、机器空闲造成的损失、工件提前/拖期完工造成的损失等。基于免疫进化机制,在免疫算法框架中引入一种自适应禁忌搜索(ATS)对种群进行局部改进,提出了一种新的免疫算法(IA-ATS)求解该问题。算法充分利用免疫算法的全局寻优能力,并结合了禁忌搜索的局部寻优能力,不同规模的仿真算例验证了该模型的可行性及算法的有效性。
　　 其次,针对钢铁制造过程中的炼钢-连铸调度问题,以控制连续浇铸及炉次在工序间等待为约束,以总加工流程时间为目标函数,建立了该问题的混合Flowshop调度模型。利用IA-ATS算法求解该问题,针对炼钢-连铸调度问题的求解复杂性,设计了一种新的抗体编码方案,并利用时间倒推法与线性规划结合的生产作业编排方法求解抗体的亲和度。实验结果表明该算法是一种有效的炼钢-连铸生产调度优化方法,能够编制出实现连浇的可执行的炼钢作业计划,并且可以降低炉次在各工序间等待造成的损失,减小总加工流程时间,从而达到降低企业运行成本、增加企业盈利的目的。
　　 再次,研究了钢铁企业中的热轧生产调度问题。根据热轧生产过程中的各种工艺约束,以降低厚度、宽度、硬度跳变引起的惩罚及满足合同交货期为调度目标,将热轧生产调度问题建模为奖金收集的车辆路径问题。该模型将热轧生产过程中板坯选择与板坯排序结合起来,综合考虑了轧辊的更换成本以及客户服务水平等指标。基于分散搜索“分散-收敛集聚”的进化机制,在分散搜索算法框架中嵌入极值优化算法以提高算法局部搜索能力,提出了一种新的分散搜索算法(SS-IEO)求解该问题。利用实际生产数据对算法进行验证,仿真结果表明SS-IEO算法虽然不能保证取得全局最优解,但是能够在合理的运算时间内求得比较满意的调度方案。
　　 最后,研究了钢铁企业中的冷轧平整机批量轧制调度问题。冷轧平整机生产过程中,不同薄钢板需要不同的表面粗糙度的轧辊下处理,而轧辊的表面粗糙度参数随着轧制过程的进行将不断的衰减,且衰减的动态过程又与轧件的调度次序密切相关。针对冷轧平整机轧件与轧辊参数耦合的特点,建立了设备参数动态变化下调度的数学模型。以轧辊磨损函数为切入点,通过对轧辊磨损曲线的分段线性简化,将复杂的调度问题分解为三个子问题,即聚类问题、K-最短路径问题(K-CSPP)、多级最短路径问题。开发了解决基于分散搜索(SS-IEO)和动态规划(DP)相结合的混合策略,首先根据约束条件,将订单分配到不同的类中,然后通过SS-IEO算法对每个订单类求解K-CSPP,最后通过DP算法将这些子问题的解合成为一个原问题的可行解。并通过某大型钢厂的实际数据验证了算法的有效性。

目录

文摘

英文文摘

上海交通大学博士学位论文答辩决议书

第一章 绪论

1.1 引言

1.2 钢铁制造工艺流程及调度问题特点

1.3 国内外钢铁生产调度研究方法、现状与热点

1.3.1 数学规划方法

1.3.2 人工智能算法

1.3.3 混合优化算法

1.3.4 钢铁生产调度理论研究热点

1.4 免疫算法与分散搜索概述

1.4.1 免疫算法

1.4.2 分散搜索

1.4.3 免疫算法与分散搜索比较

1.5 本文主要研究内容

第二章 基于免疫算法的面向成本的Flowshop调度问题研究

2.1 引言

2.2 Flowshop调度问题概述

2.2.1 一般车间调度问题的特点和分类

2.2.2 Flowshop调度问题描述

2.2.3 Flowshop调度问题研究现状

2.3.4 面向成本的Flowshop调度问题优化模型

2.3 免疫算法求解面向成本的Flowshop调度问题

2.3.1 抗体编码方案

2.3.2 抗体亲和度和浓度函数

2.3.3 免疫算子设计

2.3.4 抗体群更新

2.3.5 基于自适应禁忌搜索的局部改进策略

2.3.6 求解面向成本的Flowshop调度问题的免疫算法流程

2.4 仿真结果

2.5 本章小结

第三章 基于免疫算法的炼钢-连铸生产调度问题研究

3.1 引言

3.2 炼钢连铸生产调度问题概述

3.2.1 炼钢连铸生产工艺流程

3.2.2 炼钢连铸生产调度特点与难点

3.2.3 炼钢连铸生产调度研究现状

3.2.4 炼钢连铸生产调度的优化模型

3.3 免疫算法求解炼钢-连铸生产调度问题

3.3.1 抗体编码方案

3.3.2 寸间倒推与线性规划相结合的方法求解抗体亲和度

3.3.3 抗体浓度计算

3.3.4 免疫算子设计

3.3.5 抗体群更新

3.3.6 基于自适应禁忌搜索算法的局部改进策略

3.3.7 求解炼钢-连铸生产调度问题的免疫算法流程

3.4 仿真结果

3.5 本章小结

第四章 基于分散搜索的热轧生产调度问题研究

4.1 引言

4.2 热轧生产调度问题概述

4.2.1 热轧生产流程与工艺约束

4.2.2 热轧生产调度问题的研究方法

4.2.3 热轧生产调度问题的优化模型

4.3 分散搜索求解热轧生产调度问题

4.3.1 解编码方案与目标值定义

4.3.2 启发式规则产生初始种群

4.3.3 参考集构造与更新

4.3.4 子集的拆分

4.3.5 组合策略

4.3.6 基于Swap算子的改进策略

4.3.7 基于极值优化算法的改进策略

4.3.8 求解热轧生产调度问题的分散搜索算法流程

4.4 仿真结果

4.5 本章小结

第五章 基于分散搜索和动态规划的分解策略求解平整机调度问题

5.1 引言

5.2 平整机调度问题概述

5.2.1 冷轧薄板工艺流程

5.2.2 平整机调度问题的优化模型

5.3 基于分散搜索和动态规划的分解策略求解平整机调度问题

5.3.1 聚类问题

5.3.2 求解K最短路径问题的分散搜索算法

5.3.3 最短路径问题的动态规划算法

5.4 仿真结果

5.5 本章小结

第六章 总结与展望

6.1 本文工作总结

6.2 进一步的研究内容

参考文献

致谢

攻读博士学位期间已发表、录用和完成的论文