This thesis considers a facility location problem, which is concerned with locating facilities on a supply chain network and installing the associated equipments at the facilities to meet a given set of demands. These facilities include industrial plants, warehouses, and computing facilities in computer network systems. The objective is to minimize the sum of setup cost (facility opening cost and equipment installation cost), operation cost, and distribution cost. For the equipments, various choices of equipment modes are considered to select the best mode. Moreover, overwork is allowed at each facility but at expensive operation cost. The proposed problem is characterized as being an NP-hard problem, so that a Lagrangean relaxation based heuristic algorithm is derived. In order to evaluate the performance of the proposed algorithm, computational experiments with various numerical instances are conducted. The experiments show that the proposed algorithm gives good quality solutions within reasonable time.
본 논문에서는 공급체인망에서 주어진 수요를 만족시키기 위해서 시설들의 입지를 선정하고 각 시설에 장비를 설치하는 문제를 다루고 있다. 본 문제에서 다루는 시설들로 생산공장이나 대형보관소, 컴퓨터 네트워크 시스템의 설비 등이 적용 가능하다, 고정설치비용(시설 개설비용과 장비설치비용)과 생산비용, 운송비용의 총 합을 최소화하는 것을 목적함수로 한다. 각 시설마다 서로 다른 생산용량을 가진 다양한 장비에 대한 장비설치를 결정하여야 하며, 인상된 단위 생산비용에 한하여 추가작업이 허용된다. 본 논문의 문제는 NP-hard 문제이기 때문에 Lagrangean Relaxation을 이용한 휴리스틱 알고리즘이 구현되었다. 이 알고리즘을 다양한 문제에 대하여 실험하고 평가한 결과, 제안된 알고리즘이 수긍할 만한 시간 안에 효율적으로 최적해를 도출함을 보여주었다.