We consider facility layout problems with shape and position constraints for each facility. We use a simulated annealing (SA) algorithm for finding a layout in which sum of rectilinear distances weighted by flow amounts between facilities is minimized while satisfying the shape and position constraints for facilities. A solution of SA is encoded as a matrix of numbers. We convert the matrix into a layout by partitioning a floor plan into a set of rectangular blocks while satisfying areas of facilities. In the partition procedure, we suggest three methods to minimize the number of facilities which violate shape constraints. Computational results showed that the proposed algorithm gave better solution than existing algorithms, especially for problems which have tight shape constraints.
본 논문은 설비에 대해 모양과 위치에 제약이 있는 설비 배치 문제를 다루고 있다. 본 문제의 목적은 설비의 모양과 위치에 관한 제약을 모두 만족시키면서 설비들 간의 물류 이동 비용을 최소화 하는 배치를 구하는 것이다. 본 문제를 풀기 위해서 탐색 알고리듬의 하나임 시뮬레이티드 어닐링 알고리듬을 사용하였다. 시뮬레이티드 어닐링의 해는 설비들의 상대적인 위치를 나타내주는 매트릭스로 표현하였다. 생성된 매트릭스는 플로어 플랜을 사각형들의 집합으로 나눔으로써 설비들의 면적을 만족시키는 배치로 변환되었다. 플로어 플랜을 사각형의 집합으로 나눌 때, 설비들의 모양에 관한 제약들을 가능한 많이 만족시키기 위해 세 가지 방법을 개발하였다. 세 가지 방법들을 각각 사용한 시뮬레이티드 어닐링 알고리듬들을 기존의 알고리듬과 랜덤하게 만들어 낸 문제로 비교해 본 결과, 본 연구에서 제시한 알고리듬들이 더 좋은 결과를 보였다. 특히, 설비의 모양에 관한 제약 조건이 까다로워질수록 제시한 알고리듬들이 더욱 더 좋은 결과를 보였다.