This thesis examines a special case of the assignment problem where two different types of facilities are paired to process a set of jobs. Each job consists of two operations characterized by the type of facilities employed, and the importance of one type facilities dominates that of the other in determining the performance of each job.
Given two sets of each type facilities, we attempt to find a mapping from one set to the other which maximizes the performance of this system.
Some assumptions and definitions are made to reduce the complexity of our problem.
Our mathematical formulation takes a form of LP (linear programming) problem, but the cost coefficients are not known. Since the estimation of the cost coefficients entails difficult problems, the solution of this problem using available LP algorithms is not efficient. We settle such a difficulty by breaking our problem up into a set of subproblems and by assuming the hierarchically leveled structure of cost function.
On the basis of this reasoning, we develop a systematic algorithm and show some applicable areas of it. A numerical example is provided to illustrate the solution process of our algorithm. Finally we make some comments on both the algorithm and its extensions.
이 논문은 두가지 형태의 설비들이 짝을 지어 다수의 job를 수행하는, 배정문제의 특수한 경우를 다루고 있다.
각 job들은 두 단계의 작업들로 이루어지고, 대상 작업의 단계에 따라 투입되는 설비의 형태가 구별되며, 각 job들의 성취도를 결정짓는 데는, 첫 단계 작업에 쓰이는 형태의 설비의 중요성이 다른 설비보다 매우 크다고 가정하고 있다.
이 논문의 목적은, 두가지 형태의 설비들의 set이 주어졌을 때, 전체 job들의 성취도를 최대화 해주는, 한 set에서 다른 set으로의 Mapping을 찾는 것이다.
이 논문의 구성은 대상문제를 설명하고, 이 문제의 수식화가 가능하도록 몇가지 기본적인 가정과 정의를 부가하였으며, 이를 기초로 LP형태의 기본 Model을 제시하였고, 이 기본 Model이 갖는 문제점의 해결을 위해, 비용함수의 특수구조를 이용하여 Model의 수식을 몇가지 subproblem들로 나누어 푸는 단계적인 해법을 제시하였다.
그리고 풀이 과정의 이해를 돕기 위한 예제를 추가하였고, 이 해법의 적용 대상범위를 제시하였으며, 이 해법이 갖는 장점과 문제점에 대해 설명하였다.
