Research Of Modeling And Optimization Method Of Family Scheduling In Rolling Area

Iron&Steel production processes can be divided into three areas:iron-making area, steel-making area and rolling area. The production processes in rolling area are characterized by sending materials into the production line discretely, high processing temperature in some production line, large family setup cost and processing materials in serially families. The production scheduling problem with consideration of family production mode is called family scheduling which determines the composition and construction of each family, assignment, sequence and schedule of the familes. It belongs to combinatorial optimization problem with complex constraints. The research on modeling and optimization methods for the problem has signficant meaning for adequently untilizing the capacity of the production line, improving production efficiency and product quanlity and reducing the energy consumption.Rolling area in iron&steel industry covers the production stages including hot rolling, acid-rolling, continuous annealing, electro-galvanizing and color coating etc. This paper derives the following family scheduling problems from different production stages in rolling area: slab scheduling problem in parallel hot rolling lines, coil sequencing problem in continuous annealing line, coil scheduling problem with family setup in continuous annealing line, coil sequencing problem in electro-galvanizing line, coil sequencing problem in color coating line, coil scheduling problem in rolling area. For each of the above problems, mathematical programming model is formulated. Based on the characteristics of the problem, polynomial optimization algorithm based on dynamic programming, column generation based algorithm, metaheuristic optimization algorithms based on tabu search (TS) and filter&fan (F&F) are proposed. Finally, the decision support system for production scheduling in continuous annealing line is developed. The contents of the dissertation are summarized as follows.(1) Taking hot rolling production stage as background, slab scheduling problem in parallel hot rolling lines has been studied. With given rolling families (slab chain precedence constraints), the problem is to assign the families to hot rolling lines and determine the schedule of the families on each hot rolling line in order to minimize the total energy loss costs incurred by that the hot slabs wait before the production line. The problem is characterized by slab chain precedence constraints, dynamic arrival of slabs and considering energy loss in objective function. Based on the above characteristicses, the problem is reduced to Pchains,rjk,hot|Σfjk(waitjk) for the case that the energey loss is linearly dependent of waiting time of slabs. Considering that the problem is strongly NP-hard, a branch-and-pricing algorithm is proposed. During the procedure for finding the lower bound, since the pricing problem is still intractable, dynamic programming algorithm based on state-space relaxation is developed which improves the efficiency for solving the pricing problem. To make that the algorithm can be used for all the cases of this problem, the algorithm is further extended to the complex case that the energey loss is non-linearly dependent of waiting time of slabs. For both linear and non-linear energy loss functions, the computational results demonstrate that the algorithm can find out the optimal solution for medium-scale problem in reasonable time.(2) Taking continuous annealing production line as background, coil sequencing problem on continuous annealing line have been studied which determines the processing sequence of the coils on a continuous annealing line. The problem is characterized by considering the switches with respect to annealing temperature, width and thickness between two adjacent coils and the switching trend with respect to annealing temperature, width and thickness depending of three adjacent coils. By reducing the problem to a generalization of traveling salesman problem, a mathematical programming model is formulated. Considering that the problem is intractable, tabu search algorithm is developed to find the near optimal solution of the problem. To further improve the performance of the algorithm and help earching procedure escaping local optima, kick strategy based on alternate exchange neighborhood is proposed, and a polynomial dynamic programming recursion is constructed to search the neighborhood. Computational results based on practical data demonstrate that the proposed algorithm based on tabu search can solve the industrial size instances efficiently in reasonable time. (3) Taking continuous annealing production line as background, coil scheduling problem with family setup on continuous annealing line have been studied which determines batches of coils and batch sequence simultaneously with given coil clusters. The problem is characterized by processing the coils with given clusters, larger setup time and setup cost between different clusters and minor changeover cost between two adjacent coils in a cluster. With the objective of minimizing total adjustment cost and earliness-tardiness penalties, an integral linear programming model is formulated, and an algorithm combining tabu search and filter-and-fan strategy is proposed where tabu search is used to generate initial solution and candidate moves, filter-and-fan strategy is used to choose better compound moves from the candidate moves. By comparing the results of algorithm and CPLEX solver, the efficiency of the proposed algorithm is verified.(4) Taking electro-galvanizing line as background, coil sequencing problem in electro-galvanizing line have been studied. The problem is to determine coil processing sequence with the objective of minimizing total switching cost while satisfying practical production restrictions such as processing the coils with same post-processing requirement from wide to narrow. For the problem, an integral linear programming model is set up. Based on the analysis for the construction of the optimal solution and the propery of the problem, two-phase polynomial algorithm whose complexity is O(nk3) is developed to solve the problem optimally. In the first phase, the optimal sequence of coils in a cluster is determined with given boundary coils. Then a polynomial algorithm is proposed to solve the coil sequencing problem in cluster optimally. In the second phase, the sequence of the clusters is determined. Then another polynomial DP-based algorithm which takes the boundary coils as state variables is proposed to solve the cluster sequencing problem optimally in polynomial time. To satisfy the dynamic real-time requirement of some cases, a heuristic algorithm is constructed. By computation experiments, it is found that the two-phase algorithm can obtain optimal solution in shorter time than CPLEX and the heuristic can get near-optimal solution very quickly.(5) Taking color-coating line as background, single-turn coil sequencing problem and multi--turn coil sequencing problem have been studied. While satisfying the practical production restrictions, these two problems determine the selection of the coils from the candidate coils, and the sequence of the selected coils with minimized switching cost in a turn and in multiple turns, respectively. The problem is characterized by limited production capacity between two times of roller replacements in the color-coating line, processing the coils in cluster, practical restrictions with respect to width, thickness and color switches and considering both product coils and transition coils. The single-turn coil sequencing problem is reduced to prize-collecting traveling salesman problem with capacity constraints. Since sequencing and selecting are related in the single-turn coil sequencing problem, dominance rules are proposed which reduce the difficulty of sequencing efficiently, and a pseudo-polynomal dynamic programming algorithm is constructed to make the optimal coil selecting decision based on given coil sequence. Multi-turn coil sequencing problem is reduced to prize-collecting vehicle routing problem. The problem is intractable due to considering multiple turns simultaneously, thus tabu search based algorithm is proposed to solve the problem. To avoid searching single neighborhood trapping in local optima, composite neighbourhoods involving block moves are proposed. To evaluate the performance of the TS algorithm, the lower bound is constructed using column generation algorithm. From the computation results based on randomly generated instances, the proposed TS algorithm can find near-optimal solution quickly, and the column generation algorithm can find out tighter lower bound.(6) Taking acid-rolling stage which has unrelated parallel production lines as background, coil scheduling problem in rolling area have been studied. The problem is to assign the coils to unrelated parallel line and sequence the coils on each line which is characterized by considering unrelated parallel production lines and considering two objectives of minimizing the total completion time and minimizing the total tardiness. Based on the characteristicses of the problem, a mathematical programming model is formulated. Considering the property of multiple objectives, local search method based on ideal point methods is proposed. With consideration of minimizing total completion time, a linear programming formulation is set up, and then the ideal point can be obtained by standard LP solver. With consideration of minimizing total tardiness, heuristic based on local search is proposed to solve the problem. Combining the above results, the ideal point corresponding to the objective of minimizing total completion time is set as the upper bound which reduces the searching range of the multiple objectives problem, and the multiple objectives are converted to a single objective evaluating how close the solution is to the ideal points. Then, a local search heuristic is proposed to find pareto-solution of the primal problem. Computational results indicate that the proposed algorithm can find satisfactory solutions in reasonable time.(7) Considering the common scheduling features in different rolling areas, a coil sequencing decision supported system is developed, which takes the typical production line in rolling area-continuous annealing line as background, and uses the algorithm for coil sequencing problem in continuous annealing line as core. By experiments based on practical data, it is verified that the coil sequencing problem can be solved efficiently using the system.