This paper addresses the branch-and-price algorithm for cyclic scheduling of timed Petri nets (TPN) and the branch-and bound method with tighter lower limits. Specifically, a TPN was employed to model the scheduling problem of cluster tools, a type of semiconductor manufacturing equipment. Cluster tools are typical single wafer process equipment used in most semiconductor processes, capable of performing multiple processes within one facility. Not only are cluster tools very costly, but they also frequently carry out bottleneck processes such as etching and deposition. Solving scheduling problems for efficient operation of cluster tools is vital in the semiconductor industry. Robotic cluster tools often have periodic scheduling, repeating the same work cycle, and we utilize TPN to address this issue. Firstly, we improved the problem-solving speed compared to existing methods by using the branch-and-price algorithm and new modeling. Modeling with assignment problem further enhanced efficiency by providing a lower bound superior to the existing branch and bound method.
본 논문은 시간을 가지는 페트리넷의 주기적 스케줄링을 위한 분지평가법과 더 타이트한 하한을 가진 분기한정법에 대해서 다룬다. 특히 반도체 제조 장비중 하나인 클러스터 장비의 스케줄링 문제를 모델링하기 위해 시간을 가지는 페트리넷을 활용하였으며 클러스터 장비는 대표적인 단일 웨이퍼 공정 장비로써 대부분의 반도체 공정에 사용되며 여러 공정을 하나의 설비에서 수행할 수 있다. 클러스터 장비는 매우 비쌀 뿐 아니라 식각, 증착 등 병목 공정이 수행되는 경우가 많으며 국내 반도체 회사들의 주력 장비로써 클러스터 장비의 효율적 운용을 위한 스케줄링 문제의 해결은 반도체 산업에서 필수적이다. 로봇화 된 클러스터 장비는 동일한 작업 주기를 반복하는 주기적인 스케줄링을 가지는 경우가 많은데, 우리는 시간을 가지는 페트리넷을 이용하여 이를 모델링하고 분석하였다. 우선 분지평가법 및 새로운 모델링을 활용하여 기존의 방식보다 빠르게 문제를 풀어내었다. 또한 불변량 분석과 확률적 경로 배정을 활용한 모델링으로 기존 분기한정법보다 뛰어난 하한을 제공하여 문제를 더욱 효율적으로 풀어내었다.
