This dissertation focuses on layout planning for facilities with input and output points and shape constraints. We consider two types of decision problems for layout planning, arrangement of facilities within a floor and determination of locations of input and output points of the facilities. We develop efficient algorithms for two specific problems for each of the two types of decision problems.
First, we consider a facility layout problem in which each facility has a predetermined shape and input and output points. In the problem, facilities are placed within a given floor and the spatial coordinates and the orientation of facility are to be determined. We give a mixed integer programming (MIP) model for the problem with the objective of minimizing the sum of rectilinear distances weighted by flow amounts between input and output points of the facilities. Using the MIP model, we develop a two-phase algorithm based on a construction phase and a improvement phase.
Secondly, we consider a floorplanning problem in physical design of VLSI to place a set of blocks on a chip with the objective of minimizing area of the chip as well as total wire length. The block have different areas and their shapes are either fixed (predetermined) or flexible (to be determined). We use the sequence-pair suggested by Murata et al. (1996) to represent the topology of non-slicing floorplans and present two methods to obtain a floorplan from a sequence-pair. The two methods are implemented in a simulated annealing (SA) algorithm and used to find the best floorplan.
Thirdly, we consider a problem of locating input and output (I/O) points of each department for a given block layout with the objective of minimizing the total distance of material flows between I/O points. Here, distances between the I/O points are computed as the lengths of the shortest path between the I/O points. We develop a procedure to eliminate dominated candidate positions of I/O points and present a linear programming (LP) model for minimizing the total rectilinear distance of flows to obtain a lower bound. Using the elimination procedure and the LP model, a branch and bound algorithm is developed to find optimal locations of the I/O points.
Finally, we consider the problem of locating pickup and delivery (P/D) points of each workstation in AGV systems with the objective of minimizing the total distance of material flows between the P/D points. We suggest a procedure for eliminating dominated positions for P/D points and develop three SA algorithms to find good solutions within the solution space reduced through the elimination procedure.
Performances of all solution procedures are evaluated through series of computational tests on randomly generated test problems and well-known benchmark problems. Results of the computational tests show that the algorithms developed in this research give better solutions than existing algorithms in a reasonable amount of computation time. The algorithms suggested in this research can be directly applied to real-world problems. They can be used for the design of physical layouts of flexible manufacturing systems and cellular manufacturing systems and for physical layout design of VLSIs and PCBs, and for design of AGV systems. Also, the practicality of currently available layout design software packages can be enhanced if they are integrated with the algorithm suggested here for the I/O point location problems.
본 논문에서는 물류 입ㆍ출구와 모양에 제약을 가진 설비들의 배치계획에 관한 연구를 수행하며 이를 위해 2가지 종류의 의사결정문제를 다루고 있다. 첫번째는 설비들을 평면에 배치하는 문제이고 두 번째는 각 설비 내에서의 물류 입ㆍ출구의 위치를 결정하는 문제이다. 이 두 가지 종류의 문제와 관련하여 각각 두개의 문제들을 제시하였으며 이들을 해결하기 위한 효율적인 알고리듬을 개발하였다.
먼저, 논문의 2장에서는 모양과 물류 입ㆍ출구가 정해진 설비들을 주어진 평면에 배치하는 문제를 다루었다. 이 문제에서는 총 물류이송비용이 최소가 되도록 설비들의 위치와 놓여지는 방향을 결정한다. 혼합정수계획모형을 제시하였으며 이 모형을 사용하여 구축단계와 개선단계로 이루어진 2단계 휴리스틱 알고리듬을 개발하였다.
논문의 3장에서는 고밀도집적회로(VLSI)의 물리적 설계 단계에서 칩크기와 총 배선길이를 동시에 줄이도록 블록들을 배치하는 고밀도집적회로 블록배치 문제를 다루었다. 블록들은 서로 다른 크기를 가지며 모양은 고정되어 있거나 자유로이 변할 수 있다. Murata교수 외 3인이 제시한 순서열-쌍(sequence-pair)을 사용하여 블록배치안에서의 블록들의 상대적인 위치를 표현하였고부터 순서열-쌍으로부터 블록배치안을 생성해주는 2가지 방법들을 제시하였다. 제시한 두가지 방법들은 담금질기법(simulated annealing)에 구현되어 가장 좋은 블록배치안을 찾는데 이용되었다.
논문의 4장에서는 설비배치안이 주어졌을 때, 총 물류이송비용을 최소화 하도록 각 설비들의 물류 입ㆍ출구를 결정하는 문제를 다루었다. 각 설비의 물류 입ㆍ출구의 위치 대안들 중에서 열등한 것들을 제거해주는 방법을 제안하였고 총 물류이송비용의 하한가를 구하기 위한 선형계획모형을 제시하였다. 열등대안 제거방법과 선형계획모형을 사용하여 분지한계법(branch and bound algorithm)을 개발하였고, 이를 이용해 설비들의 물류 입ㆍ출구의 최적위치를 구하였다.
마지막으로 논문의 5장에서는 무인운반차량 시스템(automated guided vehicle system)에서의 각 작업장(workstation)마다의 물류 선적지점과 (pickup point)과 하역지점(delivery point)의 최적 위치를 결정하는 문제를 다루었다. 우선, 선적지점과 하역지점들의 위치 대안들 중에서 열등한 것들을 제거하여 해의 가능 영역을 줄였으며 담금질기법을 사용하여 각 선점 및 하역지점의 최적 위치를 결정하였다.
본 논문에서 제시한 알고리듬들은 임의로 생성된 문제들과 잘 알려진 벤치마킹 문제들을 사용하여 평가되었다. 평가로부터 제시한 알고리듬들이 짧은 시간 내에 기존에 개발된 알고리듬들 보다 우수한 해들을 찾을 수 있음을 확인하였다.
제시된 알고리듬들은 실제 문제에 바로 적용될 수 있다는 점에서 매우 실용적이다. 2장에서 제시된 알고리듬은 유연제조시스템(flexible manufacturing system)과 셀기반 제조시스템(cellular manufacturing system)에서의 설비배치를 위해 적용될 수 있으며 3장에서 제시된 알고리듬은 고밀도집적회로와 인쇄회로기판 설계 시 효과적으로 이용될 수 있다. 또한, 4장에서 제시된 물류 입ㆍ출구 위치 결정 알고리듬은 설비배치안 생성 알고리듬과 통합되어 설비배치계획 소프트웨어 패키지로 개발될 수 있으며 5장에서 제시한 알고리듬은 무인운반차량 시스템 설계를 위해 사용될 수 있다.
