A novel Lagrangian relaxation level approach for scheduling steelmaking-refining-continuous casting production

Abstract

A Lagrangian relaxation (LR) approach was presented which is with machine capacity relaxation and operation precedence relaxation for solving a flexible job shop (FJS) scheduling problem from the steelmaking-refining-continuous casting process. Unlike the full optimization of LR problems in traditional LR approaches, the machine capacity relaxation is optimized asymptotically, while the precedence relaxation is optimized approximately due to the NP-hard nature of its LR problem. Because the standard subgradient algorithm (SSA) cannot solve the Lagrangian dual (LD) problem within the partial optimization of LR problem, an effective deflected-conditional approximate subgradient level algorithm (DCASLA) was developed, named as Lagrangian relaxation level approach. The efficiency of the DCASLA is enhanced by a deflected-conditional epsilon-subgradient to weaken the possible zigzagging phenomena. Computational results and comparisons show that the proposed methods improve significantly the efficiency of the LR approach and the DCASLA adopting capacity relaxation strategy performs best among eight methods in terms of solution quality and running time.

Keywords

steelmaking-refining-continuous casting / Lagrangian relaxation (LR) / approximate subgradient optimization

References

[1] TangL-x, WangG-shu. Decision support system for the batching problems of steelmaking and continuous-casting production [J]. Omega-International Journal of Management Science, 2008, 36(6): 976-991

[2] PacciarelliD, PranzoM. Prodution scheduling in a steelmaking-continuous casting plant [J]. Computers and Chemical Engineering, 2004, 28(12): 2823-2835

[3] BellabdaouiA, TeghemJ. A mixed-integer linear programming model for the continuous casting planning [J]. International Journal of Production Economics, 2006, 104(2): 260-270

[4] KumarV, KumarS, ChanF T S, TiwariM K. Auction-based approach to resolve the scheduling problem in the steelmaking process [J]. International Journal of Production Research, 2006, 44(8): 1503-1522

[5] MissbauerH, HauberbW, StadlerW. A scheduling system for the steelmaking-continuous casting process: A case study from the steelmaking industry [J]. International Journal of Production Research, 2009, 47(15): 4147-4172

[6] AtighehchianA, BijariM, TarkeshH. A novel hybrid algorithm for scheduling steelmaking continuous casting production [J]. Computers & Operations Research, 2009, 36(8): 2450-2461

[7] PangQ-k, WangL, MaoK, ZhaoJ-h, ZhangMin. An effective artificial bee colony algorithm for a real-world hybrid flowshop problem in Steelmaking process [J]. IEEE Transactions on Automation Science and Engineering, 2013, 10(2): 307-322

[8] TanY-y, HangY-l, LiuS-xin. Two-stage mathematical programming approach for steelmaking process scheduling under variable electricity price [J]. International Journal of Iron and Steel Research, 2013, 27(7): 1-8

[9] YeY, LiJ, LiZ-k, TangQ-h, XaoX C A. Floudas. Robust optimization and stochastic programming approaches for medium-term production scheduling of a large-scale steelmaking continuous casting process under demand uncertainty [J]. Computer and Chemical Engineering, 2014, 66: 165-185

[10] MaoK, PanQ-k, PangX-f, ChaiT-you. A novel Lagrangian relaxation approach for the hybrid flowshop scheduling problem in a steelmaking-continuous casting process [J]. European Journal of Operational Research, 2014, 236(1): 51-60

[11] HaoJ-h, LiuM, JiangS-l, WuCheng. A soft-decision based two-layered scheduling approach for uncertain steelmaking-continuous casting process [J]. European Journal of Operational Research, 2015, 244(3): 966-979

[12] WangG-r, LiQ-q, WangL-hao. An improved cross entropy algorithm for steelmaking-continuous casting production scheduling with complicated technological routes [J]. Journal of Central South University, 2015, 22(8): 2998-3007

[13] HmidaA B, HaouariM, HuguetM J, LopezP. Discrepancy search for the flexible job shop scheduling problem [J]. Computers and Operations Research, 2010, 37(12): 2192-2201

[14] ChenH, ChuC, ProthJ M. An improvement of the Lagrangian relaxation approach for job shop scheduling: a dynamic programming method [J]. IEEE Transactions on Robotics and Automation, 1998, 14(5): 786-795

[15] ChenH, LuhP B. An alternative framework to Lagrangian relaxation approach for job shop scheduling [J]. European Journal of Operational Research, 2003, 149(3): 499-512

[16] NishiT, HiranakaY, InuiguchiM. Lagrangian relaxation with cut generation for hybrid flowshop scheduling problems to minimize the total weighted tardiness [J]. Computers & Operations Research, 2010, 37(1): 189-198

[17] TangL-x, LuhP, LiuJ-y, FangLei. Steelmaking process scheduling using Lagrangian relaxation [J]. International Journal of Production Research, 2002, 40(1): 55-70

[18] XuanH, TangL-xin. Scheduling a hybrid flowshop with batch production at the last stage [J]. Computers & Operations Research, 2007, 34(9): 2718-2733

[19] TangL-x, XuanH, LiuJ-yin. A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time [J]. Computers & Operations Research, 2006, 33(11): 3344-3359

[20] BrunoJ, GoffmanE, SethiR. Scheduling independent tasks to reduce mean finishing time [J]. Communications of the ACM, 1974, 17(7): 382-387

[21] LenstraJ K, KanAHG, BrukerP. Complexity of machine scheduling problems [J]. Annals of Discrete Mathematics, 1977, 7(1): 343-362

[22] KawaguchiT, KyanS. Worst case bound of an LRF schedule for the mean weighted flow time problem [J]. SIAM Journal of Computing, 1986, 15(4): 1119-1129

[23] GutaBSubgradient optimization methods in integer programming with an application to a radiation therapy problem [D], 2003

[24] WangJ-hua, LuhP B, ZhaoXing. An optimization-based algorithm for job shop scheduling [J]. Sadhana, 1997, 22(2): 241-256

[25] CameriniP M, FrattaL, MaffioliF. On improving relaxation methods by modified gradient techniques [J]. Mathematical Programming Study, 1975, 3: 26-34

[26] BrannlundUOn relaxation methods for nonsmooth convex optimization [D], 1993

[27] GoffinJ L, KiwielK C. Convergence of a simple subgradient level method [J]. Mathematical Programming, 1999, 85(1): 207-211

[28] D'antonioG, FrangioniA. Convergence analysis of deflected-conditional approximate subgradient methods [J]. SIAM Journal on Optimization, 2009, 20(1): 357-386

[29] ZhaoX, LuhP B, WangJ-hua. Surrogate gradient algorithm for Lagrangian relaxation [J]. Journal of Optimization Theory and Applications, 1999, 100(3): 699-712

[30] MijangosE. Approximate subgradient methods for nonlinearly constrained network flow problems [J]. Journal of Optimization Theory and Applications, 2006, 128(1): 167-190