This thesis is concerned with the channel assignment for the design of cellular mobile communication systems. Our first model is an optimal channel assignment problem which minimize the weighted average blocking probability subject to only co-channel interference constraints. The problem is converted into al linear mixed integer problem. We apply a Lagrangean relaxation procedure to the mixed integer problem to obtain lower bounds and feasible solutions. Computational experiments show that our method found high-quality solutions with information about meaningful error ranges. In second model, we consider an optimal channel assignment problem which minimize the span of frequencies required subject to generalized constraints. For this problem, we suggeste a heuristic algorithm for the minimum span problem. And the computational experiment is performed with the algorithm and comparisons are made with the existing algorithms. The result show that our algorithm is superior over the existing algorithms in all the problems tested. We apply this algorithm successfully to the problem which minimize the weighted average blocking probability.
이 논문은 이동통신시스템의 채널 할당문제를 다루었다. 첫번째 모델에 서는 코-채널 간섭제약만 고려해서 가중평균화된 손실율을 최소화하는 최적 채널할당문제를 다루었다. 이 문제는 선형 혼합 정수 계획 문제로 바뀔수 있다. 이 문제에 라그랑쥐 완화 과정을 적용하여서 이 문제의 하한과 가능 해를 구하였다. 계산 결과 위 방법이 좋은 해는 물론 에러 범위에 관해 의미있는 정보를 제공하였다. 두번째 모델에서는 모든 간섭제약을 고려해서 주파수 스팬을 최소화하는 최적채널할당 문제를 다루었다. 이 문제에 대해 하나의 휴리스틱 알고리즘을 개발하였다. 이 알고리즘과 현존하는 여러 알고리즘을 구현하여 비교하였다. 계산 결과 이 논문에서 개발한 알고리즘이 시험된 모든 알고리즘보다 좋은 결과를 나타냈다. 마지막으로 이 알고리즘을 가중평균화된 손실율을 최소화하는 문제에 적용할수 있도록 성공적으로 바꾸었다.
