| Rolling area in iron&steel industry covers hot rolling and pickling-rolling production stages and is an important process to produce hot rolling crude steel and further processed steel with high value-added and high quality. The management of the operations will affect on the operation cost. The production time scheduling and logistics space scheduling are kinds of key problems of the operation management for iron and steel companies. The production time scheduling is to determine the production sequence of jobs (slabs or coils) on production lines, while logistics space scheduling is to decide the storage space of items (slabs or coils) in warehouses before the production lines. The rational and efficient production time scheduling and logistics space scheduling can help the enterprise improve productivity, decrease work-in-process inventory, cut down material consumption, reduce production and logistics cost, improve product quality. Therefore, the research on modeling and optimization methods for the production time scheduling and logistics space scheduling problems has signficant meaning for improving the operation management.This dissertation abstracts a serial of novel production time scheduling and logistics space scheduling problems with new features from hot rolling and pickling-rolling production stages in rolling area. These problems include:pickling-rolling production time scheduling problem, hot rolling production time scheduling problem with considering slab logistics operation cost, coil shuffling logistics space scheduling problem, slab shuffling logistics space scheduling problem, and the integrated pickling-rolling/hot rolling production time scheduling and coil shuffling logistics space scheduling problems. For above problems, mathematical programming models are formulated, and valid inequalities are constructed based on the structures of feasible solutions. In aspect of academic studies, optimal solution properties are analyzed and polynomial optimization algorithms are proposed for some special cases; for some strongely NP-hard problems, heuristic algorithms are constructed and their worst-case performance ratios are analyzed. In aspect of practical application, intelligent optimization algorithms are proposed and decision support systems are developed. The main contents include:1) Production time scheduling problems in rolling area(1) Pickling-rolling production time scheduling problemTaking practical pickling rolling production stage as background, pickling-rolling production time scheduling problem has been refined. Different from making pickling and rolling production time schedules separately, it needs to consider both pickling and rolling practical prodution tecnological constraints to make a production time schedule. The problem is to selecte and sequence coils considering the changeovers cost between adjacent coils. Besides the capacity constraint and practical prodution tecnological constraints, the flow requirement constraint is considered such that the total weight of the selected coils over respective downstream unit should satisfy the production requirement on each downstream unit. The objective is to minimize the total transition cost and the penaty cost on the left capacity. The problem is formulated as an integer programming model. A new tabu search with the enhanced dynasearch algorithm is developed for the PPSP. The two-phase heuristic based on Nearest Insert method is proposed to act the initial feasible solutions to the tabu search. The algorithm designs double tabu lists to fit the different neighborhood structure. In order to help the solution escape from the local optima, the enhanced dynasearch neighborhood is embeded in each iteration. The dynasearch neighborhood which is polynomially searchable by dynamic programming can perform the multiple-exchange composite move by combining swap neighborhood and inner-insert neighborhood. Based on the analysis of the characteristics of the problem, block structure is defined and several properties of the feasible solution are direved to accelerate the search process. Compared with the standard TS algorithm, the computational results show that the enhanced-dynsearch&TS algorithm is effective for solving the problem and outperforms the standard one by3.62%on average. Based on the model and the proposed enhanced-dynsearch&TS algorithm, a decision support system is developed.(2) Hot rolling production time scheduling problem with considering slab logistics operation costTaking hot rolling production stage as background, hot rolling production time scheduling problem with considering slab logistics operation cost has been studied, which determines the processing sequence of required slabs on a hot rolling line. Different from the existing published papers on hot rolling production time scheduling problems, our problem is characterized by considering the number of shuffles arising from the required slabs loading as well as practical prodution tecnological constraints. The objective is to minimize the total production transition cost and shuffling logisics cost related with processing sequence. The problem is formulated as a linear integer programming model in which the relationship between shuffle number and processing sequence is formulated linearly. For simplified problem, dynamic programming based heuristic algorithm is proposed and its worst-case performance is analyzed. For the general problem, based on some optimal properties derived, dynasearch based heuristic algorithms is presented. In order to further improve solutions obtained by dynasearch, this paper designs an iterated local search algorithm where tabu, backtrace and kick strategies are embedded. The computational results on practical production data with partly randomly generated show that proposed ILS algorithm is better than normal ILS algorithm by3.7%; compared with classical hot rolling production time scheduling problem without considering slab logistics operation cost, the proposed model and ILS algorithm can reduce the total cost effectively by12.89%,2) Item shuffling logistics space scheduling problems in rolling area(1) Coil shuffling logistics space scheduling problemTaking the logistics operations in coil warehouse as background, coil shuffling logistics space scheduling problem is refined. Required coils are retrieved according to the given sequence. Shuffling occurrs if a required coil is blocked by other coils. The problem studied in this paper is to decide the shuffling order and assign shuffled coils to suitable storage space for retrieving a given sequence of the required coils so that the total number of shuffles and the overall crane traveling distances are minimized. Based on the definition of "inclined stack" proposed in this paper, a novel linear integer programming model is formulated through considering the practical storing and retrieving features. Several families of valid inequalities are constructed to reduce the size of model. Some properties of optimal solutions are derived. Two special cases are demonstrated to be solved optimally in polynomial time, respectively. For general case, a heuristics CH is proposed and its worst-case is analyzed. A tabu search algorithm with variable length of tabu list is proposed to further improve the heuristic solutions. Numerical runs show the proposed heuristic algorithms are effective and TS algorithm can improve the solution obtained by heuristics CH by21.43%. For the requirements in practice, a decision support system is developed based on the proposed model and heuristic algorithms.(2) Slab shuffling logistics space scheduling problemTaking the logistics system in slab warehouse as background, slab shuffling logistics space scheduling problem is refined. The problem is to assign shuffled slabs to suitable storage positions with considering practical stacking and shuffling constraints, according to the given retrieving sequence of the required slabs. Because of different shapes between slabs and coils, slab is stacked one on top of another. Different from coil shuffling logistics space scheduling problem, the features of this problem include:1) Slabs are stacked one on top of another, and each stack can store several slabs but can not exceed its maximum height;2) Relative height constraint needs to be additionally considered if shuffling occurs;3) The shuffling order of shuffled slabs of a required slab is confirmed by their priority relationship. A linear integer programming model is formulated with the objective being to minimize the total number of shuffles and the overall crane traveling distances. Several families of valid inequalities are constructed to reduce searching time. Four special cases are studied, where for three among them three polynomial time algorithms are proposed to obtain the optimal solutions respectively, and an (1-1/e)-approximation algorithm is presented for the other special case. For general case, a lower bound on the optimal solutions is obtained by constructed heuristics LBH, and a heuristics SH is proposed and its worst-case performance is analyzed. Numerical runs show the proposed heuristic algorithm is effective and makes great improvement over the current heuristics used in a real slab yard by13.46%.3) The integration of production time scheduling and shuffling logistics space schedulingThe published literatures related to production time scheduling or logistics space scheduling problem focus on optimizing independently without considering the relationship between production stage and logistics stages serving production in material warehouse before production line, so that it is hard to optimize the production and the logistics schedules synchronously. Therefore, this dissertation proposes an optimizing strategy which integrates the production time scheduling and shuffling logistics space scheduling. Using this strategy. the processing sequence and the assignment of storage space to shuffled items can be obtained simultaneously. Taking the hot rolling and pickling rolling stages as the background, this dissertation studies two different kinds of problems. In the first problem, candidate items are all the required items and need to be processed in production line. On the contrary, in the second problem not all candidate items need to be processed and required items are a part of candidate items and need to be selected from candidate items.(1) The integration of pickling-rolling production time scheduling and coil shuffling logistics space schedulingThe scheduling objects of this problem are given required coils stored in coil warehouse before pickling-rolling production line. The task of this problem is to determine the processing sequence of required coils and shuffling orders of shuffled coils, as well as assign the shuffled coils to storage space during implementing required coils retrieving so that the total transition cost and the number of shuffles are minimized. According the features of this problem, the integrated problem can be divided into two sub-problems. The first stage sub-problem is to decide the processing sequence of required coils with considering practical prodution tecnological constraints and the relationship between shuffle numbers and processing sequence. The seconde stage sub-problem is to determine the shuffling orders of and the assignment of shuffled coils with considering coil storing and retrieving constraints. For both sub-problems, linear integer programming models are formulated respectively. Some analytical properties are provided. Based on these properties, some families of valid inequalities are constructed to add into the first stage sub-problem model to reduce the solution space. Furthermore, through introducing a adjusting variables to the first stage sub-problem, above two models can be combined so that a model-based heuristic algorithm is proposed for small size instances. In order to adapt the practical size instances, a tabu search based algorithm with variable neighborhoods is proposed for solving the problem. From the computational results based on randomly generated instances, the proposed algorithms can effectively reduce the total production and shuffling logistics cost resepectively by4.06%, compared to optimize independently.(2) The integration of hot rolling production time scheduling and slab shuffling logistics space schedulingThe scheduling objects of this problem are candidate slabs stacked in slabs yard before hot rolling line. The task of this problem is to select and sequence the required slabs from candidate slabs to construct a rolling turn, as well as assign the shuffled slabs to storage space during implementing required slabs retrieving. Using the new modeling strategy, the problem is formulated as a novel linear integer programming model where the hot rolling production tecnological constraints, slab stacking constraints and slab shuffling constraints are all considered, objective being to minimize the total transition cost and shuffling number and maximize the production load in a turn. Since this problem is a large scale combinatorial optimization problem that includes many complex practical constraints, it is very difficult to solve this problem. Therefore, a TS&FF hybrid algorithm is proposed based on the characteristics of this problem. Two-stage heuristic algorithm is presented to obtain an initial solution. According to the features of our problem, many kinds of moves are developed to construct neighborhoods. In order to help the solution escape from the local optima and decrease the neighborhood size, branch-memory and tree memory are introduced into Fiter-and-Fan searching. The computational results using practical production data with partly randomly generated show that the proposed TS&FF algorithm outperforms the simulated manual scheduling method by23%, and can be effectively reduce the total production and shuffling logistics cost by5.3%compared with the classical optimize independently. Based on the model and the proposed TS&FF algorithm, a decision support system is developed. |
PDF Full Text Request