This thesis focuses on the problem of designing a material flow network for a given block layout. For an efficient design of a network, locations of input and output points, flow paths, and the smoothness of material flows are considered simultaneously. The problem is formulated as a mixed integer program by representing a block layout as a directed graph. For the problem with the objective of minimizing the sum of transportation cost, flow path construction cost and penalty cost for non-smooth material flows, we suggest two heuristic algorithms based on the LP-relaxation and the Lagrangian relaxation techniques. To evaluate performance of the suggested algorithms, a series of computational experiments is performed on well-known problem instances as well as randomly generated test problems. Results show that the suggested algorithms give good solutions in a reasonable amount of computation time.
본 논문은 주어진 block layout 하에서의 물류 네트워크 설계 문제를 다루고 있다. 시스템을 유지하기 위한 단위 면적당 고정비용이 매우 큰 LCD (liquid crystal display) 제조 공장과 같은 경우 효율적인 물류 네트워크 설계가 곧 큰 비용 절감으로 이어지므로 효율적인 물류 네트워크 설계는 매우 중요한 문제가 되고있다. 기존의 다른 연구에서 입출고 점들의 위치 선정과 물류 흐름 경로들의 설계를 개별적으로 다루었던 것에 반해 본 논문에서는 입출고점의 위치와 흐름 경로, 물류 흐름의 smoothness를 동시에 고려하고 있다. 주어진 block layout을 방향성 있는 그래프로 변환함으로써 이 문제는 혼합정수계획법으로 표현되며 이 때의 목적식은 총 운송 비용, 흐름 경로 건설 비용, 흐름 경로의 smoothness에 따른 penalty 비용의 합을 최소화 하는 것이다. 입출고점의 위치들이 결정되고 단위 penalty 비용이 없을 때 본 문제는 이미 잘 알려진 NP-hard 문제인 the fixed charge capacitated network 문제가 되므로 본 문제 또한 NP-hard 문제임을 알 수 있으며, 따라서 본 논문에서는 충분히 빠른 시간 안에 큰 문제를 다룰 수 있도록 LP-relaxation과 Lagrangian relaxation을 기초로 하는 두 가지 휴리스틱을 제안하고 있다. 제안된 두 휴리스틱의 성능 평가를 위해 여러 알려진 layout들과 임의로 생성한 layout을 이용하여 다양한 조건하에서 실험을 수행하였고 그 결과 빠른 시간 내에 좋은 해를 찾을 수 있었다. 두 휴리스틱중에서는 LP-relaxation을 이용한 휴리스틱보다 Lagrangian relaxation을 이용한 휴리스틱이 더 좋은 해를 주는 것으로 나타났다.
