Article ID: | iaor1998787 |
Country: | United Kingdom |
Volume: | 24 |
Issue: | 9 |
Start Page Number: | 849 |
End Page Number: | 860 |
Publication Date: | Sep 1997 |
Journal: | Computers and Operations Research |
Authors: | Kim Sehun, Chang Kun-Nyeong |
Keywords: | heuristics, lagrange multipliers |
In this article, two efficient heuristic algorithms are suggested for the channel allocation problem which minimizes the average blocking probability of the whole network subject to the co-channel, adjacent-site and co-site interference constraints, given the number of available channels. We convert this problem into a convenient form using the piecewise linearization technique and the concept of pattern, and apply Lagrangean relaxation and subgradient optimization techniques. Computational experiments show that this procedure provides high-quality solutions with information about their error ranges for networks with special compatibility matrices. We also suggest a general procedure using a GOS (grade of service) updating scheme, and provide encouraging computational results.