새로운 p-median 모델을 이용한 셀 생산시스템 디자인

Cellular Manufacturing System Design using New p-median Models

본 논문에서는 그룹테크놀러지 생산시스템에서 기계 셀 형성문제를 푸는 새로운 p-median 모델을 제시한다. 기계 셀 형성문제를 푸는 방법론으로서 p-median 모델은 성과가 좋다는 것이 알려져 있지만 기존의 p-median 모델은 적어도 세 가지 점에서 한계가 있다. 첫째, 셀 형성 문제는 NP-complete이므로 문제를 푸는데 계산시간이 매우 많이 소요된다. 둘째, 기존의 p-median 모델은 이진변수가 많이 필요하므로 중규모 이하의 셀 형성문제에만 적용가능하다. 셋째, 기존의 p-median 모델은 컴퓨터에서 모델을 빨리 실행할 수 있는 별도의 수단이 없다. 이로 인해 기존의 p-median 모델을 대규모 셀 형성문제에 적용하는 데는 한계가 있다. 본 논문에서 제시하는 p-median 모델은 빠른 계산시간 내에 대규모 셀 형성문제를 풀 수 있다는 점에서 기존의 p-median 모델보다 효과적이다. 모델을 실행하는 동안 메디안으로 선정되는 기계에 대한 선택정보를 전혀 활용하지 않는 기존의 p-median 모델과는 달리, 본 논문에서 제시하는 p-median 모델에서는 메디안후보 기계집합을 도입하여 실행 초기부터 메디안으로 선정되는 기계에 대한 선택정보를 활용한다. 더 나아가서 이진변수가 줄어든 p-median 모델을 제시한다. 이 모델은 연속변수나 제약식을 추가로 필요로 하지 않는다. 문헌에서 이용 가능한 큰 사이즈의 데이터들을 가지고 기존의 p-median 모델과 비교계산해 본 결과 본 논문에서 제시한 p-median 모델의 성과가 좋음을 발견하였다.

This paper proposes new p-median mathematical formulations for solving the cell formation (CF) problem in group technology manufacturing. In spite of its successful applications to CF problems that have ever been reported in literature, existing p-median formulations have critical limitations for at least three reasons. First, since CF problem is NP-complete, it takes enormous amount of computation time to solve the problem optimally. Second, existing p-median formulations can solve small to medium-sized CF problems since they require too many binary variables. Some of modified p-median formulations require extra continuous variables and constraints at the cost of decreased binary variables. Third, existing p-median formulations suggest no efficient schemes for implementation of the formulations. These limitations discourage cell designer to apply existing p-median formulations to large-size CF problems. Our modified p-median formulations have fundamental advantages over existing p-median formulations in the sense that they can be applied to large-size CF problems within short computer runtime. Unlike existing p-median formulations which do not utilize any information of the median machines throughout the implementation procedure, our modified p-median formulations introduce the candidate set of median machines so that the models can utilize the information of the median machines from the beginning of implementation procedure. This leads to much speedier implementation of model. Furthermore, we develop an alternative p-median formulation which requires less number of binary variables. Our p-median formulations need no extra continuous variables and constraints. Computational results with medium- to large-size data sets available in literature compare our p-median formulations favorably.