| 摘要 |
본 발명은 우선순위 및 상호 배제의 제약들을 갖는 복수의 동시 작업 시퀀스들을 스케줄링하는 방법 및 시스템에 관한 것이다. 특히, 본 발명은 자원들(머신들)의 세트를 사용해야 하는 비선점성 작업들을 포함하고 릴리즈 시간들 및 실행 시간들에 대한 제약들을 갖는 임상 샘플들에 대한 생물학적 분석들을 수행하는 시스템에 대한 스케줄러에 관한 것이다. 스케줄링 문제가 실제 산업 시스템에서 발생한다. 원칙적으로, 이러한 문제는 시간 페트리 넷(Time Petri Net) 및 타이밍된 오토머턴(Timed Automaton)과 같은 동시 모델에 대한 실시간 모델 체킹의 경우로서 공식화될 수 있다. 그러나, 이러한 접근방식은 예상 런타임 내장 플랫폼에서 실행가능하지 않다. 본 발명의 바람직한 실시예에 따른 스케줄링 방법은 완전한(full-fledged) 모델 체킹 툴의 엔진으로부터 DBM 데이터 구조들 및 Floyd-Warshall 알고리즘의 코어를 추출하여 경우의 특정한 요건들에 맞추는 의도적 알고리즘 솔루션을 활용한다. 이것은 준최적 솔루션들에 대한 휴리스틱들을 허용하는 서치의 복잡성을 크게 감소시키고, 증분적 알고리즘 개량들에 의해, 예상된 성능 요건들을 획득하는 것을 허용한다. |
