In this thesis, we firstly describe the properties of job shop scheduling problem and review the various approaches to this problem, the classical approaches and knowledge-based ones. The former includes the methods based on the Operations Research literature such as mathematical programming, priority dispatching rule, and man-machine interactive scheduling. The latter includes the approaches based on the Artificial Intelligence literature such as constraint-directed search method, multiple perspective opportunistic scheduling, executional opportunistic scheduling, nonlinear planning method, rule-based approach, and logic-based ones. Having discussed the previous approaches, we propose KAIS-2 for job shop scheduling.
KAIS-2 is a knowledge-based job shop scheduling system adopting the generate-and-compare procedure. This procedure is useful in solving the problems which have intrinsic combinatorial complexity and dynamic environments like job shop scheduling problems. The characteristics of KAIS-2 are the following: 1) The flexible and structured representation of diverse relevant knowledge in frame form, 2) the generate-and-compare strategy using the multiple knowledge sources, 3) The reflection of user's preference in resolving the conflict of potential actions through interactive alternative comparison, 4) the learning capability to construct the user's strategy base automatically, 5) the object oriented programming paradigm for the interactions between resources. The research prototype of KAIS-2 is developed, and illustrated how this system works to solve the job shop scheduling problems.
일반적으로 다공정 생산 체제의 생산 일정 계획 문제는 매우 복잡하고 시간에 따른 환경의 변화를 사전에 알 수 없어 완전한 최적해를 구하기가 불가능하다. 따라서, 실제로 쓸모 있는 생산 일정 계획 시스템을 개발하기 위해서는 생산 일정 계획에 필요한 모든 지식을 구조적이고 효과적으로 표현할 수 있는 지식 표현 체계와, 이를 바탕으로 해를 구하고 수정해 나갈 수 있는 체계적 추론 방법이 마련되어야 한다.
본 논문에서는 생산 일정 계획 문제에 대한 지금까지의 접근 방법들 수학적 모형의 개발 (Mathematical Programming), 순위 결정 규칙의 개발 (Priority Dispatching Rule), 대화식 생산 일정 계획 방법 (Man-Machine Interactive Scheduling), 지식을 기초로한 접근 방법 (Knowledge Based Approach) - 을 고찰하고 이들의 장.단점을 논한 다음, 새로운 생산 일정 계획 시스템으로서 KAIS-2 (Knowledge Assisted Intelligent Scheduler)를 제안하고 이 시스템의 특성및 그 구성 요소의 기능을 설명하였다. KAIS -2 가 갖고 있는 중요 특성은 다음과 같다.
1) 프레임을 이용한 지식 표현 (Knowledge Representation in Frame)
2) 디몬을 이용한 시스템 상태의 자동적 생성 (Automatic Generation of System Status By Demon)
3) 여러 규칙에 의한 실행 대안 생성후 비교 선택의 과정을 통해 해를 구하는 추론 방법 (Generate-and-Compare Inference Mechanism)
4) 규칙을 이용한 여러 가지 생산 일정 계획 기법및 전략의 표현 (Scheduling Heuristic and Strategy Representation in Rule)
5) 메타 규칙을 이용한 실행 규칙의 선택 (Conflict Resolution by Meta Rule)
6) 메세지 교환에 의한 객체간의 상호 작용을 통한 규칙 실행의 구조화 (Structured Rule Execution by Message Passing Paradigm for The Interactions between Objects)
7) 단계적 배정후 역방향 수정 전략에 의한 생산 일정 계획 (Forward Assignment and Backward Adjustment Scheduling Strategy)
KAIS-2 는 생산 일정 계획에 관한 지식이나 전략을 규칙(Rule)으로 표현하는 시스템이므로 새로운 지식의 추가 및 기존 지식의 변경이 용이하여 환경이 다른 여러 생산 체제의 일정 계획 문제 해결에 이용 가능할 것으로 생각된다.
