IEICE TRANSACTIONS on Fundamentals
An Improved Method of Convex Rectilinear Block Packing Based on Sequence-Pair
Summary :
In this paper, for convex rectilinear block packing problem, we propose 1) a novel algorithm to obtain a packing based on a given sequence-pair in O(n2) time (conventional method needs O(n3) time), where n is the number of rectangle sub-blocks made from convex blocks, 2) a move operation for Simulated Annealing which is symmetric and can guarantee reachability for the first time, and 3) a method to generate a random adjacent sequence-pair in O(n2) time. By using 1), 2) and 3) together, the time complexity of the inner loop in Simulated Annealing becomes surely O(n2) time. Experimental results show that the proposed algorithm is faster than the conventional ones in practical and the wire length as well as packing area is taken into consideration in the proposed method.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E86-A No.12 pp.3148-3157
- Publication Date
- 2003/12/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
- Category
- Place and Routing
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Kazuya WAKATA, Hiroaki SAITO, Kunihiro FUJIYOSHI, Keishi SAKANUSHI, Takayuki OBATA, Chikaaki KODAMA, "An Improved Method of Convex Rectilinear Block Packing Based on Sequence-Pair" in IEICE TRANSACTIONS on Fundamentals,
vol. E86-A, no. 12, pp. 3148-3157, December 2003, doi: .
Abstract: In this paper, for convex rectilinear block packing problem, we propose 1) a novel algorithm to obtain a packing based on a given sequence-pair in O(n2) time (conventional method needs O(n3) time), where n is the number of rectangle sub-blocks made from convex blocks, 2) a move operation for Simulated Annealing which is symmetric and can guarantee reachability for the first time, and 3) a method to generate a random adjacent sequence-pair in O(n2) time. By using 1), 2) and 3) together, the time complexity of the inner loop in Simulated Annealing becomes surely O(n2) time. Experimental results show that the proposed algorithm is faster than the conventional ones in practical and the wire length as well as packing area is taken into consideration in the proposed method.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e86-a_12_3148/_p
Copy
@ARTICLE{e86-a_12_3148,
author={Kazuya WAKATA, Hiroaki SAITO, Kunihiro FUJIYOSHI, Keishi SAKANUSHI, Takayuki OBATA, Chikaaki KODAMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Improved Method of Convex Rectilinear Block Packing Based on Sequence-Pair},
year={2003},
volume={E86-A},
number={12},
pages={3148-3157},
abstract={In this paper, for convex rectilinear block packing problem, we propose 1) a novel algorithm to obtain a packing based on a given sequence-pair in O(n2) time (conventional method needs O(n3) time), where n is the number of rectangle sub-blocks made from convex blocks, 2) a move operation for Simulated Annealing which is symmetric and can guarantee reachability for the first time, and 3) a method to generate a random adjacent sequence-pair in O(n2) time. By using 1), 2) and 3) together, the time complexity of the inner loop in Simulated Annealing becomes surely O(n2) time. Experimental results show that the proposed algorithm is faster than the conventional ones in practical and the wire length as well as packing area is taken into consideration in the proposed method.},
keywords={},
doi={},
ISSN={},
month={December},}
Copy
TY - JOUR
TI - An Improved Method of Convex Rectilinear Block Packing Based on Sequence-Pair
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 3148
EP - 3157
AU - Kazuya WAKATA
AU - Hiroaki SAITO
AU - Kunihiro FUJIYOSHI
AU - Keishi SAKANUSHI
AU - Takayuki OBATA
AU - Chikaaki KODAMA
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E86-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2003
AB - In this paper, for convex rectilinear block packing problem, we propose 1) a novel algorithm to obtain a packing based on a given sequence-pair in O(n2) time (conventional method needs O(n3) time), where n is the number of rectangle sub-blocks made from convex blocks, 2) a move operation for Simulated Annealing which is symmetric and can guarantee reachability for the first time, and 3) a method to generate a random adjacent sequence-pair in O(n2) time. By using 1), 2) and 3) together, the time complexity of the inner loop in Simulated Annealing becomes surely O(n2) time. Experimental results show that the proposed algorithm is faster than the conventional ones in practical and the wire length as well as packing area is taken into consideration in the proposed method.
ER -
English
