【作者】 潘常春；

【导师】 杨根科；

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

【摘要】 组合优化问题广泛存在于科学研究和工程应用中的各个领域。设计快速、可靠的最优化算法一直是研究者不懈努力的目标。随着现代社会日益增多的复杂问题,传统的确定性最优化方法存在计算复杂性方面的局限性,而启发式算法,包括现代智能优化算法在内,尽管简单、通用,但是不能保证解的质量。因此如何设计一种集成两种算法优点并应用于实际问题的混合算法正成为学术界关注的热点问题之一。而在钢铁生产中,尤其是在轧制调度问题中,存在着大量的组合优化问题。轧制过程是钢铁生产过程中的关键工序之一,优化钢铁轧制过程直接关系到成品的质量、库存的成本、客户的满意度。因此,该研究具有重要的经济意义。本文提出了基于反馈校正机制的混合优化算法,并分别针对薄板生产过程中的热轧调度问题和冷轧连续镀锌生产线调度问题做了深入的研究,其创新点主要概括有如下两个方面:从建模的角度,考虑了轧辊和轧件之间的耦合效应,建立了基于时变参数的调度模型。建模的难点是由于不同的轧件调度会造成不同程度的轧辊磨损,轧辊的磨损程度会直接影响轧件的性能,从而影响后续的调度结果。轧件和轧辊的耦合效应在连续镀锌线的平整机生产过程中体现的尤为明显。从算法的角度,设计了基于反馈校正原理的集成数学规划和启发式算法的混合算法框架。目的在于利用数学规划的精确性和启发式算法的快速性求解组合优化问题。反馈校正算法的原理是通过算法之间的大量信息交互,使得在不影响最优解的前提下简化问题。具体研究内容包括以下几个方面:(1)提出了解决非对称旅行商问题(ATSP)的基于反馈校正原理的优化算法框架。ATSP是许多工业生产调度问题原型,也是热轧问题需要解决的一个关键子问题。该方法核心是依据ATSP问题松弛模型对偶关系推断ATSP最优解被排除弧集合的弧排除算法。算法框架以ATSP问题的弧集合作为“参考输入”,以ATSP最优解的上下界求解算法作为“控制对象”,以弧排除算法作为“反馈校正控制器”,其“反馈输入”是“控制对象”的上下界差值。算法迭代过程中,上下界差值缩小,排除弧集合增加,算法呈现出自收敛性。该框架将数学规划方法和元启发式算法系统的集成在一个统一的框架之中,无论从理论上和还是从仿真上都充分说明该自收敛算法是非常有效的。(2)建立了热轧计划、调度问题的基于多路径、多目标的数学模型。与以往热轧模型不同之处在于:(i)将同宽度连续轧制数量的限制建立为资源约束模型;(ii)通过递阶目标层次结构,将原问题分解为易于解决的子问题求解。提出了基于数学规划与启发式方法相结合的混合策略。针对大型工业调度问题,以求近优解为出发点。算法的主要思想是根据对问题的宏观分析,松弛模型的复杂约束,通过数学规划定位最优解或者近优解的理想区域,然后由启发式算法进行后续寻优或者修复不可行解。相对与一般的混合算法,这种策略不仅可以找到相当出色的次优解,并且能够给出下界,可对解的性能做有效的评估。(3)针对复杂的连续镀锌生产线调度问题,考虑了轧辊性能与轧件之间耦合约束,并建立了时间相关旅行商问题(TDTSP)的调度模型,提出了基于反馈校正机制的上、下界并行求解算法。以第二章提出的框架为基础,在该框架之中嵌入了次梯度算法,使得在求解原始松弛问题的对偶问题过程中出现的大量对偶信息能够被有效的利用以降低问题的规模,并在此基础之上,归纳了解元素集排除过程及其算法实施的一般形式。而在一般的求解整数规划过程中,是根据对偶理论求解原问题松弛问题的对偶问题获得下界。如果该下界对应的解是可行的,则已经找到了最优解。若不可行,则采用分支定界或其他修复策略获得最优或者近优解。这种串行处理策略,只利用到了最后的下界信息,而没有利用到求解对偶问题过程出现的大量对偶信息。因此,如果不能充分利用计算获得的问题内部信息作为指导,算法性能会降低。本文对钢铁生产中的关键问题之一批量轧制调度问题从建模和算法设计两个方面都做了较为深入的探讨,研究成果可为优化钢铁生产物流水平,提高生产作业计划与调度的效率和质量提供理论与技术支持。本文研究工作受国家自然科学基金项目(No. 60574063)和香港城市大学基金(No. CityU122305)的资助。更多还原

【Abstract】 Optimization problem exists widely in all domains of scientific research and engineering applications. Much effort has been, and will continue to be, devoted to the design of good optimization algorithms, that is the algorithm which find extrema or near extrema reliably and quickly. Traditional deterministic methods appear to be unrealistic when solving complex problem involving in modern practical applications due to great computational complexity. Heuristic methods, including intelligent optimization algorithms, are simple, general and can be implemented easily but they can not provide solutions with quality guaranteed. So, how to design a hybrid and applicable algorithm with both advantages of the two kinds of methods is attracting more and more interests of worldwide domain scholars. Meanwhile, there are many optimization problems arising in steel production, in particularly in rolling batch scheduling problem. The rolling process is one of the most important parts in the whole procedure of steel production and thus is of great importance with respect to improving the final product quality, to reducing the inventory cost and to making a more responsive position towards customers. Therefore, the research is of great economical profits.In this dissertation, a novel optimization method with feedback and self-tuning mechanism is proposed. Moreover, the Hot Strip Mill (HSM) scheduling problem as well as the Continuous Galvanizing Line (CGL) scheduling problem based on the proposed method are studied carefully. Concretely, the major contributions involved in this dissertation are twofold:From the viewpoint of the modeling, a time-dependent parameter model is established to consider the coupling effect between jobs (coils or slabs) and the machine (rolls). The mutual-effect lies in that jobs through the mill will wear the rolls and change physical parameters of surface of rolls meanwhile the physical parameters of surface will determine the posterior rolling sequence to avoid fabricating substandard products. Such mutual-effect is notable especially in the process of skin pass in CGL.From the viewpoint of the algorithm, a novel algorithm with feedback and self-tuning mechanism is proposed to solve combinatorial optimization in which the mathematical programming and the heuristic methods are integrated systematically. The motivation is to take full advantage of both the two kinds of algorithms to solve complex combinatorial problems. The most prominent advantage of the algorithm lies in that algorithms involved in the hybrid framework is interactive through a simple mechanism, which can reduce the searching region without excluding the optimality.The main topics included in this dissertation are generalized as follows:(1)A novel algorithmic framework based on the feedback and self-tuning mechanism is proposed to solve the asymmetric traveling salesman problem (ATSP). ATSP and its variations are very commonly used models to formulate many practical problems. Here, ATSP is a key sub-problem that has to deal with in order to solve the HSM scheduling problem. The main idea hint in the framework is that we develop an algorithm to exclude increasingly arcs not belonging to the optimal solution using the dual information produced during solving the dual problem of the relaxed ATSP problem. In the framework, the solution components set is regarded as the“reference input”, and the lower-bound solver as well as the upper bound solver is served as the“controlled plant”. The algorithm of excluding arcs not belonging to the optimal solution is used as the“controller”and the gap between the lower bound and the upper bound is employed as the input to the“controller”. During the process of iterations, the gap between the lower bound and the upper bound is reduced gradually. So, the cardinality of the excluding arc set will be augmented which guarantees the algorithm’s self-convergence to the optimal solution. The mathematical programming and the heuristic method are integrated systematically. The superiority of the hybrid algorithm over a single method can be illustrated theoretically and the computational experiments verify the efficiency.(2)The HSM planning and scheduling problem is modeled as a multi-route and multi-objective problem (MRMOP). It differs from earlier work in the following two aspects: (i) the restriction of limiting the number of slabs processed consecutively with the same width within a single round is formulated as a resource constraint.(ii) by defining a hierarchical cost structure it is natural to decompose the MRMOP into several well-studied sub-problems. A mixed serial strategy is developed that combing mathematical programming and local heuristics. To solving a large-scale industrial problem, the strategy, from the viewpoint of finding sub-optimal solutions, first employ the mathematical programming to locate the most promising searching region and then let heuristics perform the further optimization or repair some infeasible solutions. Compared with some existing algorithms, not only can our method find a promising solution, but also it provides a tight lower bound to evaluate the found solution. Computational results are presented compared with several promising methods on practical data which demonstrate the efficiency of the proposed algorithm.(3)A time dependent traveling salesman problem (TDTSP) is modeled for the complex CGL scheduling problem in which the coupling effect between the machine and jobs is considered. A parallel hybrid algorithm framework with feedback and self-tuning mechanism is presented that simultaneously utilizes the lower bound and upper bound. Based on the framework presented in Charter 2, the subgradient algorithm is incorporated to utilize the information generated in the process of solving the dual problem of the relaxed primal problem in order to reduce the searching region. Further step, we also present the generalized form and its algorithmic implementation about how to reduce the solution component set without excluding the optimal solution. The process is very different from the typical way to handle the integer programming problem where only the best so far lower bound is used to obtain an optimal integer solution. For example, the best so far lower bound is commonly embedded in some upper-layer framework such as branch and bound algorithm if the solution corresponding to the lower bound is infeasible. Thus, plenty of information produced during solving the dual problem is discarded. The performance of the algorithm is degenerated due to the inefficient usage of the obtained information.In summary, the models and algorithms for the rolling batch scheduling problem, one of the key parts in the entire steel production, are well explored in the research. The achievements can provide theoretical and technical support for optimizing logistics in the steel production process and enhancing the efficiency and quality of production planning and scheduling. The work is supported by grants from National Natural Science Foundation of Chain (Grant No. 60574063) and City University of Hongkong (Grant No. CityU122305).更多还原