Simulated Annealing Technique for Routing in a Rectangular Mesh Network
In the process of automatic design for printed circuit boards (PCBs), the phase following cell placement is routing. On the other hand, routing process is a notoriously difficult problem, and even the simplest routing problem which consists of a set of two-pin nets is known to be NP-complete. In thi...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2014-01-01
|
| Series: | Modelling and Simulation in Engineering |
| Online Access: | http://dx.doi.org/10.1155/2014/127359 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832556935696613376 |
|---|---|
| author | Noraziah Adzhar Shaharuddin Salleh |
| author_facet | Noraziah Adzhar Shaharuddin Salleh |
| author_sort | Noraziah Adzhar |
| collection | DOAJ |
| description | In the process of automatic design for printed circuit boards (PCBs), the phase following cell placement is routing. On the other hand, routing process is a notoriously difficult problem, and even the simplest routing problem which consists of a set of two-pin nets is known to be NP-complete. In this research, our routing region is first tessellated into a uniform Nx×Ny array of square cells. The ultimate goal for a routing problem is to achieve complete automatic routing with minimal need for any manual intervention. Therefore, shortest path for all connections needs to be established. While classical Dijkstra’s algorithm guarantees to find shortest path for a single net, each routed net will form obstacles for later paths. This will add complexities to route later nets and make its routing longer than the optimal path or sometimes impossible to complete. Today’s sequential routing often applies heuristic method to further refine the solution. Through this process, all nets will be rerouted in different order to improve the quality of routing. Because of this, we are motivated to apply simulated annealing, one of the metaheuristic methods to our routing model to produce better candidates of sequence. |
| format | Article |
| id | doaj-art-0ca27968212b442a9f16dd8bf697e3c2 |
| institution | Kabale University |
| issn | 1687-5591 1687-5605 |
| language | English |
| publishDate | 2014-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Modelling and Simulation in Engineering |
| spelling | doaj-art-0ca27968212b442a9f16dd8bf697e3c22025-02-03T05:43:58ZengWileyModelling and Simulation in Engineering1687-55911687-56052014-01-01201410.1155/2014/127359127359Simulated Annealing Technique for Routing in a Rectangular Mesh NetworkNoraziah Adzhar0Shaharuddin Salleh1Department of Mathematical Sciences, Faculty of Science, Universiti Teknologi Malaysia (UTM), 81310 Johor Bahru, Johor, MalaysiaDepartment of Mathematical Sciences, Faculty of Science, Universiti Teknologi Malaysia (UTM), 81310 Johor Bahru, Johor, MalaysiaIn the process of automatic design for printed circuit boards (PCBs), the phase following cell placement is routing. On the other hand, routing process is a notoriously difficult problem, and even the simplest routing problem which consists of a set of two-pin nets is known to be NP-complete. In this research, our routing region is first tessellated into a uniform Nx×Ny array of square cells. The ultimate goal for a routing problem is to achieve complete automatic routing with minimal need for any manual intervention. Therefore, shortest path for all connections needs to be established. While classical Dijkstra’s algorithm guarantees to find shortest path for a single net, each routed net will form obstacles for later paths. This will add complexities to route later nets and make its routing longer than the optimal path or sometimes impossible to complete. Today’s sequential routing often applies heuristic method to further refine the solution. Through this process, all nets will be rerouted in different order to improve the quality of routing. Because of this, we are motivated to apply simulated annealing, one of the metaheuristic methods to our routing model to produce better candidates of sequence.http://dx.doi.org/10.1155/2014/127359 |
| spellingShingle | Noraziah Adzhar Shaharuddin Salleh Simulated Annealing Technique for Routing in a Rectangular Mesh Network Modelling and Simulation in Engineering |
| title | Simulated Annealing Technique for Routing in a Rectangular Mesh Network |
| title_full | Simulated Annealing Technique for Routing in a Rectangular Mesh Network |
| title_fullStr | Simulated Annealing Technique for Routing in a Rectangular Mesh Network |
| title_full_unstemmed | Simulated Annealing Technique for Routing in a Rectangular Mesh Network |
| title_short | Simulated Annealing Technique for Routing in a Rectangular Mesh Network |
| title_sort | simulated annealing technique for routing in a rectangular mesh network |
| url | http://dx.doi.org/10.1155/2014/127359 |
| work_keys_str_mv | AT noraziahadzhar simulatedannealingtechniqueforroutinginarectangularmeshnetwork AT shaharuddinsalleh simulatedannealingtechniqueforroutinginarectangularmeshnetwork |