Solving multi-objective constrained minimum weighted bipartite assignment problem:a case study on energy-aware radio broadcast scheduling  

作　　者：Yupeng ZHOU Mingjie FAN Feifei MA Minghao YIN 

机构地区：[1]College of Information Science and Technology,Northeast Normal University,Changchun 130117,China [2]Laboratory of Parallel Software and Computational Science,Institute of Software Chinese Academy of Sciences,Beijing 100190,China [3]State Key laboratory of Computer Science,Institute of Software Chinese Academy of Sciences,Beijing 100190,China

出　　处：《Science China(Information Sciences)》2022年第8期19-34,共16页中国科学（信息科学）（英文版）

摘　　要：This paper proposes a multi-objective constrained minimum weighted bipartite assignment problem(MCMWBAP),which is considered an extension of the classical bipartite matching problem(BMP).We first provide the formulation of the MCMWBAP and prove that it is an NP-hard combinatorial optimization problem.Based on this formulation,multi-objective energy-aware shortwave radio broadcast resource allocation problem(MSRBRAP)application is studied.The goal of this problem is to allocate radio programs to transmission devices to broadcast all radio programs felicitously with a maximized objective of total qualified monitoring sites and a minimized objective of energy consumption.Then,a novel multi-objective hybrid evolutionary algorithm(MOHEA),which is integrated with push and pull initialization,the dynamic resource allocation strategy,and the aggregate local search procedure,is developed to solve the problem.The proposed method is evaluated using two categories of benchmarks for MCMWBAP together with a real scenario case study for MSRBRAP.Furthermore,the key components of MOHEA are analyzed,and the experimental results demonstrate that MOHEA outperforms two classical multi-objective evolutionary algorithms(NSGA-II and MOEA/D),improving working efficiency.

关 键 词：constrained minimum weighted bipartite assignment multi-objective energy-aware radio broadcast scheduling evolutionary algorithms dynamic resource allocation aggregate local search 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]