화학공학소재연구정보센터
홈 로그인 로그아웃 연락처 사이트맵
HWAHAK KONGHAK, Vol.33, No.6, 734-746, December, 1995
Export Citation
유전 알고리듬을 이용한 Earliness 와 Tardiness Penalty를 가진 다품종 회분식공정의 생산계획
Scheduling of Multi-product Batch Processes with Earliness and Tardiness Penalties Using Genetic Algorithm
이창형, 정재학, 이인범
초록
고객에 대한 서비스와 재고비용절감 등 제품생산에서 발생하는 간접적 생산성에 관한 요소들이 특히 다단 회분공정의 다품종 소량생산체제에서의 생산계획에서 점점 더 중요한 문제로 부각되고 있다. 이러한 관점에서 주문한 제품군의 최적생산순서나 한 제품의 주문량이 커서 여러 회분을 연속적으로 생산하는 Campaign 생산 계획에 있어서 납기일 이전에 생산완료되어 발생하는 재고비용(earliness penalty)과 납기일 후에 생산완료되어 물어야 하는 납기일 위반 벌칙비용(tardiness Penalty)을 최소화하는 문제가 최근 세계적으로 많은 연구진들에 의해 매우 중요하게 다루어지고 있다. 본 연구는 이러한 earliness 및 tardiness penalty의 최소화를 목적함수로 하는 회분식 다단위 다품종 최적생산계획문제를 위한 유전 알고리듬(Genetic Algorithm)을 개발하였다. 유전 알고리듬은 최근 개발된 첨단 최적화 알고리듬으로 3가지 기본 연산자인 재생(reproduction), 교배(crossover) 및 돌연변이(mutation) 연산자를 가진다. 본 연구는 유전 알고리듬을 회분식 화학공정의 최적 생산계획에 적합하게 개선하기 위해 기본연산자 외에도 교배연산자의 강화, 돌연변이 빈도수 강화 및 Crowding Factor Model과 세대차(generation gap) 등의 확장된 연산자들을 유효 적절히 개발하여 사용하였다. 본 연구를 통해 개발된 유전 알고리듬의 성능평가를 위해 UIS 및NIS 중간저장탱크 운용방식의 회분식 화학공정의 생산계획문제를 무작위로 만들어 적용해 보았으며, 기존의 방법으로 가장 우수한 성능을 보이고 있는 Ku와 Karimi[16]의 simulated Annealing(SA)에 비해 매우 향상된 성능을 보임을 입증하였다.
Improving customer service and reducing inventory costs become more and more important aspects in the production scheduling of many batch processes. From this point of view, one of the important problems is to determine the optimum production sequence of a list of products or single-product campaigns so as to minimize the total penalty cost with earliness and tardiness where tardiness means any later deliveries than the due date and earliness is any early production resulting in the inventory cost. In this paper, we present a Genetic Algorithm(GA) for multi-product batch process scheduling problems with minimum cost of earliness and tardiness penalties. For this algorithm, we have improved the three basic operators, reproduction, crossover and mutation. Additionally we have developed the extended operators, so called Crowding Factor Model, Elitist Model and Generation Gap. To evaluate the performance of this study, we have tested various scheduling problems with UIS and NIS policies and the results are compared with Simulate Annealing(SA) method by Ku and Karimi[16]. Finally the GA by this work is outperformed to SA.
  1. Reklaitis GV, AIChE Symp. Ser., 78, 119 (1982)
  2. Reklaitis GV, "Perspectives on Scheduling and Planning of Process Operations," Proceedings of 4th International Symp. on PSE, Montebello, Canada (1991)
  3. Ku HM, Rajagopalan D, Karimi I, Chem. Eng. Prog., Aug., 35 (1991)
  4. Johnson SM, Naval Res. Logistics Quarterly, 1, 1 (1954)
  5. Dannenbring DG, Manage. Sci., 23, 1174 (1977)
  6. Rajagopalan D, Karimi I, "Scheduling in Serial Mixed-Storage Multiproduct Processes with Transfer and Set-up Times," Computer-Aided Proc. Oper., CACHE and Elsevier, New York, 679 (1987)
  7. Ku HM, Karimi I, Ind. Eng. Chem. Res., 27, 1840 (1988) 
  8. Wellons MC, Reklaitis GV, "Problems in the Scheduling of Batch Processes," Presented at the TIMS/ORSA Joint National Meeting, Washington, D.C. (1988)
  9. Musier RFH, Evans LB, Comput. Chem. Eng., 13, 229 (1989) 
  10. Baker K, Scudder G, Operations Res., 38, 22 (1990)
  11. Garey M, Tarjan R, Wilfong G, Math. Opns. Res., 13, 330 (1988)
  12. Fry T, Armstrong R, Blackstone J, IEEE Trans., 19, 445 (1987)
  13. Abdul-Razaq T, Potts C, J. Opnl. Res. Soc., 39, 141 (1988) 
  14. Jung JH, Lee HK, Yang DR, Lee IB, Comput. Chem. Eng., 18(6), 537 (1994) 
  15. Ku HM, Karimi I, Ind. Eng. Chem. Res., 29, 580 (1990) 
  16. Ku HM, Karimi IA, Comput. Chem. Eng., 15, 283 (1991) 
  17. Lee CH, Jung JH, Lee I, Comput. Chem. Eng., resubmitted (1994)
  18. Holland J, "Adaptation in Natural and Artificial Systems," University of Michigan Press (1975)
  19. Goldberg DE, Eng. Comput., 3, 35 (1987) 
  20. Goldberg DE, "Genetic Algorithms in Search, Optimization and Machine Learning," Addison-Wesley (1989)
  21. Rajagopalan D, Karimi I, Comput. Chem. Eng., 13, 175 (1989)