Lagrange Relaxation Level Optimization Method And Its Application To Production Scheduling Of The Steelmaking-Continuous Casting Process

Efficient optimization methods are vital for the industrial production scheduling. However, according to the computational complexity theory, most production scheduling problems are strongly NP-hard, which implies that the global optimization methods cannot be directly applied to the complicated practical production scheduling problems. Using the separable structure of scheduling problems and adopting the decomposition and coordination strategies, Lagrange relaxation (LR) approach can obtain high quality solutions within acceptable time and provide the lower bounds of the minimization problems to evaluate the quality of the solution. Therefore, the LR approach is generally recognized as a favorable alternative to deal with the complicated scheduling problems.The LR approach first applies the Lagrangian multipliers to relax the coupled constraints, which cause the problem difficult to solve, and then obtains a Lagrange relaxation problem corresponding to the given multipliers by introducing these constraints to the objective function. The optimal multipliers are obtained by optimizing the Lagrange dual (LD) problem with the subgradient algorithms. The optimal dual value is the lower bound of the primal minimization problems. The subgradient, used to update the multiplier, is obtained by optimizing the relaxed problem per iteration in the subgradient algorithms. Based on the solution of the relaxed problem, a feasible solution is obtained by a heuristic. There are three drawbacks in the LR approach:the empirical termination criterion caused by the strict convergence condition which make the approach cannot obtain optimal dual value, the low efficiency of the subgradient algorithm caused by the zigzagging phenomenon and the low efficiency of the LR approach caused by fully optimizing the relaxed per iteration. To overcome the above drawbacks, we study these problems in theory and propose a Lagrange relaxation level method. Then, we applied the proposed approach to the steelmaking-continuous casting (SCC) scheduling problem. The main contributions of this thesis are as follows.1. To overcome the unrealizable convergence condition of the traditional subgradient algorithm, we introduce the Brannlund’s level control strategy to provide a practical termination criterion without knowing the information of the problem such as the distance between the initial iterative point and the optimal point, which provide a realizable termination criterion. Hence, the improved strategies improve not only the practicality of the LR approach but also the exactness of evaluating the quality of the solution. Then, we propose a subgradient level algorithm and a LR approach based on this algorithm. In addition, the proof of the convergence and convergent rate of the proposed algorithm is also presented.This thesis applies the Lagrange relaxation approach based on the subgradient level algorithm strategy to a SCC scheduling problem. Since the efficiency and effectiveness of the LR approach depends on the formulation of the scheduling problem, based on the relaxation of machine capacity constraints corresponding to the steelmaking and refining stages (multiple charges cannot be processed on the same machine at the same time), we study the SCC scheduling problem with two modeling methods. First, a mixed integer programming (MIP) model is established based on the big-M method. To address the unbounded case of the solution of the relaxed problem in the MIP-based method, a necessary and sufficient condition of boundedness for the relaxed problem is proposed and the method to deal with the unboundedness is presented. Second, a 0-1 integer programming (IP) model is established based on the time-index variables. Considering the characteristic of the continuous casting, three relaxation strategies including job-level, batch level and machine-level are proposed and the corresponding polynomial dynamic programming method to solve the relaxed problem are presented. Numerical experiments based on the practical datas from the steel production showed that the methods based on the IP model perform better the method based on the MIP model. Moreover, among the methods based on the IP model, the method based on the machine-level relaxation has the best solution quality, whereas the method based on the job-level relaxation is the most efficient.,2. To overcome the low convergent rate of the subgradient algorithm caused by the traditional subgradient, we first analyze two kinds of zigzagging phenomena and introduce deflected-conditional subgradient to weak the zigzagging. Based on the subgradient level algorithm, a deflected-conditional subgradient level (DCSL) algorithm and the corresponding LR method are proposed. The proof and analysis of the convergence and convergent rate of the proposed algorithm are also presented. The numerical experiments based on the classical problems showed that the the effficiecny of the LR approach is significantly improved by the DCSL algorithm.To deal with the flexible-job-shop (FJS) type SCC scheduling problem, where the refining orders of all charges are not the same, we first establish a 0-1 integer-programming model for the scheduling problem based on the time-index formulation. By using the relaxation strategies of machine capacity constraints corresponding to the steelmaking and refining stages, a LR approach based on the DCSL algorithm for the scheduling problem is proposed. Numerical experiments based on the practical datas from the steel production showed that the DCSL algorithm significantly improves the efficiency of the LR approach for the scheduling problem.3. To overcome the low efficiency caused by the exact optimization of the relaxed problem per iteration in the subgradient algorithm, we introduce the approximate subgradient to approximately optimize the relaxed problem. Furthermore, the deflected-conditional approximate subgradient is proposed by combining the approximate subgradient and deflected-conditional subgradient. Based on the subgradient level algorithm, the deflected-conditional approximate subgradient level (DCASL) algorithm is proposed. The LR approach based on the DCASL algorithm is called Lagrange relaxation level (LRL) approach. The proof of convergence and convergent rate of the DCASL algorithm is presented. The theoretical analysis illustrates the relationship between the approximate error of the relaxed problem and the optimal dual value, which is the foundation for evaluating the solution quality.The LRL approach is applied to address the FJS-type SCC rescheduling problem. Based on the time-index variables, we first establish a mixed integer-programming model for the rescheduling problem with respect to different disturbances. Then, the charge-level and machine-level decomposition strategies based on the relaxation of the machine capacities are proposed. The polynomial dynamic programming algorithms are presented to solve the corresponding relaxed problems with variable processing times. Based on the above approaches, an approximate optimization method with controllable errors is proposed to solve the relaxed problem. Numerical experiments based on the practical datas from the steel production showed that the differences of the solution qualities between the method based on the charge-level decomposition strategy and the method based on the machine-level decomposition strategy is tiny. However, the efficiency of the former is slightly better than that of the latter. Moreover, the numerical experiments based on different levels of errors showed that the efficiency of the LRL approach is significantly improved by the DCASL algorithm.