단일 장치열로 구성된 비순차 다목적 회분식 공정의 생산계획을 위한 유전 알고리즘

박상대, 손세훈, 정재학

영남대학교 화학공학및공업화학과

Genetic Algorithm for Scheduling of Single Line Non-sequential Multi-purpose Batch Process

Sangdae Park, Sehoon Son, Jae Hak Jung

School of Chemical Engineering and Technology, Yeungnam University

1. 서론

지난 10여 년간 회분식공정의 주요 연구대상이었던 다품종 회분식 공정에 비해 그 연구가 미비하였던 다목적 회분식 공정이 빠르게 변하는 소비자의 요구와 고부가가치제품의 시장수요 급상승 등의 이유로 최근 들어 주목을 받고 있다. 다품종 회분식 공정과 비교해서, 다목적 회분식 공정에는 각 제품들의 처리경로 불규칙, 불가능한 조업순서 존재 등 많은 다른 특징들이 존재한다[11].

본 논문에서는 다품종 회분식공정에 비해 더 큰 해 공간을 가진 다목적 회분식 공정 중 가장 간단한 구조인 단일 장치열로 구성된 비순차 다목적 회분식 공정[9]의 유전알고리즘을 이용한 생산계획방법을 제시하고자 한다. 대상공정으로는 UIS 정책을 사용하는 비순차 다목적 회분식 공정을 선택하였고, 수송시간 및 준비시간을 고려하였다. 또한 본 연구에서의 목적 함수는 makespan의 최소화로 정하였다.

2. 본론

유전알고리즘은 다윈의 적자생존과 자연도태 현상을 인위적으로 구현한 방법으로서 다른 최적화 알고리즘과 비교해서 가장 두드러진 차이점 두 가지가 존재한다. 첫째는 병렬 탐색 기법을 사용한다는 것이다. 이로 인해 탐색 도중 지역해 또는 준-최적해에 빠졌을 경우 여러 점을 동시에 탐색하는 병렬성을 이용하여 이런 상황을 극복할 수 있다는 장점이 있다. 둘째는 스트링(String)화된 변수와 그 함수값을 의미하는 적합도(Fitness) 두 가지만을 대상으로 최적화과정을 수행한다는 것이다. 다시 말해 다른 최적화 알고리즘에 비해 주변 파라미터들의 영향을 적게 받는다는 장점이 있다.

2.1 스트링과 적합도

본 논문에서의 변수는 makespan(적합도)을 계산하기 위한 조업순서이다. 스트링화 된 변수를 이용하여 makespan을 계산하기 위해 박(1997) 등이 제시한 수송시간 및 준비시간을 고려한 다목적 회분식 공정의 조업완료시간 알고리즘을 사용하였다[11].

식 (1)

결국 본 연구에서 사용한 스트링은 이진 스트링이 아닌 십진 스트링이다. 최소화 문제를 최대화 문제로 바꾸는 과정에 있어서는 정(1994)의 학위 논문을 참고하였다[10].

2.2 연산자 및 파라미터들

유전 알고리즘에는 세 가지 연산자(즉, 재생, 교배, 돌연변이 연산자)와 몇 개의파라미터(교배확률 Pc, 돌연변이확률 Pm, 세대수, 개체수 등)가 존재한다. 이외에도 De Jong 등(1995)이 제시한 고급 파라미터들(Elitist model, Expected value model, Elitist expected value model, Crowding factor model, Generalized crossover model)이 존재한다[8]. 본 논문에서 사용한 연산자와 파라미터들을 살펴보면 다음과 같다.

① 연산자들

본 연구에서는 유전 알고리즘에 대한 다른 연구들[1∼8]에서와 마찬가지로 세 가지 연산자(즉, 재생, 교배, 돌연변이 연산자)를 사용하였다. 재생연산자는 한 세대를 구성하는 개체들의 우열을 가려서 현세대의 우등개체가 자신의 좋은 유전정보를 다음세대에 물려줄 수 있게 인위적으로 구현한 것 다시 말해 자연도태의 인위적 구현 방법이다. Roulette Wheel 방법을 사용하여 이 연산자를 구현한다. 그러나 재생연산자의 구현이 거듭될수록 즉 몇 세대를 거쳐 재생연산자를 사용하면 각 개체의 적합도 값이 전체적으로 좋아지므로 우열을 가리기가 힘들어지게 되고, 이로 인해 문제가 발생할 수 있다. 이런 경우 좋은 값은 더 좋게, 나쁜 값은 더 나쁘게 만들어 줌으로서 우열을 두드러지게 만드는 것이 스케일링 작업이다. 본 논문에서는 선형 스케일링 대신 Sigmoid 스케일링 방법을 사용했다. 재생연산자와 스케일링을 거친 후 교배장(mating pool)으로 한 쌍의 개체를 복사하고 그 개체들을 서로 교배시킨다. 물론 교배장으로 개체를 복사할 때 사용하기 위해 우열을 가려 각 개체에 선택될 확률을 부여하는 것이 재생연산자이다. 본 논문에서는 PMX 교배방법을 사용하다. 마지막으로 본 연구에서 사용한 돌연변이 방법으로는 인접 상호 교환방법과 활주 상호 교환 방법을 사용하였다.

② 파라미터들

교배확률(Pc)이 1 이라는 것은 교배장에서 무조건 교배를 한다는 것이고 그 확률값이 0 이라는 의미는 교배를 하지 않는다는 것 즉, 부모개체를 다음세대에서 그대로 복제한다는 것을 의미한다. 본 연구에서는 교배확률(Pc)을 1로 정하였다. 또, 돌연변이 확률은 0.01을 사용했다. 개체수와 세대수에 있어서는 정 등(1998)이 사용한 값을 사용했다[6]. 결국, 그림 3에서 나타낸 것과 같이 몇 세대를 거치면 적합도의 최대값(목적함수값을 최대화하는 문제의 경우)과 적합도의 평균값이 첫 세대의 경우에서 보다 근접하게 될 것이다. 그래서 주어진 수렴조건 내에 속할 경우에는 전체 세대수를 거치지 않고도 종료할 수 있다. 본 논문에서 사용한 파라미터들의 값을 표 1에 나타내었고, 표에서 N은 처리해야 할 제품수를 나타내고, M은 장치수를 나타낸다. 그리고, 전체적인 유전 알고리즘의 순서도는 그림 1에 나타내었다.

3. 적용 예제

그림 2에 나타낸 공정도[13]는 대표적인 비순차 다목적 회분식 공정의 예이고 본 논문에서는 이 공정이외에도 많은 임의 공정들에 대해 유전 알고리즘을 적용하였다. 그림 3에서 가로축은 세대 번호를 나타내고 세로축은 적합도(본 논문에서는 makespan)를 나타낸다. 그리고 그림 3에서 F_min은 각 세대의 적합도 중 최소값을 나타내고 F_avg는 각 세대에서 적합도의 평균값을 나타낸다.

4. 결론

본 논문에서는 다품종 회분공정에 비해 그 해 공간이 상당히 큰 비순차 다목적 회분공정에 대한 생산계획문제에 유전 알고리즘을 적용하였다. 그리고 계산시간 및 수렴성 및 해의 성능 등에서 우수함을 보였다. 그러나 De Jong등이 제안한 고급 파라미터들의 적용과 더 복잡한 다목적 공정으로의 확대적용 등이 앞으로의 과제가 될 것이다.

5. 감사

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

6. 참고문헌

1. Goldberg, D.E., "Genetic Algorithms in Search, Optimization and Machine Learning", Addison-Wesley Publishing Co. (1989)

2. Davis, L., "Handbook of Genetic Algorithms", Van Nostrand ReinHold, New Yourk (1991)

3. Yural Davidor, " Genetic Algorithms and Robotics : A Heuristic Strategy for Optimization", World Scientific (1991)

4. L. Davis, "Genetic Algorithms and Simulated Annealing", Morgan Kanfmann Publishers (1987)

5. Rawlins, G.J.E., "Foundation of Genetic Algoritnms", Morgan Kanfmann Publisheres (1991)

6. Jae Hak Jung, Chang Hyung Lee and In-Beum Lee, "Short-note a genetic algorithm for scheduling of multi-product batch processes", Computers Chem. Engng Vol. 22, No. 11, pp. 1725-1730, (1998)

7. Hugh M. Cartwright and Robert A. Long, "Simutaneous Optimization of Chemical Flowshop Sequencing and Topology Using Genetic Algorithms", Ind. Eng. Chem. Res. 32, 2706-2713, (1993)

8. De Jong, K.A., "Genetic Algorithms; a 10 year perspective.", Proc. nt. Conf. on Genetic Algoritm and their Application, pp. 210, (1995)

9. Voudouris, V.T. and Grossmann, I.E., "MILP Model for Scheduling and Design of a Special Class of Multipurpose Batch Plants",  Computers Chem. Engng Vol. 20, No. 11, pp. 1335-1360, (1996)

10. 정재학, □다품종 회분식 공정의 최적생산계획 및 자동화 모델□, (1994)

11. 박상대, 김형준, 정재학, □다목적 회분식 공정의 최적 조업완료시간결정 알고리즘□, 화학공학의 이론과 응용, Vol. 3, No. 2, pp. 1897-1900, (1997)

그림 3. GA 결과값의 추이도

그림 1. GA의 순서도

그림 2. 비순차 다목적 회분식 공정의 예

표 . 각 파라미터의 값

파라미터 이름	파라미터 값
세 대 수	3×N
개 체 수	10×N
교배 확률	1.0
돌연변이 확률	0.01