This paper presents a new heuristic method for quickly finding a good feasible solution to the channel assignment problem
(CAP). Like many other greedy-type heuristics for CAP, the proposed method also assigns a frequency to a call, one at a time.
Hence, the method requires computational time that increases only linear to the number of calls. However, what distinguishes
the method from others is that it starts with a narrow enough frequency band so as to provoke violations of constraints that
we need to comply with in order to avoid radio interference. Each violation is then resolved by inserting frequencies at the
most appropriate positions so that the band of frequencies expands minimally. An extensive computational experiment using
a set of randomly generated problems as well as the Philadelphia benchmark instances shows that the proposed method perform
statistically better than existing methods of its kind and even yields optimum solutions to most of Philadelphia benchmark
instances among which two cases are reported for the first time ever, in this paper.
Won-Young Shin was born in Busan, Korea in 1978. He received B.S. in industrial engineering from Pohang University of Science and Technology
(POSTECH) in 2001 and M.S in operation research and applied statistics from POSTECH in 2003. Since 2003 he has been a researcher
of Agency for Defense Development (ADD) in Korea. He is interested in optimization of communication system and applied statistics.
Soo Y. Chang is an associate professor in the Department of Industrial Engineering at Pohang University of Science and Technology (POSTECH),
Pohang, Korea. He teaches linear programming, discrete optimization, network flows and operations research courses. His research
interests include mathematical programming and scheduling. He has published in several journals including Discrete Applied
Mathematics, Computers and Mathematics with Application, IIE Transactions, International Journal of Production Research, and
so on. He is a member of Korean IIE, and ORMSS.
Jaewook Lee is an assistant professor in the Department of Industrial Engineering at Pohang University of Science and Technology (POSTECH),
Pohang, Korea. He received the B.S. degree in mathematics with honors from Seoul National University, and the Ph.D. degree
from Cornell University in applied mathematics in 1993 and 1999, respectively. He is currently an assistant professor in the
department of industrial engineering at the Pohang University of Science and Technology (POSTECH). His research interests
include nonlinear systems, neural networks, nonlinear optimization, and their applications to data mining and financial engineering.
Chi-Hyuck Jun was born in Seoul, Korea in 1954. He received B.S. in mineral and petroleum engineering from Seoul National University in
1977, M.S. in industrial engineering from Korea Advanced Institute of Science and Technology in 1979 and Ph.D. in operations
research from University of California, Berkeley, in 1986. Since 1987 he has been with the department of industrial engineering,
Pohang University of Science and Technology (POSTECH) and he is now a professor and the department head. He is interested
in performance analysis of communication and production systems. He has published in several journals including IIE Transactions,
IEEE Transactions, Queueing Systems and Chemometrics and Intelligent Laboratory Systems. He is a member of IEEE, INFORMS and
ASQ.
相似文献