큰 다목적 회분식공정의 생산계획문제에 대한 Simulated Annealing의 개조

박상대, 손세훈, 정재학

영남대학교 화학공학부

Modification of Simulated Annealing for Large Size Scheduling Problems of Multi-purpose Batch Process

Sangdae Park, Sehoon Son, Jae Hak Jung

School of Chemical Engineering and Technology, Yeungnam University

1. 서론

지난 10여년간 회분식 공정의 하나인 다품종 회분식 공정의 연구는 크게 둘로 나누어졌다. 하나는 생산계획 관점에 대한 연구이고 다른 하나는 공정설계 관점으로 나눌 수 있다. 생산계획 관점에서의 연구는 이미 설계과정을 마친 공장에서 소비자나 고객들로부터의 주문제품을 □어떻게 하면 최소의 비용으로 최대의 이익을 얻을수 있을까?□하는데 초점을 둔것이고 공정설계 관점은 시장성이 높은 제품을 생산하기 위한 공장설비를 □어떤 배치 또는 어떤 크기로 했을 때 경제성에서 뛰어나게 할 수 있느냐□는데 중점을 둔 것이다. 연구단계에서는 비교적 작은 문제를 다루지만 실제공정에서는 그 문제의 크기가 커지는 것이 보통이다. 다품종회분식 공정의 연구는 이미 실제 공정에 많이 적용되고 있는 실정이다. 반면에 회분식 공정 중 다른 하나인 다목적 회분식 공정에 대한 연구는 극히 미미하다고 할 수 있다. 본 논문에서는 다품종 회분식 공정에서 비교적 큰 크기 문제에 대해 성능이 우수했던 SA 알고리즘을 개조해서 다목적 회분식 공정에 대해 적용하였고 그 성능을 SA와 비교하였다. 본 논문에서 목적함수는 makespan의 최소화로 두었고 무작위로 생성한 상당히 많은 문제를 적용시켜본 결과 본 연구의 방법이 매우 우수한 결과로 나타났다.

2. 본론

2-1. 대상공정

본 논문에서 선택한 대상공정은 비교적 큰 크기의 문제들로서 총 조업순서가 15!∼30!인 6개의 대상공정들을 임의로 만들었다. 각 공정마다 무작위로 15개의 문제를 생성했다. 그 대상공정들 중 제품수가 10개, 장치수가 8개인 공정의 예를 그림 1에 나타내었다. 그림 1에서 Pi는 제품, Ui는 장치를 나타내고 화살표는 제품의 처리 경로를 의미한다.

2-2. 다목적 회분식 공정의 조업최적화를 위한 모델링

다목적 회분식 공정이란 제품들의 경로가 일정치 않아 장치들을 다목적으로 사용하는 공정을 말한다. 이러한 다목적 공정의 최적 생산계획을 위해 필수적인 조업완료시간 알고리즘은 다음과 같다. 다음 식은 수송시간과 준비시간을 고려한 다목적 회분식 공정의 조업완료시간 알고리즘이다.

(식 1)

2-3. SA알고리즘의 개조

Ku와 Karimi[1991]가 제시한 metropolis 알고리즘에 기초한 SA 알고리즘은 그 내부변수들에 의해 성능면에서 많은 영향을 받는다. 그 중 본 논문에서는 기존의 SA로부터 초기해, 초기해로부터 다음해의 생성방법, up-hill movement 확률등 3가지 요소를 수정해서 개조된 SA 알고리즘을 개발했다. 우선 초기해는 무작위 방법에서 RAES를 다목적 회분식 공정에 적용할 수 있게 개조한 MRAES(Modified RAES)방법을 사용했고, 초기해에서 다음해를 생성하는 방법은 pairwise change에서 pairwise change 방법과 random generate 방법을 교대로 적용하는 방법을 채택했다. 그리고 초기해가 좋은 곳에 위치했으므로 나쁜해를 받아들일 확률을 낮추어야 한다. 그렇지 않으면 좋은해 영역에서 나쁜해 영역으로 해가 이동할 확률이 높아질 수 있기 때문이다. 그래서 up-hill movement 확률은 조절변수의 감소율을 조정하여 낮추었다. 조절변수의 감소율을 0.6∼0.95사이에서 시행착오적 방법으로 최적값을 구했다. 큰 크기 문제에 있어서 그 값은 0.8이었다. 이 값을 사용했을 때 up-hill movement 확률값은 다음 (식 2)과 같다.

[eqn: lpile{P`_1``(DELTAE)``=``EXP( -(DELTAE_i )/T_1 )``SIMEQ``bold under 0.513 # ~~ T_1 = kt_1 = bold under 1.5 TIMES SUM_i=1^3000 ({|DELTAE_i` |}/3000) # P`_20``(DELTAE)``=``EXP(-(DELTAE_i )/T_20)``SIMEQ``bold under 0.0 # ~~ T_20 = 0.8^19 times T_1 = bold under 0.0144 times bold under 1.5 TIMES SUM_i=1^3000 ({|DELTAE_i` |}/3000)}]	(식 2)

2-4. 평가

큰 크기 문제에 있어서는 최적값을 확인할 수가 없기 때문에 본 논문에서 제시한 알고리즘의 값과 SA 결과값의 차이를 평균한 값을 Difference로 정의했다. 다음 (식 3)에서 Difference의 값이 클수록 본 논문에서 제시한 알고리즘이 우수함을 알 수 있다.

[eqn: Difference ``= {sum_i=1^N{(SA-Hybrid~System)_i}} over N]	(식 3)

그림 2는 Difference를 나타낸것이고 그림 3은 계산시간의 결과값을 나타낸 것이다. 그림들에서 나타난것처럼 본 연구는 Difference 및 계산시간에서 우수한 결과를 나타냈다.

3. 결론

본 논문에서는 Ku와 Karimi가 제시했던 SA 알고리즘의 내부변수중 초기해, 초기해에서 다음해의 생성방법 그리고 up-hill movement 확률을 수정해서 실제 회분식 공정과 유사한 큰 크기 문제의 생산계획에 적용하였다. 큰 크기 문제의 준최적해에서 본 연구는 SA보다 상당히 우수한 값을 구했고 계산시간 측면에서는 비교도 안될 만큼의 성능을 나타내었다. 하지만 시행착오적으로 최적화시킨 내부변수들이 상호종속적이라는 면에서 볼 때 내부변수들을 체계적으로 최적화시키는 것과 GA등과 같은 다른 알고리즘에 적용시키는 것들이 앞으로의 과제일 것이다.

그림 . 큰 크기의 다목적 회분식 공정의 예

그림 2. Difference의 결과 비교

그림 3. 계산시간의 비교

4. 감사

본 연구는 포항공과대학교 공정산업의 지능자동화연구센터를 통한 한국과학재단 우수연구센터 지원금에 의한 것입니다.

5. 참고문헌

E. C. Yamalidou, E. P. Patsidou and J.C. Kantor, □Modeling Discrete-event Dynamical Systems for Chemical Process Control-A Survey of Several New Techniques□, Computers chem. Engng. Vol. 14, No. 3, pp. 281-299,(1990)

Hasebe, S. and Hashimoto, I., □Optimal Design a Multi-purpose Pipeless Batch Chemical Plant□, Proc. Fourth Intl. Symp. on Proc. Systems Engng, Monte bell, Canada, (1991)

Jung, J. H., Lee, H., Yang, D. R. and Lee, I., □Completion times and optimal scheduling for serial multi-product processes with transfer and set-up times in zero wait policy□, Computers chem. Engng, Vol. 18, pp. 537-544, (1994)

Kim H. J., Jung J. H., Kim M., and Lee I., □A Hybrid System for Large Size Scheduling Problems of Batch Processes with Pipeless Intermediate Storage□, KJChE, Vo1. 14, No. 4, pp. 225-232 (1997)

Ku, H. M. and Karimi, I., □An Evaluation of Simulated Annealing for Batch Process Schedulin□, Ind. Engng Chem. Res., 30, pp. 163 (1991)

W. Wiede Jr and G. V. Reklaitis, □Determination of completion times for serial multiproduct process-2. A multiunit finite intermediate storage system□, Computers chem. Engng., Vol. 11, pp. 345(1987)