There have been many approaches and algorithms for scheduling diverse complex discrete event systems, such as workflows, job shops, flow shops, and automated manufacturing systems. Most of these methods have focused on their effectiveness or efficiency in solving their own problems. Hence, they tend to ignore the issue of compatibility with other scheduling problems, and the solution methods are ad hoc and hard to be used for other scheduling problems even with small changes. Since various scheduling problems with different constraints and objectives can be easily represented with a timed Petri net, we examine non-cyclic scheduling problems of timed Petri nets which have start and end transitions. We first develop an efficient branch and bound procedure for obtaining an optimal solution based on a reachability tree. A dynamic branching strategy that branches only enabled transitions is used, and a lower bound is computed by relaxing resource capacity constraints. The widely used resource-based lower bound is also generalized to timed Petri nets. The efficiency of the algorithm is verified with many complicated cluster tool scheduling problems. However, the reachability tree is so large for even a small Petri net that it takes a long time to search all possible paths in a reasonable time. Thus, we propose a new type of a reachability tree called a time-feasible reachability tree to reduce the search space of a scheduling problem by analyzing a firing sequence of transitions in a timed Petri net. A linear cluster tool scheduling problem with multiple robots and different types of wafers is easily handled with the new reachability tree. In addition to sequencing decision while assuming deterministic process times, we also analyze a schedulability issue of a timed event graph when activities or tasks have time window constraints and bounded time variations. We develop necessary and sufficient conditions for which there always or never exists a feasible firing schedule that does not exceed the maximum token delay at each place, and verify the conditions with a systematic procedure. We also develop a method that makes a given task sequence that does not satisfy the schedulability condition always schedulable by adding a feedback control arc. We finally apply all the algorithms and methods to a wet station scheduling problem that has time window constraints and reentrant flows. We develop specified deadlock avoidance conditions and define predetermined precedence relations, and then compare the efficiency of each strategy experimentally. With this research, we can easily schedule and control diverse complex discrete event systems.
본 논문에서는 시간을 갖는 페트리 넷의 비주기적 스케줄링 문제와 시간 제어를 다루었다. job shop 이나 flow shop 또는 자동화된 시스템의 스케줄링 문제는 그 동안 많은 연구자들이 해결하려고 노력하였고 효율적인 알고리즘 또한 많이 개발되어 있다. 그러나, 대부분의 알고리즘이나 방법론들이 특정 문제에 국한되어 있어 새로운 제약식이 추가되거나 목적식이 바뀌게 될 경우 기존에 개발된 방법들을 적용하기에 어려움이 있다. 페트리 넷은 이산사건 시스템의 모델링 및 분석에 사용되는 툴로서 스케줄링 문제의 다양한 제약식이나 목적식을 표현할 수 있다는 장점이 있다. 또한 시간을 갖는 페트리 넷은 플레이스와 트랜지션들이 토큰 홀딩 타임과 딜레이 시간을 가지고 있어 다양한 시스템을 모델링 할 수 있다. 따라서 본 논문에서는 페트리 넷을 기반으로 한 비주기적 스케줄링 문제를 분기 한정법을 이용하여 해결하고자 노력하였고 시간 변동 및 제약이 있는 경우 이벤트 그래프의 스케줄링 가능 여부 등을 판단할 수 있는 조건과 체계적인 검증 방법을 개발하였다.
페트리 넷의 스케줄링 문제는 해당 목적 함수의 최적값을 얻으면서 모든 트랜지션의 파이어링 (firing) 순서와 시점을 계산하는 것이다. 이네이블 (enabled)된 트랜지션만 시스템의 상태를 변화 시킬 수 있고 시스템의 모든 상태는 reachability tree를 이용하여 생성할 수 있다. 따라서 본 논문에서는 이네이블 된 트랜지션만 파이어링시키는 dynamic branching 전략을 사용하였으며 lower bound는 자원 제약을 완화시켜 페트리 넷을 이벤트 그래프 (event graph)로 변환한 후 선형 계획법 (linear programming) 을 이용하여 얻었다. 또한 one-machine sequencing 문제를 페트리 넷에 일반화시켜 기존 lower bound 보다 더 좋은 값을 얻을 수 있는 방법을 제안하였다. 챕터 2에서는 다양한 페트리 넷 모델을 스케줄링 할 수 있는 일반적인 분기 한정법을 개발하였고 클러스터 장비의 스케줄링 문제에 적용하여 그 효율성을 입증하였다. 챕터 3에서는 페트리 넷을 스케줄링 하는 데 있어 시간적으로 가능하지 않은 트랜지션 파이어링 순서들이 reachability tree에 생성되는 것을 발견하고 이를 줄이기 위하여 다양한 속성을 규명하였다. 또한 이를 간단한 flow shop 문제와 선형 클러스터 장비에 적용하여 문제 해결 시간 및 찾는 노드의 수를 많이 줄일 수 있음을 보였다. 챕터 4에서는 시간 제약 및 변동이 있는 시스템에서 스케줄링 가능 여부와 시간 제어에 관한 연구를 진행 하였다. 주어진 이벤트 그래프에서 실현 가능한 스케줄의 존재 여부를 타진할 수 있는 조건과 체계적인 검증 방법을 개발하여 클러스터 장비의 비주기적 운용에 적용시켜 보았다. 마지막 챕터 5에서는 많은 로봇과 시간 제약, 재방문 등의 제약을 갖는 ㅇㅞㅅ 스테이션 스케줄링 문제를 다루었다. 이전 챕터에서 개발된 알고리즘과 방법들이 적용되었으며 교착상태를 방지하기 위한 이론을 추가적으로 개발하였다. 이를 바탕으로 실험을 통하여 기존의 알고리즘들 보다 더 좋음을 보였고 시간 변동이 있는 경우 시간 제어에 관한 분석 또한 수행하였다.
