The Optimization Algorithm With Feedback And Self-Tuning Mechanism Applications In The Rolling Batch Scheduling Problem

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