철강 공정의 일정계획을 위한 혼합정수계획 모델

복진광, 이동엽, 박선원

한국과학기술원 화학공학과

Mixed-Integer Programming Model for Scheduling of Steelmaking Processes

Jin-Kwang Bok, Dong-Yup Lee and Sunwon Park

Dept. of Chem. Eng., KAIST

1. 서  론

철강공정에서의 일정계획 문제는 운전비를 최소화시키면서 고객의 납기일에 맞추어 정련된 철강을 생산, 배달하는 것으로 정의할 수 있다. 컴퓨터를 이용한 이에 대한 연구는 포괄적으로 이루어져 왔는데 크게 분류해보면 OR(operation research) 기법 [1, 2], 인공지능 기법 [3]으로 거론 할 수 있다. 일반적인 철강 생산 공정은 크게 3가지로 나눌 수 있다. ironmaking, primary steelmaking, 그리고 finishing 이다. 특히 primary steelmaking 단계가 일정계획 관점에서 가장 중요한 부분을 차지한다 [4, 5].

Ironmaking은 철강원료(철광석, 석탄)와 환원반응을 얻기 위해 석회석과 결합하여 hot iron 또는 선철로 알려진 중간제품이 생성되는 단계이다. 이 단계에서 생성된 hot iron은 primary steelmaking 단계에서 basic oxygen furnace (BOF), continuous caster (CC), hot strip mill (HSM)을 거쳐 다양한 종류의 반제품으로 전환된다. 그리고 마지막으로 표면 마무리, 코팅 등의 finishing 작업으로 제품이 완성된다.

Primary steelmaking 단계의 일정계획은 다음의 문제들을 다루어야 한다.

제조장치들의 이용 : 일정계획의 목적 중에 하나는 장치들을 잘 이용할 수 있도록 일정계획을 만들어내는 것이다.

병렬적인 제조장치사이의 생산의 할당 : 여러개의 연속주형들과 같이 기능적으로 유사한 장치들 사이에 어떻게 표준 작업량을 부과해야 하느냐를 결정하는 문제이다.

생산단계들 사이의 일정계획의 조정 : 상류흐름의 장치와 하류흐름의 장치간의 생산과 소비속도간의 균형이 고려된다.

그외에도 압연 그룹의 사양, 재일정계획(Rescheduling) 등과 같은 다양한 형태의 문제가 철강공정에서 고려된다.

또한 철강공정의 일정계획에서 중요하게 생각되어지는 부분이 CC와 HSM사이의 운전조건이다. 크게 3가지의 mode로 운전되어지는데 다음과 같다.

·Cold-charge : 여기에서 caster와 rolling mill은 완전히 분리되어 있다. caster에서 나온 슬래브들이 hot strip mill로 들어가기 앞서 재가열 용광로(reheat furnace)에서 압연 온도로 가열된다.

·Hot-charge : 이 모드의 운전으로 압연되기 전에 요구되는 재가열량을 감소시킨다. 그러한 경우 caster는 hot strip mill에 느슨하게 연결되어 있다.

·Direct-hot-charge : 이 모드의 운전은 주형과 hot strip mill 사이의 빈틈없는 연결을 요구한다.

실제 철강 공장은 혼합된 압연 모드(mixed-rolling mode)에서 운전되고 에너지의 최소사용을 위해서는 direct-hot-charge로의 운전이 바람직하다.

이상과 같이 매우 다양한 환경이 primary steelmaking부분에서 존재함을 알 수 있다. 따라서 이러한 특별한 문제들을 잘 설명하는 일정계획이 요구된다.

2. 일정계획을 위한 수학적 모델

본 절에서는 철강공정 중 primary steel을 만드는 공정의 일정계획에 대한 수학적 모델을 제안한다. 우선 대상으로 하는 범위는 그림 1에서와 같이 용광로에서 녹여진 상태의 철을 BOF를 통해 제련을 하고, ladle treatment에서 각종 합금 성분과 화학물질을 첨가 한 후, CC를 거쳐 HSM에서 압연 작업과 coiling 작업으로 주문 생산량을 만족시키는 문제로 정의한다. 본 모델에서는 혼합정수계획을 이용한 수학적인 방법으로 그 해를 제시하고자 한다. 여기에서 쓰인 알고리즘은 연속시간 표현법으로 시작과 끝을 나타내는 time slot외 불필요한 grid를 없애고자 하는 알고리즘이다 [6-10].

제조공정의 일정계획에서 주로 고려되는 목적식은 납기일을 만족하면서 최대 이윤을 낼 수 있도록 하는 것으로 다음과 같이 표현할 수 있다.

Maximize PROFIT	(1)

생산이윤 PROFIT는 최종생산물의 생산량과 해당되는 판매가격의 곱의 합과 재고비용을 고려해 재고량에 벌칙을 가하여 다음과 같이 나타낼 수 있다.

[eqn: PROFIT = SUM_{s in S} sum_{n in N} lambda_s Q_sn - SUM_{s in S} sum_{n in N} mu_s ST_sn]	(2)

각 생산량은 식(3)과 같이 기본 구매 요구량을 만족해야 한다.

[eqn: sum_{n in N} Q_sn GE R_s]	[eqn: FORALL s in S]	(3)

물질수지식은 다음과 같다.

[eqn: ST_sn = ST_s,n-1 + sum_{i in I_s} rho_si^p sum_{j in J_i} B_i,j,n-1 + sum_{i in I_s} rho_si^c sum_{j in J_i} B_i,j,n] [eqn: (FORALL s IN S_F,~~ n in N )~ BIGWEDGE (n GE2)]  (4)

Event slot n에서 생기는 state s의 양은 그 전 slot n-1에서 생기는 양에 만들어지는 회분량을 더하고 생산물로 나간 양을 제하면 된다.

첫번째 slot에서의 state s의 양은 초기 원료의 양에 의해 제한된다.

[eqn: ST_sn LE SIN_s]	[eqn: FORALL s in S, ~ LEFT || n RIGHT || =1]	(5)

회분량은 다음과 같은 제한크기를 갖는다.

[eqn: B_j ^min W_{i n} LE B_ijn LE B_j ^max W_{i n}]	[eqn: FORALL i in I, ~j in J_i ,~ n in N]                         (6)

task가 slot에 대응되었을 때([eqn: W_{i n} = 1]) 0-1변수를 사용해 회분량이 정의된다

또한 각 slot에 대해 각 장치에는 모든 task 중에 하나만을 수행할 수 있다. 이는 (7)식과 같이 표현된다.

[eqn: sum_{i in I_j} W_{i n} = Y_jn]	[eqn: FORALL j in J, n in N]	(7)

여기서 [eqn: Y_jn]가 장치 j가 slot n에 대응될 때 1, 나머지 경우는 0을 갖는다고 해서 반드시 0-1변수로 선언할 필요는 없다. [eqn: W_{i n}]이 0-1변수이므로 [eqn: Y_jn]은 [0, 1]의 범위를 갖는 연속변수로 선언해도 무방하다. 또한 변수의 수를 줄이고자 할 때는 (7)식을 이용하여 [eqn: Y_jn] 변수를 모두 치환함으로써 그 수를 줄일 수 있다. 각 task에 대한 시작시간과 종결시간의 관계는 다음과 같이 나타낼 수 있다.

[eqn: TE_ijn = TS_ijn + alpha_ij B_ijn]	[eqn: FORALL i in I, ~j in J_i ,~ n in N]	(8)

Event slot은 각 사건들의 순서를 나타내는데 유용하다. 모든 사건은 slot을 기준으로 그 시간적 관계를 알 수 있고 다음과 같이 표현된다.

[eqn: TS_i'j'n' GE TE_ijn - U(2-W_{i n} -Y_jn )] [eqn: (FORALL i,i' in I, ~j in J_i ,~ j' in J_i' ~ n, n' in N) BIGWEDGE ( LEFT || n RIGHT || < LEFT || n' RIGHT || )]  (9)

Task i가 slot n에서 장치 j에서 이루어 졌다면, 그 이후 slot인 n'에서의 작업의 시작시간은 n에서의 종결시간보다 항상 크거나 같아야 한다는 것을 나타내고 있다. 여기서 U의 값은 가능하면 작은 값으로 tight하게 식을 만들어주어야 계산하게 되는 정수계획문제의 node수를 줄일 수 있다. 주형과 압연사이 direct-hot-charge의 경우는 zero-wait가 이루어져야 하므로 해당 task에 대해 식(9)를 등식으로 바꾸어 표현할 수 있다.

동일한 장치에서의 시작시간 역시 slot의 크기로 그 관계를 결정할 수 있다

[eqn: TS_i'jn' GE sum_{n in N, LEFT || n RIGHT || < LEFT || n' RIGHT || } sum_{ i in I_j} (TE_ijn -TS_ijn )] [eqn: FORALL i' in I, ~j in J_i' ,~ n in N]	(10)

각 생산물은 주어진 납기일을 갖게되므로 이는 다음과 같이 표현된다.

[eqn: TE_ijn LE D_i]	[eqn: FORALL i in I, ~j in J_i ,~ n in N]	(11)

제조공정에서 또 다른 목적함수로 이용되는 것은 주어진 주문량을 만족하면서 최종생산시간을 최소화시키는 경우이다. 그런 경우는 다음과 같이 목적함수가 바뀌어야 한다.

Minimize MS	(12)

최종생산시간인 MS는 모든 task 중에 종결시간이 가장 늦은 것에 해당된다.

[eqn: MS GE TE_ijn]	[eqn: FORALL i in I, ~j in J_i ,~ n in N]	(13)

3. 예  제

그림 1에 보여진 장치의 최대 부피량 [eqn: B_j ^max]은 {j01 100, j02 75, j03 50, j04 40, j05 50, j06 40, j07 50, j08 40}이라 하고, 최소량 [eqn: B_j ^min]은 0이라고 한다. 각 state의 최대 용량은 {s01 10000, s02~s11 100, s12~s15 10000}이라고 하고 초기 양은 {s01 500, s02~s15 0}, 각 state의 판매가 [eqn: lambda_s]는 {s01~s11 0.0, s12 2.0, s13 2.3, s14 1.7, s15 1.0}라고 하자. 그리고 각 제품에 대한 최소 요구량은 {s01~s11 0.0, s12~s15 30}과 같이 주어졌다. 문제의 규모 및 계산결과는 표 1에 나타나 있다.

표 . 예제의 최적화 결과

0-1 variables	Constraints	Continuous variables	Profit	CPU[s]	Iterations
127	3149	1020	1063	273.28	7906

최적화 모델은 GAMS [11]를 통하여 구현하였고, 혼합정수계획 모델의 solver로는 OSL [12]을 이용하였다. SUN SPARC-10 workstation에서의 계산시간은 273.28초였다. 각 장치에서의 조업을 나타내는 Gantt chart는 그림 2와 같다.

4. 결  론

본 논문에서는 혼합정수계획 모델을 이용한 수학적인 접근방법으로 일정계획 해를 얻어내었다. 다룬 대상 공정은 primary steel-making 부분으로써, 주어진 납기일을 만족하면서 생산이득을 최대로 하는 경우와 주문량을 만족하면서 총 생산시간을 최소로 할 수 있는 두 가지 목적함수를 이용하여 모델을 구성하였다. 특히, 원료물질의 제약조건을 다룰 수 있고, 중간 저장능력을 고려할 수 있다는 면에서 실용적이라고 할 수 있다. 또한, 연속 시간표현법을 이용하여 모델의 효율성을 꾀하였고, 이는 예제를 통하여 보였다. 예제에서는 재고량에 벌칙을 가함으로써 각 state의 재고량이 줄어드는 것을 관찰하였다. 각 state의 초기조건을 가지고 최적화 작업을 수행할 수 있기 때문에, 공정에 이상이 발생하여 다시 일정계획이 필요한 경우에도 이를 빠르게 처리할 수 있는 재생산계획(rescheduling) on-line 일정계획 알고리즘으로써 기여할 수 있으리라 본다.

감  사

포항공대 지능자동화 연구센터(ERC)를 통한 한국과학재단의 부분적 재정 지원에 감사드립니다.

참고문헌

1. B. Lally, L. Biegler, and H. Henein, "A model for sequencing a continuous casting operation to minimize costs", Iron & Steelmaker, October 1987

2. V. Jain and I. E. Grossmann, "Integrated scheduliing in steel plants", FOCAPO 1998, Snowbird, Utah, USA, 1998.

3. N. Masayuki and S. Morishita, "Cooperative scheduling and its application to steelmaking processes", IEEE Transaction on Industrial Electronics, vol. 38, no. 2, pp. 150-155, 1991.

4. H. S. Lee, S. S. Murthy, S. W. Haider and D. V. Morse, "Primary production scheduling at steelmaking industry", IBM. J. Res. Develop., vol. 40, no. 2, pp231-252, 1996.

5. L. Lopez, M. W. Carter and M. Gendreau, "The hot strip mill production scheduling problem: A tabu search approach", European Journal of Operation Research 106 pp. 317-335, 1998.

6. J. M. Pinto and I. E. Grossmann, "A continuous time mixed integer linear programming model for short term scheduling of multistage batch plants", Ind. Eng. Chem. Res., vol. 34, no 9, pp. 3037-3051, 1995.

7. J.-K. Bok and S. Park, "Continuous-time modeling for short-term scheduling of multipurpose pipeless plants", Ind. Eng. Chem. Res., vol. 37, no. 9, pp. 3652-3659, 1998.

8. J.-K. Bok, S. Moon and S. Park, "Scheduling of multipurpose batch plants with sequence dependent changeovers", Ind. Eng. Chem. Res., submitted.

9. J.-K. Bok and S. Park, "Scheduling of pipeless processes considering sequence dependent setup time and transferring time", Hwahak Konghak, submitted.

10. M. G. Ierapetritou and C. A. Floudas, "Effective continuous-time formulation for short-term scheduling. 1. Multipurpose batch processes", Ind. Eng. Chem. Res., vol. 37, no 10, pp. 4341-4359, 1998.

11. A. Brooke, D. Kendrix and A. Meeraus, GAMS: Users Manual, Scientific Press, Redwood City, CA, 1992.

12. IBM: OSL (Optimization Subroutine Library) Guide and reference, release 2; Kingston, NY, 1991.

그림 2. 납기일을 만족하면서 생산이득을 최대화한 일정계획 결과.

그림 1. 예제에 대한 State-task network. (□ : task, ○ : state)