期刊
IEEE ACCESS
卷 7, 期 -, 页码 98436-98452出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/ACCESS.2019.2929410
关键词
Combinatorial optimization; cyclic bandwidth minimization; multiple neighborhood search; threshold-based search; extended evaluation function
资金
- China Scholarship Council [201608070103]
- Mexican Secretariat of Public Education through SEP-CINVESTAV [00114]
The cyclic bandwidth problem (CBP) was initially introduced in the context of designing ring interconnection networks and has a number of other relevant applications, such as the design of computer networks and minimization of wire lengths in VLSI layout. However, the problem is computationally challenging since it belongs to the class of NP-hard problems. Existing studies on the CBP mainly focus on theoretical issues, and there are still very few practical methods devoted to this important problem. This paper fills the gap by introducing an iterated three-phase search approach for solving the CBP effectively. The proposed algorithm relies on three complementary search components to ensure a suitable balance of search intensification and diversification, guided by an enriched evaluation function. Computational assessments on a test-suite of 113 popular benchmark instances in the literature demonstrate the effectiveness of the proposed algorithm. In particular, it improves on 19 best-known computational results of the current best-performing algorithm for the problem and discovers 12 new record results (updated upper bounds). The key components of the proposed algorithm are investigated to shed light on their influences over the performance of the algorithm.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据