• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Chen, Chuandong (Chen, Chuandong.) [1] | Lin, Dishi (Lin, Dishi.) [2] | Wei, Rongshan (Wei, Rongshan.) [3] | Liu, Qinghai (Liu, Qinghai.) [4] | Zhu, Ziran (Zhu, Ziran.) [5] | Chen, Jianli (Chen, Jianli.) [6]

Indexed by:

EI

Abstract:

Ordered Escape Routing (OER) problem, which is an NP-hard problem, is critical in PCB design. Primary methods based on integer linear programming (ILP) or heuristic algorithms work well on small-scale PCBs with fewer pins. However, when dealing with large-scale instances, the performance of ILP strategies suffers dramatically as the number of variables increases due to time-consuming preprocessing. As for heuristic algorithms, ripping-up and rerouting is adopted to increase resource utilization, which frequently causes time violation. In this paper, we propose an efficient ILP-based routing engine for dense PCB to simultaneously minimize wiring length and runtime, considering the specific routing constraints. By weighting the length, we first model the OER problem as a special network flow problem. Then we separate the non-crossing constraint from typical ILP modeling to reduce the number of integral variables greatly. In addition, considering the congestion of routing resources, the ILP method is proposed to detect congestion. Finally, unlike the traditional schemes that deal with negotiated congestion, our approach works by reducing the local area capacity and then allowing the global automatic optimization of congestion. Compared with the state-of-the-art work, experimental results show that our algorithm can solve cases in larger scale in high routing quality of less length and reduce routing time by 76%. © 2023 Copyright held by the owner/author(s).

Keyword:

Computational complexity Global optimization Heuristic algorithms Heuristic methods Integer programming Organic pollutants Polychlorinated biphenyls

Community:

  • [ 1 ] [Chen, Chuandong]Fuzhou University, Fuzhou, China
  • [ 2 ] [Lin, Dishi]Fuzhou University, Fuzhou, China
  • [ 3 ] [Wei, Rongshan]Fuzhou University, Fuzhou, China
  • [ 4 ] [Liu, Qinghai]Fuzhou University, Fuzhou, China
  • [ 5 ] [Zhu, Ziran]Southeast University, Nanjing, China
  • [ 6 ] [Chen, Jianli]Fudan University, Shanghai, China

Reprint 's Address:

Email:

Show more details

Related Keywords:

Related Article:

Source :

Year: 2023

Page: 535-540

Language: English

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 0

Affiliated Colleges:

Online/Total:150/9652966
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1