【作者】 孙凯；

【导师】 杨根科；

【作者基本信息】 上海交通大学 ， 控制理论与控制工程， 2009， 博士

【摘要】 生产调度是制造企业生产管理的关键,科学的制定和执行生产调度方案对提升产品质量,缩短生产周期,减少在制品库存,降低物耗和能耗,降低生产成本,提高企业竞争力有着极其重要的意义。钢铁生产调度是生产调度理论在钢铁行业特殊环境中的应用,需综合考虑钢铁工艺生产要求、计算机系统和管理方法,以通过建立合理的调度模型快速排定调度方案,使之成为钢铁生产过程的辅助决策工具。免疫算法(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算法将这些子问题的解合成为一个原问题的可行解。并通过某大型钢厂的实际数据验证了算法的有效性。更多还原

【Abstract】 Production scheduling is the key element in manufacturing enterprises, and scientifically formulating and executing it can shorten production cycle, reduce inventories of work in process, decrease the production cost and improve enterprises competitive power in the market. Steel-making production scheduling is the application of production scheduling theory in the steel-making circumstance, and it should consider several aspects such as technological requirements of steel-making, computer system and management techniques, and then make it become auxiliary decision-making tools for the steel-making process by establishing reasonable scheduling model and scheduling scheme.Immune algorithm (IA) and scatter search (SS) are population-based evolutionary algorithms which have strong global search ability, but they have many differences in evolution mechanism, search strategy and so on. The paper discusses several scheduling problem in steel-making production, analyzes their scheduling needs, presents their mathematical models, develops effective optimization algorithms to search optimal and near-optimal solutions, and then applies industrial production data to illustrate the effectiveness of these algorithms. The main objective of the paper is providing effective and reasonable scheduling scheme to steel-making industries and providing theoretical foundation for the improvement of steeling-making scheduling techniques. The main research achievements of the paper are:Firstly, the paper has studied the cost-driven flowshop scheduling problem. The paper presents a cost-driven model of the flowshop scheduling problem (FSP) by involving economic index into the problem. The cost model is developed in terms of a combination of multi-dimensional costs generated from product transitions, revenue loss, earliness / tardiness penalty, and so on. A new immune algorithm, called IA-ATS, combines the strong global search ability of IA with the strong local search ability of adaptive tabu search (ATS). The experimental simulation tests show the validity of the cost-driven model and the effectiveness of the hybrid IA-ATS algorithm.Secondly, the paper has studied continuous casting scheduling problem (CCSP). The paper presents a hybrid flow shop scheduling model for the problem, which takes continuous casting and waiting time of furnaces as constraints, and takes total flowtime of process as objective function. A production scheduling method which combines heuristic rule and linear programming is presented after considering the solving complexity of the problem, and then embedded into the IA-ATS algorithm. The experimental results show that the algorithm is an effective method for the CCSP. It can realize continuous casting during working process, improve the equipment usage efficiency, reduce the waiting time between different operations, reduce materials and energy consumption, and consequently reduce production cost and improve the profit of steel-making enterprises.Thirdly, the paper has studied hot rolling scheduling problem. We apply prize-collecting vehicle routing problem to present the mathematical model of hot rolling scheduling problem after considering switchover cost of roller and customer service level. The mathematical model combines order selection with slab sequencing, and takes reducing the width, gauge and hardness jump penalty and satisfying delivery date as scheduling objectives. And then, a new scatter search algorithm (SS-IEO) which combines scatter search (SS) with improved extremal optimization (IEO) is proposed. The hybrid SS-IEO algorithm combines the strong global search ability of SS with the strong local search ability of IEO and mitigates their disadvantages. Several experiment simulations of steel-making enterprise production instances are conducted to illustrate the effectiveness of algorithm. The computational results show that the algorithm can get satisfied scheduling solutions in reasonable running time and is superior to IA-ATS, but has less generality than IA-ATS.Lastly, the paper studied the cold rolling scheduling problem. Skin pass mill scheduling problem is a very complex problem which has coupling between coil parameters and machine performance. In chapter 5, the paper presents an effective decomposition-combination mechanism which divides the complex scheduling problem into three tractable sub-problems: clusting problem, K- constrained shortest path problem (K-CSSP), and multi-phase shortest path problem. A mixed strategy which combines SS-IEO with dynamic programming (DP) is presented: firstly assigning orders into different stages, and then solving the K-CSSP of each stage by SS-IEO, and combining the solutions of sub-problems into a feasible solution by DP at last phase. The computational experiments demonstrate the effectiveness of the proposed strategy.更多还原