一种求解炼油厂连续时间调度模型的Lagrange分解算法

施磊; 江永亨; 王凌; 黄德先

doi:10.16511/j.cnki.qhdxxb.2016.24.016

PDF(1398 KB)

清华大学学报（自然科学版） ›› 2016, Vol. 56 ›› Issue (4) : 437-447. DOI: 10.16511/j.cnki.qhdxxb.2016.24.016

自动化

一种求解炼油厂连续时间调度模型的Lagrange分解算法

施磊, 江永亨, 王凌, 黄德先

作者信息 +

Lagrangian decomposition approach for solving continuous-time scheduling models of refinery production problems

SHI Lei, JIANG Yongheng, WANG Ling, HUANG Dexian

Author information +

文章历史 +

摘要

在炼油厂连续时间调度模型中,随着调度问题规模的增大,求解耗时会显著增长。该文提出了一种基于Lagrange分解的求解算法。根据炼油厂生产流程特点,将调度模型分解成9个子问题,并在子问题中加入辅助约束加快Lagrange乘子收敛。针对问题特点设计了乘子初始化方案、乘子迭代方案和对偶解可行化方法。案例仿真选用了3个具有不同调度周期和订单数量的案例进行仿真,结果表明:采用该文提出的算法能够显著提高模型的求解效率,算法求解时间与直接求解和普通Lagrange分解算法相比都要少,且随着问题规模的增大优势会更明显。从求解结果上看,算法能够得到原问题的最优解或者近似最优解。

Abstract

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.

导出引用

施磊, 江永亨, 王凌, 黄德先. 一种求解炼油厂连续时间调度模型的Lagrange分解算法[J]. 清华大学学报（自然科学版）. 2016, 56(4): 437-447 https://doi.org/10.16511/j.cnki.qhdxxb.2016.24.016

SHI Lei, JIANG Yongheng, WANG Ling, HUANG Dexian. Lagrangian decomposition approach for solving continuous-time scheduling models of refinery production problems[J]. Journal of Tsinghua University(Science and Technology). 2016, 56(4): 437-447 https://doi.org/10.16511/j.cnki.qhdxxb.2016.24.016

中图分类号： TP273

参考文献

[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.

PDF(1398 KB)

Accesses

Citation

Detail

段落导航

收稿日期	出版日期
2015-08-30	2016-04-15
发布日期
2016-04-15

选择文件类型/文献管理软件名称

选择包含的内容

摘要

Abstract

关键词

Key words

引用本文

{{custom_sec.title}}

{{custom_sec.title}}

参考文献

访问统计

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

摘要

Abstract

关键词

Key words

引用本文

{{custom_sec.title}}

{{custom_sec.title}}

参考文献

访问统计