Approach To Shortwave Radio Broadcast Resource Allocation

Shortwave radio broadcasting is the principal way for broadcasting of voice in many countries,such as China.An important problem in shortwave radio broadcasting is how to allocate transmission devices to radio programs,so that all radio programs are broadcasted properly and the overall broadcasting effect is optimized.The broadcasting effect of a program is determined by various factors,such as time,location,and device parameters.There are also restrictions on the usage of transmission devices.Currently,the radio programs are managed by staff members manually.This is not efficient,and it is also error-prone.Since the search space of the problem is extremely huge,the staff members have no choice but to rely heavily on previous allocation plans,which are becoming obsolete with the change of programs and devices.In this paper,we describe the allocation of shortwave radio broadcast resources as a constrained optimization problem and prove that it is NP-hard.A Pseudo-Boolean constraint formulation and a Weighted Partial MaxSAT(maximum satisfiability)formulation for the problem are presented.We also propose a GRASP and a GRASP-CHCC local search algorithm to solve the problem.All methods are evaluated using real data.The Weighted Partial MaxSAT solver can provide the optimal value on few small instances.The CPLEX and clasp solver can provide the optimal value on most small instances.The local search solver can reach the optimal value for most instances.Experimental results suggest that we can find an allocation plan with good broadcasting effect quite efficiently.