There can be many scheduling problems one of the resources in which is two or three dimensional space. We will call spatial resource scheduling problem 'Spatial Scheduling' in this thesis. Since spatial scheduling should plan the dynamic spatial layout, the characteristics of the problem are different from those of traditional scheduling problem. Spatial scheduling has two major topics. One is scheduling and the other is spatial layout planning.
As a prior phase of research about spatial scheduling, we develop a methodology for spatial allocation of convex polygons in a rectangle. As a representation scheme of the problem, we apply configuration space approach in Find-path problem. Above its foundation, the concept of distinct space is introduced to reduce search space. And given search space reduced, several allocation strategies are developed, compared each other and combinated to increase allocation performance. In two dimensional spatial resource problem, we introduce a three dimensional view of the spatial scheduling. With the three dimensional view of spatial scheduling, we define distinct scheduling space and propose the strategies for searching a solution in the space.
The developed methodologies for spatial scheduling are applied to block assembly scheduling in ship building industry. To satisfy the constraints of the factory environment, we adopt a knowledge-based approach and develop a spatial scheduling expert system (DAS-SS) using UNIK-FRAME, UNIK-WINDOW, and LISP languages. Due to computational intractability of spatial scheduling problem, we develop heuristic procedures composed of a myopic optimal scheduling procedure and a backtracking procedure.
일정 계획을 시간에 따라 작업에 자원을 할당하는 문제라 할때, 그 자원중에 하나가 2차원 또는 3차원의 공간인 문제들이 있을 수 있다. 이러한 일정계획 문제를 이 논문에서는 공간 일정 계획이라 부른다. 공간 일정계획은 시간에 따라 변하는 공간적 배치에 관한 계획을 수립해야 하므로 전통적인 일정계획과는 다른 특성을 가지고 있다. 공간 일정계획을 보면 크게 두가지 해결해야할 문제가 있는데, 하나는 일정계획 문제이고 다른 하나는 공간 배치 계획 문제이다.
공간 일정 계획의 전 단계로서, 직사각형에 볼록다각형들을 할당하는 문제에 관한 방법론을 개발하였다. 이 문제의 기본 표현 체계로서 길찾기 문제에서의 configuration space 방법을 적용하였다. 그 기초위에 특이 공간(Distinct Space)의 개념을 정의하여 탐색 공간을 줄이고, 특이 공간을 탐색하는 세개의 할당 전략을 개발, 비교, 합성하였다. 2차원 공간 자원문제에서는 공간 일정계획의 3차원적 관점을 제시하여 특이 일정계획 공간(Distinct Scheduling Space)을 정의하고 그 공간에서 해를 찾는 전략들을 제시하였다.
개발된 방법론을 조선 공업에서의 블록(block) 조립 일정계획에 적용하였는데, 공장의 제약조건을 만족시키기 위해 지식 기반 방법을 적용하고, 공간 일정계획 전문가시스템(DAS-SS)을 UNIK-FRAME, UNIK-WINDOW등의 도구와 LISP 언어를 가지고 개발하였다.
