在炼油厂连续时间调度模型中,随着调度问题规模的增大,求解耗时会显著增长。该文提出了一种基于Lagrange分解的求解算法。根据炼油厂生产流程特点,将调度模型分解成9个子问题,并在子问题中加入辅助约束加快Lagrange乘子收敛。针对问题特点设计了乘子初始化方案、乘子迭代方案和对偶解可行化方法。案例仿真选用了3个具有不同调度周期和订单数量的案例进行仿真,结果表明:采用该文提出的算法能够显著提高模型的求解效率,算法求解时间与直接求解和普通Lagrange分解算法相比都要少,且随着问题规模的增大优势会更明显。从求解结果上看,算法能够得到原问题的最优解或者近似最优解。
Continuous-time models need more computational effort to solve refinery production scheduling problems as the scheduling problem size increases. A new Lagrangian decomposition approach was used which divides the whole scheduling problem into nine subproblems. The convergence of Lagrange multipliers is accelerated by adding auxiliary constraints to the subproblems. This paper gives an initialization scheme for the Lagrange multipliers, a hybrid method to update the Lagrange multipliers and a heuristic algorithm to find feasible solutions. Computational results for three cases with different time horizons and different numbers of orders show that the Lagrangian scheme improves the computational efficiency and obtains optimal or near-optimal solutions.
[1] Pinto J M, Joly M, Moro L F L. Planning and scheduling models for refinery operations[J]. Computers & Chemical Engineering, 2000, 24(9-10), 2259-2276.
[2] Göthe-Lundgren M, Lundgren J T, Persson JA. An optimization model for refinery production scheduling[J]. International Journal of Production Economics, 2002, 78(3), 255-270.
[3] JIA Zhenya, Ierapetritou M. Efficient short-term scheduling of refinery operations based on a continuous time formulation[J]. Computers & Chemical Engineering, 2004, 28(6-7), 1001-1019.
[4] LUO Chunpeng, RONG Gang. Hierarchical approach for short-term scheduling in refineries[J]. Industrial & Engineering Chemistry Research, 2007, 46(11), 3656-3668.
[5] Mouret S, Grossmann I E, Pestiaux P. A new Lagrangian decomposition approach applied to the integration of refinery planning and crude-oil scheduling[J]. Computers & Chemical Engineering, 2011, 35(12), 2750-2766.
[6] CAO Cuiwen, GU Xingsheng, XIN Zhong. A data-driven rolling-horizon online scheduling model for diesel production of a real-world refinery[J]. AIChE Journal, 2013, 59(4), 1160-1174.
[7] Shah N K, LI Zukui, Ierapetritou M G. Petroleum refining operations:Key issues, advances, and opportunities[J]. Industrial & Engineering Chemistry Research, 2011, 50(3), 1161-1170.
[8] Joly M. Refinery production planning and scheduling:The refining core business[J]. Brazilian Journal of Chemical Engineering, 2012, 29(2), 371-384.
[9] SHI Lei, JIANG Yongheng, WANG Ling, et al. Refinery production scheduling involving operational transitions of mode switching under predictive control system[J]. Industrial & Engineering Chemistry Research, 2014, 53(19), 8155-8170.
[10] Terrazas-Moreno S, Trotter P A, Grossmann I E. Temporal and spatial Lagrange an decompositions in multi-site, multi-period production planning problems with sequence-dependent changeovers[J]. Computers & Chemical Engineering, 2011, 35, 2913-2928.
[11] Neiro S M, Pinto J M. Langrange an decomposition applied to multiperiod planning of petroleum refineries under uncertainty[J]. Latin American Applied Research, 2006, 36(4), 213-220.
[12] Shah N, Saharidis G, JIA Zhenya, et al. Centralized-decentralized optimization for refinery scheduling[J]. Computers & Chemical Engineering, 2009, 33(12):2091-2105.
[13] TANG Lixin, Luh P B, LIU Jiyin, et al. Steel-making process scheduling using Lagrangian relaxation[J]. International Journal of Production Research, 2002, 40(1), 55-70.
[14] LI Zukui, Ierapetritou M. Production planning and scheduling integration through augmented Lagrangian optimization[J]. Computers & Chemical Engineering, 2010, 34, 996-1006.
[15] JIANG Yongheng, Rodriguez M A, Harjunkoski I, et al. Optimal supply chain design and management over a multi-period horizon under demand uncertainty. Part Ⅱ:A Lagrangean decomposition algorithm[J]. Computers & Chemical Engineering, 2014, 62, 211-224.
[16] Knudsen B R, Grossmann I E, Foss B, et al. Lagrangian relaxation based decomposition for well scheduling in shale-gas systems[J]. Computers & Chemical Engineering, 2014, 63, 234-249.
[17] Held M, Karp R M. The traveling-salesman problem and minimum spanning trees:Part Ⅱ[J]. Mathematical Programming, 1971, 1(1):6-25.
[18] Held M, Wolfe P, Crowder H P. Validation of subgradient optimization[J]. Mathematical Programming, 1974, 6(1), 62-88.
[19] Cheney E W, Goldstein A A. Newton's method for convex programming and Tchebycheff approximation[J]. Numerische Mathematik, 1959, 1(1), 253-268.
[20] Kelley J J E. The cutting-plane method for solving convex programs[J]. Journal of the Society for Industrial & Applied Mathematics, 1960, 8(4), 703-712.
[21] Marsten R E, Hogan W W, Blankenship J W. The boxstep method for large-scale optimization[J]. Operations Research, 1975, 23(3), 389-405.
[22] Baker B M, Sheasby, J. Accelerating the convergence of subgradient optimization[J]. European Journal of Operational Research, 1999, 117, 136-144.
