Study On Optimization-based Methods For Batching Planning And Scheduling Problems In The Metallurgical Industry

The metallurgical industry is an important industry for providing raw material, and also is an essential sector for national economy. The production planning and scheduling is one of the key sections of production operation management in metallurgical industry. The rational and efficient production planning and scheduling can help the enterprise improve productivity, reduce production cost, improve product quality and ensure production system operating under optimal condition. Therefore, it becomes a research focuse in both the academic and industrial society to research on the modeling and optimization methods for the production planning and scheduling problem in the metallurgical industry.This dissertation takes ferrous metal steel production and nonferrous metal aluminium production as the background, and makes theoretical studies on the modeling and optimization methods respectively for the metallurgical production batch planning, the production scheduling with various metallurgical characteristics, and the integrated batching and scheduling. This research is beneficial to optimize metallurgical enterprise’s rational resource allocation, reduce the energy consumption, improve the equipment operating rate, increase production efficiency, improve customers’ service level, thus improve the metallurgical enterprise’s core competitiveness. The main contents include:1) The batching planning problemIn the iron and steel enterprise, batching planning is to compose customers’ demand with multiple varieties and small lot into production batch. While meeting the diverse requirements of customers, the enterprise organizes production in batch mode to achieve the purpose of economic operation. The batching planning at the steelmaking stage is called charge plan. It is a decision making process which combines orders of diverse customers demand into charge (the basic production unit of steelmaking intermittent equipment) according to steel grade and specification. This dissertation investigates the charge batching planning problem (CBP) arising from practical steelmaking production. By considering the steelmaking production constraints and composition batch conditions, a novel mixed integer programming model for the CBP is presented, and two kinds of Lagrangian relaxation (LR) methods are proposed to solve the CBP by using different relaxation methods. In the first LR method, the relaxed problem obtained by relaxing the assignment constraints is separated into subproblems which are solved optimally by dynamic programming. In the second method, variable splitting is adopted in the Lagrangian relaxation method. The computational results on randomly generated instances show that both LR methods can produce a satisfactory average duality gap and the variable splitting based LR method is a little better than the first method.2) The production scheduling problem(1) Single machine scheduling problem with release timesFor a single machine scheduling problem with release times, a mixed integer linear programming model is established based on slot idea. Using the continuous time modeling, the original problem becomes an allocation and timetable decision problem where the main decision is the assignment of the time slot to each job and the starting time of each slot. The Lagrangian relaxation method is desgined by relaxing release time constraints and precedence constraints. The relaxed problem is decomposed into two subproblems. One subproblem can be optimally solved by checking variable coefficients, while another subproblem can be reduced to assignment problems which can be optimally solved by Hungarian algorithm. The computational results show that the upper bounds obtained by the Lagrangian-based heuristic are close to the optimal objective function value obtained by CPLEX.(2) Single machine scheduling problem with deteriorating jobsIn the iron and steel producton, high-temperature job waiting before processing will cause temperature drop. Re-heating this job to meet the temperature requirements will inevitably lead to increase in job’s processing time. The characteristic that job processing time is dependent on its starting time or waiting time is known as deterioration. For the single machine scheduling problem with release times and deteriorating jobs, a mixed integer programming is proposed. The Lagrangian Relaxation algorithm is designed to solve the problem approximatly. In the implementing LR, the relaxed problem is decomposed into job-level subproblems by relaxing machine capacity constraints. A shorten time horizon strategy is derived to speed-up implementing algorithm of Lagrangian relaxation. Computational results on randomly generated instances with different parameter settings show that the average duality gap of the proposed algorithm is1.28%and the average running time of the proposed algorithm is20.89second. Therefore we can conclude that the proposed algorithm can obtain near optimal solutions in a relatively short computational time. (3) Re-entrant hybrid flowshop scheduling problemIn the cold rolling stage of aluminium production, aluminium coils usually require processing several times at the cold rolling operation (repeated processing at the same operation) to achieve the surface quality and mechanical performance of the technological requirements. This characteristic is called re-entrant. For a re-entrant hybrid flowshop scheduling problem, a mixed integer programming is presented and a Lagrangian relaxation algorithm is proposed. To overcome the shortcoming that low efficiency of the regular Lagrangian relaxation algorithm caused by minimizing all subproblems at each iteration, a surrogate subgradient based Lagrangian relaxation algorithm is proposed. The advantage of this method is that only one job-level subproblem obtained by relaxing the capacity constraints is minimized at each iteration. Computational results show that the proposed algorithm can effectively solve the small size problems in a relatively short time.(4) Dynamic parallel scheduling problem with release timesIn the steelmaking stage of iron and steel enterprise, since the production environment in reality is often influenced by various uncertainties or random factor, static production scheduling must be adjusted to adapt to changing demand of the dynamic environment. For a dynamic parallel machine scheduling problem with variable job release time and processing time, a mixed integer programming model in a rolling horizon is established based on model predictive control principle. The formulation takes into account the total weighted completion times of jobs, the energy consumption, and the total deviation of actual job completion times from those in the original schedule. The Lagrangian relaxation algorithm is designed to solve the scheduling subproblem during each rolling window. The computational results on randomly generated instances are carried out to compare the proposed method based on model predictive control based rolling horizon modeling and the Lagrangian relaxation algorithm with the passive adjustment method often adopted by human schedulers. The result shows that the proposed method yields significantly better results, with11.72%improvement on average.3) Batching planning and scheduling problem(1) Parallel machine batch scheduling problem with deteriorating jobsIn the hot rolling production stage, slabs need to be processed in batches in order to reduce setup costs. If the slab in batch needs to be waiting before rolling, it will cause temperature drop. When the temperature is below the entrance temperature of rolling, the slab must be re-heated, which leads to increase in processing time. In this paper, the properties of the optimal solution are derived for the parallel machine batch scheduling problem with deteriorating jobs. Based on the solution properties, an improved scatter search algorithm is proposed for solving the problem. In order to evaluate the performance of the proposed algorithm, a lower bound on the optimal objective function is developed through Lagrangian relaxation. Computational results on randomly generated instances with different parameter settings show that the proposed algorithm can obtain solutions whose average deviation over the lower bounds is within2%.(2) Integrated batching and scheduling for Aluminium ingot productionFrom the two-stage aluminium ingot production system consisting of a smelting stage and a casting stage, a class of integrated batching and scheduling problems are extracted. The characteristic of the problem is that the batch composition, batch size, batch allocation, batch sequencing and time schedules must be determined simultaneously. A mixed integer linear programming model is established for the integrated batching and scheduling problem of the aluminium ingot production. Since the integrated model is hard to solve, we develop two heuristics based on the stage-decomposition strategy and level-decomposition strategy respectively. Computational results show that the proposed two heuristics can get better results in relatively short time compared to MILP formulation solved by CPLEX, and the heuristic based on level-decomposition strategy is a litter better than the heuristic based on stage-decomposition strategy.