In large-scale industries like shipbuilding, aircraft manufacturing, and construction, the work-in-process subassemblies as well as assemblies are usually very heavy and bulky assemblies, it is necessary to employ expensive material handling equipment like cranes and work plates. Since the space equipped with such facilities is usually limited and bottlenecked, the scheduling needs to consider spatial resources, as well as more traditional resources such as like manpower and machinery. We call this type of scheduling Spatial Scheduling. As the term implies, spatial scheduling pursues the optimal dynamic spatial layout schedule which can also satisfy traditional scheduling constraints.
As a prior research for spatial scheduling, we study orientation-fixed convex polygon layout problem considering spatial scheduling context. The Feasible Locatable Space is computed using the configuration space approach. To extract a set of meaningful points out of the continuous space, we define Distinctive Locatable Point Set which consists of the vertices of the feasible locatable space. Theoretically speaking, the Distinctive Locatable Point Set is not sufficient search space, but it has empirically provided very satisfactory locations with the advantage of computational efficiency in shipbuilding domain. Given the search space, we propose four positioning strategies - Maximal Remnant Space Utilization Strategy, Maximal Free Rectangular Space Strategy, Initial Positioning Strategy, and Edging Strategy - and incorporate them into a composite positioning algorithm which applies the strategies contingently according to the situation. During the research on spatial scheduling, we investigate the Sufficient Search Space to reduce the search space to tractable and effective one. We prove the two theorems on the sufficient search space in rectangle layout and arbitrary-shaped object layout respectively. In rectangle layout, the Convex Vertex Set of the Feasible Locatable Space is proved to be the sufficient search space. In arbitrary-shaped object layout, the sufficient search space is proved to be the Boundary Point Set of the Feasible Locatable Space.
Adding the time dimension to the two-dimensional layout problem, dynamic spatial layout methodology is developed, in which the spatial activities can be regarded as cylinders and the spatial resources as parallelepipeds. We define Distinctive Schedulable Point Set as the search space and develop the three-dimensional versions of the four positioning strategies and devise the fifth positioning strategy - Clustering Strategy.
We develop backtracking methodology for spatial scheduling, which consists of six types of adjustment: Work Plate Re-Selection, Intra-Plate Spatial Adjustment, Inter-Plate Spatial Adjustment, Intra-plate Temporal Adjustment, Intra-plate Spatiotemporal Adjustment, Inter-plate Spatiotemporal Adjustment. The proposed methodology is implemented for reactive scheduling phase and visual interactive scheduling phase as well as in generative scheduling phase. The graphic user interface for visual interactive spatial scheduling is developed, in which reactive spatial scheduling methodology is incorporated such as Virtual Cutting.
Our methodology is a product of scheduling expert system project named 'DAS'. In the project, three spatial scheduling expert systems have been developed, DAS-CURVE, DAS-ERECT-SPACE, DAS-LPP-SPACE. They are successfully operational in the field. We explain the characteristics of each domain and report the performance and effects of the systems. With the experience and results from the development of the specific applications in shipbuilding, we have built the primitives and their modules for spatial scheduling into a kernel system, UNIK-SPACE.
The spatial scheduling methodology is expected to be applicable for domains like shipbuilding, airplane assembly shops, construction, warehouses, and retail stores, and delivery container scheduling, etc.
공간 일정계획은 인력이나 기계와 같은 전통적인 자원의 사용 계획뿐만 아니라 조립물이 생산 기간동안 점유하는 공간 자원의 효율적인 활용 계획을 다루는 문제 로, 조선, 항공, 건설등의 대규모 산업 현장에서 자주 발생하는 문제이다. 공간 일정 계획 문제는 보통의 일정 계획 문제와 동적인 공간 배치 문제가 혼합된 형태 의 문제이며, 일반적인 일정계획 문제의 제약조건을 만족시키면서 최적의 공간 배치를 찾는 문제이다.
연구의 첫 단계로, 공간 일정계획의 상황에서, 배치 방향이 고정된 볼록 다각형의 공간 배치 문제를 연구하였는데, 배치 가능 공간을 구하기 위하여 형상 공간 기법 을 사용하였다. 구해진 배치 가능 공간은 연속 공간이므로, 의미 있는 해들을 뽑아내기 위하여, 배치 가능 공간의 꼭지점을 특이 배치점 집합으로 정의하여 사용 하였다. 이론적으로 말할 때, 특이 배치점 집합은 충분한 탐색공간은 아니지만, 조선 공업에서의 공간 일정계획 문제에서는 계산의 효율성과 더불어 만족스러운 결과를 보였다. 구해진 탐색공간에서 상황적으로 사용될 수 있는 네가지의 배치 전략 - 잔여 공간 최대 이용 전략, 빈 직사각형 공간 최대화 전략, 초기 배치 전략, 가장자리 배치 전략 - 들을 개발하고 그것을 통합한 배치 알고리듬을 개발하였다.
연구의 과정에서, 공간 배치에서의 충분 탐색 공간에 대한 이론적 연구를 하였는데, 그 결과, 직사각형 배치 문제에서는 배치 가능 공간의 볼록 꼭지점 집합이 충 분 탐색 공간이 되고, 임의의 모양을 가지는 물체의 경우에는 배치 가능 공간의 경계점 집합이 충분 탐색 공간이 됨을 증명하였다.
2차원의 배치 문제 방법론에 시간축을 추가하여, 동적인 공간 배치 방법론을 개발 하였는데, 앞의 네개의 배치 전략을 3차원상의 전략으로 확장하고, 5번째의 배치 전략(묶음 배치 전략 )을 개발하였다.
공간 일정계획에서의 역추적 탐색을 위하여, 6개의 조정 방법 - 정반 재 선택, 정 반내 위치 조정, 정반간 위치 조정, 정반내 시간 조정, 정반내 위치-시간 조정, 정반간 위치-시간 조정 - 을 개발하였는데, 이 조정 전략들은 일정 계획 생성 단 계에서 뿐만 아니라, 일정 계획 조정 단계에서도 사용된다. 또한, 시각적 일정 계 획 조정을 위한 그래픽 사용자 인터페이스를 개발하였는데, 내부적으로는 가상 절단과 같은 공간 일정계획을 위한 리액티브 일정계획 방법론이 기능하고 있다.
이 연구는 DAS라는 조선 공업을 위한 일정계획 전문가시스템 개발 프로젝트의 일환으로 수행되어 왔는데, 이 기간동안 DAS-CURVE, DAS-ERECT-SPACE, DAS-LPP-SPACE의 각각의 특성을 가진 공간 일정계획 전문가 시스템이 구현되었고, 현장에 성공적으로 운영중이다. 이들 시스템들로 부터 공간 일정계획을 위한 핵심 시스템인 UNIK-SPACE가 구축되었다.
이 논문에서 개발된 공간 일정계획 방법론은 조선 공업, 항공기 생산, 건설, 창고 운영, 유통 산업, 콘테이너 일정계획등의 분야에 응용될 수 있을 것으로 예상된다.
