For the construction and maintenance of large scale job shop scheduling systems, numerous approaches have been introduced. Most of the systems however suffer from their intrinsic complexity of scheduling and the poor real time responsiveness to the deviation from the original schedule. We argue that the computational complexity in the real world scheduling systems is caused by the excessive centralization of scheduling activities. In order to reduce the complexity, we suggest to distribute the scheduling activities to several lower level dispatchers under the centralized coordination of the supervising scheduler. For this purpose, we propose a two-layered hierarchical architecture. In this architecture, each dispatcher schedules and controls its work area independently as far as the constraints imposed by the supervising scheduler are not violated. If there occur and conflicts within a dispatcher, it is reported to the higher level scheduler so that the scheduler can take action to resolve the conflicts. Through a series of experiments, we found that the hierarchical architecture can reduce the complexity significantly and can provide the robustness of the original schedule to the local changes. The performance of schedules are evaluated with respect to tardiness, setups, and flow time not only for the generative scheduling phase but also for the reactive control phase.
The next objective of this research is the discovery of appropriate heuristics for the activity ordering, the time slot allocation, and the split of activities to parallel machines. We have also performed various experiments under different combinations of scheduling heuristics and architectures. Based on the contingencies found from the experiments, we can suggest how to design scheduling expert systems.
A prototype scheduling expert system named KAIS-3 was implemented based on the hierarchical architecture using the expert system development tool UNIK on SUN 3/280 work station.
작업 일정 계획 문제는 대상 문제의 복잡성(NP-Hardness) 및 동적인 생산 환경에 대응 할 수 있는 일정 계획(Robust Schedule) 이 요구되는 관계로 수리 모형 개발이 어려운 분야이다. 이에 본 논문에서는 인공 지능 기법을 이용하여, 이단계 계층적 구조(Two-Layered Hierarchical Architecture) 및 이 구조하의 일정 계획 휴리스틱들을 제시하고, 기존의 인공 지능 일정 계획 시스템들이 채택하고 있는 중앙집중적 구조(Centralized Architecure) 와의 성능 분석을 통해, 대상 문제의 성격에 따라 적합한 시스템 구조 및 일정 계획 휴리스틱들을 제시하고자 한다.
이단계 계층적 구조는 크게 상위 단계의 일정 조정자(Coordinating Scheduler) 와 하위 단계의 일정 생성 및 통제기(Dispatchers) 로 이루어지며, 가능상 특징은 다음과 같다.
(1) 상위 단계의 조정자가 주문들을 각기 관련된 생산 공정을 파악, 각 공정별 마감일을 설정한 후, 관련 정보를 해당 공정을 담당하는 하위 단계의 일정 생성기에게 분산시킨다. 이때 각 주문의 공정별 마감일을 사전에 적절히 결정해 주어야만 추후에 재일정 작업(Backtracking) 이 감소되어 복잡도를 줄일 수 있다.
(2) 하위 단계의 처리기(Dispatcher) 들은 각기 독자적으로 일정 계획을 수립하게 되는데, 위임받은 제약 조건들을 만족하지 못한 작업들은 상위 단계의 조정자에게 보고하여, 다른 처리기와의 협력을 통하여 일정 계획을 조정하도록 한다.
(3) 하위 단계의 각 처리기별 일정 계획은 한 작업이 여러 기계에 할당될 수 있는 복수기계 일정 문제(Parallel Machine Scheduling) 가 된다. 이때 효과적인 일정 계획을 위해서는 작업 처리 순서(Activities Ordering), 작업 시작 시각 선정(Activity's Start Time Selection), 기계할당(Resource Assignment) 의 단계적인 문제 해결 영역의 분할이 필요하다. 각 단계별로 필요한 휴리스틱들을 개발하고, 실험을 통해 일정 계획 목적에 따른 적합한 휴리스틱 조합을 제시하였다.
본 연구에서는 계층적 구조를 갖춘 구체적 전문가 시스템으로서, KAIS-3 를 개발하였다. KAIS-3 는 전문가 시스템 개발 도구인 UNIK 을 이용하여 SUN-3 기종에서 개발되었으며, 시스템의 주요 특성은 다음과 같다.
. 다중 흑판 모형(Multi-Blackboard) 을 이용한 복수 지식 베이스의 관리 . 프레임을 이용한 객체 지향적 자료관리
. 규칙을 이용한 패턴 매칭 형태의 추론(Rule-based Forward-Chaining Inference)
. 사전 규칙 분류(Procedural Control) 를 통한 추론 시간의 절약
. 사용자 인터페이스를 위한 화면 생성기
시스템에서 생성된 일정 계획을 이용하여 실제 작업을 수행하는 경우, 작업 환경의 동적인 성격으로 인해, 수립된 일정 계획과 실제 현황간에 차이가 필연적으로 발생하게 된다. 본 논문에서는 이러한 차이가 일정 계획에 미치는 영향을 파악, 종류별로 분류하고, 원계획(Original Schedule) 을 보정해주기 위한 휴리스틱들을 제시하였다. 모의 실험 기법을 이용하여, 계층적 구조를 갖춘 시스템이 중앙집중적 구조하의 시스템보다 계산의 복잡도를 감소시키고, 동적 생산환경에 대처하는 능력(Robustness) 이 우수함을 입증하였다. 또한, 선택된 각 구조하에서 여러 일정 계획 조합간의 능력을 통계적으로 비교, 분석함으로써, 대상 문제의 성격 및 일정 계획 목적에 따라 적합한 휴리스틱을 선택할 수 있는 기준을 마련하였다. 실제 생산 현장에서의 다양한 요구 사항을 반영하기 위한 전문가 시스템 설계시에 본 논문의 결과가 이용될 수 있을 것으로 기대된다.
