Search / Korean Journal of Chemical Engineering
HWAHAK KONGHAK,
Vol.36, No.4, 618-625, 1998
Benders 분해법을 이용한 스케쥴링 및 강건한 생산계획
Batch Scheduling and Robust Production Planning using Benders Decomposition
본 연구에서는 화학공정에 관련된 의사결정 문제에서 계산의 효율성을 높이고자 benders 분해법을 이용한 모델을 제시하였다. 이 방법은 비선형 쌍대(雙對)알고리즘을 이용해 큰 규모의 문제를 SUB라는 primal 문제와 MASTER라는 master문제의 두단계 문제로 분해하여 구성한다. 다루고자 한 문제의 대상 중 하나는 회분식공정에 있어서 설계와 스케쥴링 문제를 동시에 고려한 문제이고, 또 다른 하나는 공정규모의 확대를 포함하는 장기 생산계획 문제이다. 단기 스케쥴링 문제에서는 설계비용, 조업비용뿐 아니라 재고관리까지 고려해서 NPV를 최소화하는 문제로 구성된다. 생산계획 문제에서는 생산량 및 구입량뿐 아니라 각 공정규모의 확대까지 고려하고 있고, 미래의 수요예측이 불확실하기 때문에 이를 보완하고자 강건한 생산계획모델을 제시하고자 한다. 다룬 두 가지 문제들은 결정변수들이 많기 때문에 문제의 규모가 크고, 이에 따라 효과적인 계산방법을 요구하는 문제들이었다. 제시된 모델의 효율성은 단기 스케줄링 문제와 장기 생산계획 문제를 다루는 예제들을 통해 입증하였다.
Benders decomposition algorithm to improve the computation for the decision problems involved in chemical processes is addressed. Using nonlinear duality algorithm. a large scale problem is decomposed into two stage problems, SUB and MASTER, respectively. The target problems are short-term scheduling and design problems, and long-term planning problems including capacity expansions. In the first issue, the net present cost involving design cost and operation cost with consideration of inventory is minimized. The latter addresses robust models that are insensitive to future uncertainty. The problems presented in this paper are so computationally complex that enhanced algorithms have been required. The effectiveness of the improved algorithm is illustrated through examples relevant to scheduling and design problem, and long-term capacity expansion problem, respectively.
[References]
  1. Moon S, Bok J, Park S, HWAHAK KONGHAK, 35(5), 599, 1997
  2. Bok JK, Lee H, Park S, Comput. Chem. Eng., 22(7-8), 1037, 1998
  3. Lee H, Ph.D. Dissertation, KAIST, Taejon, Korea, 1997
  4. Reeve A, Process Eng., 73, 33, 1992
  5. Birewar DB, Grossmann IE, Comput. Chem. Eng., 13, 141, 1989
  6. Moon S, Park S, Lee WK, Ind. Eng. Chem. Res., 35(10), 3458, 1996
  7. Voudouris VT, Grossmann IE, Ind. Eng. Chem. Res., 32, 1962, 1993
  8. Voudouris VT, Grossmann IE, Comput. Chem. Eng., 20(11), 1335, 1996
  9. Sahinidis NV, Grossmann IE, Comput. Chem. Eng., 13, 1049, 1989
  10. Berman O, Ganz Z, Wagner JM, Naval Res. Logistics, 41, 545, 1994
  11. Paraskevopoulos D, Karakitsos E, Rustem B, Management Sci., 37, 787, 1991
  12. Ierapetritou MG, Pistikopoulos EN, Ind. Eng. Chem. Res., 33(8), 1930, 1994
  13. Liu ML, Sahinidis NV, Ind. Eng. Chem. Res., 35(11), 4154, 1996
  14. Markowitz HM, "Stochastic Optimization Models in Finance," Academic Press, New York, 1975
  15. Malcolm SA, Zenios SA, J. Opl Res. Soc., 45, 1040, 1994
  16. Brooke A, Kendrix D, Meeraus A, In GAMS: Users Manual, Scientific Press, Redwood City, CA, 1992
  17. IBM: "OSL(Optimization Subroutine Library) Guide and Reference," Release 2. Kingston, NY, 1991
  18. Drud A, Mathematical Prog., 31, 153, 1985
  19. Geoffrion AM, J. Opt. Theory Appl., 10(4), 237, 1972
  20. Benders JF, Number. Math., 4, 238, 1962
  21. Fletcher R, Leyffer S, Math. Prog., 66, 327, 1994