Journal
SCIENCE CHINA-INFORMATION SCIENCES
Volume 62, Issue 7, Pages -Publisher
SCIENCE PRESS
DOI: 10.1007/s11432-017-9324-0
Keywords
radio broadcast scheduling; branch-and-bound algorithm; constrained maximum weighted bipartite matching; Kuhn-Munkres algorithm; strategy combinations
Funding
- National Natural Science Foundation of China [61772503]
- National Basic Research Program of China [2014CB340302]
Ask authors/readers for more resources
Given a set of radio broadcast programs, the radio broadcast scheduling problem is to allocate a set of devices to transmit the programs to achieve the optimal sound quality. In this article, we propose a complete algorithm to solve the problem, which is based on a branch-and-bound (BnB) algorithm. We formulate the problem with a new model, called constrained maximum weighted bipartite matching (CMBM), i.e., the maximum matching problem on a weighted bipartite graph with constraints. For the reduced matching problem, we propose a novel BnB algorithm by introducing three new strategies, including the highest quality first, the least conflict first and the more edge first. We also establish an upper bound estimating function for pruning the search space of the algorithm. The experimental results show that our new algorithm can quickly find the optimal solution for the radio broadcast scheduling problem at small scales, and has higher scalability for the problems at large scales than the existing complete algorithm.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available