关键词: 放置问题, 禁忌搜索, 搜索域, 图状网络

Abstract: This service facility placement problem is investigated, which appears representatively in fog computing for the cost minimization and the optimal resource utilization. After the problem being modelled as a (p+m)-median problem, a novel heuristic placement algorithm is proposed that combines the greedy and tabu-search strategies. The proposed algorithm can be used in networks with arbitrary topology and random demand distribution. Analysis results show that it is polynomial in time complexity and can reach the optimal performance in the case that the number of the extended service nodes in the network is equal to that of the request nodes. Finally, simulations verify the advantages above.

Key words: placement problem, tabu-search, search domain, graph network