Development of spatial scheduling expert systems

Abstract

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 pr...