Flexible manufacturing systems (FMSs), which can easily adapt to changes in product types and quantities, have been widely used in manufacturing areas, and they mostly consist of multiple machines and material handling robots. Scheduling of FMSs is extremely hard because different types of jobs are produced at the same time and deadlocks caused from robots can frequently occur. Branch and bound is one of the optimization methods which branches possible cases sequentially and prunes nodes by calculating the dominance rule and lower bound. Therefore, we propose a branch and bound (B&B) algorithm based on a timed Petri net (TPN) to find an optimal solution for the FMS scheduling problem. A TPN is first provided for the FMS, and deadlock avoidance rules are proposed. Also, tight lower bounds based on bottleneck machines and dominant marking state rules are developed. The experimental results show that the proposed algorithm can efficiently solve the various FMS problems
작업물의 양과 종류 변경을 쉽게 적용할 수 있는 유연 제조 시스템은 제조 분야에서 많이 사용되고 있으며 여러 기계 및 핸들링 로봇으로 이루어져 있다. 유연 제조 시스템 스케줄링은 다양한 종류의 작업물들이 동시에 진행되고 사용할 수 있는 기계 및 로봇의 수가 제한되어 있기 때문에 특정 작업을 마무리할 수 없는 교착 상태가 빈번하게 발생해 쉽게 풀 수 없다. 분기한정법은 가능한 노드들을 순차적으로 탐색하며 하한 및 지배적인 관계를 계산함을 통해 탐색 범위를 효과적으로 줄이는 최적화 방법이다. 따라서 우리는 유연 제조 시스템 문제의 최적 솔루션을 찾기 위해 시간 페트리 넷에 기반한 분기한정법을 제안하고자 한다. 먼저 시스템을 시간 페트리 넷으로 모델링한 후, 교착 상태를 피하기 위한 규칙들에 대해서 제안한다. 또한 빠른 탐색을 위하여 병목 기계에 기반한 강력한 하한 계산 방법과 지배적인 마킹 상태 규칙을 추가로 제안한다. 실험 결과를 통해 우리가 제안한 알고리즘이 다양한 유연 제조 시스템 벤치마크 데이터에서 효율적으로 최적해를 찾을 수 있는 것을 알 수 있다.
