JPH09108933A - 素材の配置および切り出し方法 - Google Patents
素材の配置および切り出し方法Info
- Publication number
- JPH09108933A JPH09108933A JP7293798A JP29379895A JPH09108933A JP H09108933 A JPH09108933 A JP H09108933A JP 7293798 A JP7293798 A JP 7293798A JP 29379895 A JP29379895 A JP 29379895A JP H09108933 A JPH09108933 A JP H09108933A
- Authority
- JP
- Japan
- Prior art keywords
- horizontal
- vertical
- grid
- section
- lines
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Ceased
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F30/00—Computer-aided design [CAD]
- G06F30/30—Circuit design
- G06F30/39—Circuit design at the physical level
- G06F30/392—Floor-planning or layout, e.g. partitioning or placement
-
- H—ELECTRICITY
- H05—ELECTRIC TECHNIQUES NOT OTHERWISE PROVIDED FOR
- H05K—PRINTED CIRCUITS; CASINGS OR CONSTRUCTIONAL DETAILS OF ELECTRIC APPARATUS; MANUFACTURE OF ASSEMBLAGES OF ELECTRICAL COMPONENTS
- H05K3/00—Apparatus or processes for manufacturing printed circuits
- H05K3/0097—Processing two or more printed circuits simultaneously, e.g. made from a common substrate, or temporarily stacked circuit boards
Landscapes
- Engineering & Computer Science (AREA)
- Computer Hardware Design (AREA)
- Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Architecture (AREA)
- Evolutionary Computation (AREA)
- Geometry (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Packaging Frangible Articles (AREA)
Abstract
(57)【要約】
【課 題】 素材を配置することができる最小の面積
を、系統立てて探すことができる素材の配置および切り
出し方法を提供すること。 【解決手段】 素材の配置方法は、下記第１工程ないし
第４工程からなっている。素材の数よりも多い区画を有
する格子（Ａ）を描く第１工程。なお、この格子は、隣
接する左右２区画に渡る横線と、隣接する上下２区画に
わたる縦線とを複数用いて描かれている。第１工程で描
かれた区画に矩形の素材（mi) を配置する第２工程。区
画内の素材の縦方向の長さを確保した状態で、縦線
（Ｌ）を縮めて、横線（Ｂ）を格子の上辺または下辺に
近づける第３工程。区画内の素材の横方向の長さを確保
した状態で、横線を縮めて、縦線を格子の左辺または右
辺に近づける第４工程。
を、系統立てて探すことができる素材の配置および切り
出し方法を提供すること。 【解決手段】 素材の配置方法は、下記第１工程ないし
第４工程からなっている。素材の数よりも多い区画を有
する格子（Ａ）を描く第１工程。なお、この格子は、隣
接する左右２区画に渡る横線と、隣接する上下２区画に
わたる縦線とを複数用いて描かれている。第１工程で描
かれた区画に矩形の素材（mi) を配置する第２工程。区
画内の素材の縦方向の長さを確保した状態で、縦線
（Ｌ）を縮めて、横線（Ｂ）を格子の上辺または下辺に
近づける第３工程。区画内の素材の横方向の長さを確保
した状態で、横線を縮めて、縦線を格子の左辺または右
辺に近づける第４工程。
Description
【０００１】
【発明の属する技術分野】本発明は、複数の素材を基材
や容器に配置する方法および、基材から複数の素材を切
り出す方法に関する。
や容器に配置する方法および、基材から複数の素材を切
り出す方法に関する。
【０００２】
【従来の技術】この種の素材の配置および切り出し方法
は、たとえば、半導体集積回路やプリント配線基板の配
置設計工程、および、鋼板や布地などの平面基材から各
種大きさの複数の部材を切り出す工程などに用いられて
いる。
は、たとえば、半導体集積回路やプリント配線基板の配
置設計工程、および、鋼板や布地などの平面基材から各
種大きさの複数の部材を切り出す工程などに用いられて
いる。
【０００３】ところで、素材の配置および切り出しにお
いては、できるだけ小さな基材を用いることができれ
ば、製造コストを低下させたり、素材が配列されている
製品の性能を向上させたりすることができる。
いては、できるだけ小さな基材を用いることができれ
ば、製造コストを低下させたり、素材が配列されている
製品の性能を向上させたりすることができる。
【０００４】そこで、図８を用いて、従来の素材の配置
および切り出し方法における素材の配置の決定方法を説
明する。図８は素材の配置の決定方法を説明するための
説明図で、（ａ）は素材が分散している状態の図、
（ｂ）は素材が集結している状態の図である。
および切り出し方法における素材の配置の決定方法を説
明する。図８は素材の配置の決定方法を説明するための
説明図で、（ａ）は素材が分散している状態の図、
（ｂ）は素材が集結している状態の図である。
【０００５】図８（ａ）には、各種大きさの素材miが図
示されている。この素材miの総面積よりも少し大きな面
積を有する矩形の基材Ｋを想定し、この基材Ｋの外縁す
なわち矩形の枠Ｗを、図８（ｂ）に図示するように描
く。そして、この枠Ｗ内に、全ての素材miが重ならない
ように嵌まり込む必要がある。
示されている。この素材miの総面積よりも少し大きな面
積を有する矩形の基材Ｋを想定し、この基材Ｋの外縁す
なわち矩形の枠Ｗを、図８（ｂ）に図示するように描
く。そして、この枠Ｗ内に、全ての素材miが重ならない
ように嵌まり込む必要がある。
【０００６】この嵌め込み方法には、種々の方法が存在
するが、代表的な例としては、まず初めに、枠Ｗに一番
大きな素材miを嵌め込み、次いで２番目に大きな素材mi
を嵌め込んでいくというように、大きな素材miの順に嵌
め込んでいく方法がある。全部の素材miが嵌まり込めば
問題ないが、嵌まり込まない場合には、素材miの配置を
変更して嵌め込み直す。この様に試行錯誤をして、どう
しても嵌め込むことが不可能な場合には、もう少し大き
な枠Ｗを用意して再度行う。この様にして、素材miを全
て嵌め込むことができる最小の枠Ｗを捜し出す。
するが、代表的な例としては、まず初めに、枠Ｗに一番
大きな素材miを嵌め込み、次いで２番目に大きな素材mi
を嵌め込んでいくというように、大きな素材miの順に嵌
め込んでいく方法がある。全部の素材miが嵌まり込めば
問題ないが、嵌まり込まない場合には、素材miの配置を
変更して嵌め込み直す。この様に試行錯誤をして、どう
しても嵌め込むことが不可能な場合には、もう少し大き
な枠Ｗを用意して再度行う。この様にして、素材miを全
て嵌め込むことができる最小の枠Ｗを捜し出す。
【０００７】
【発明が解決しようとする課題】ところで、図８（ｂ）
において、素材mi同士の位置を互いに変更する際に、位
置を交換する素材mi同士（たとば素材m7と素材m8) が略
同じ大きさの場合には、素材miが位置の変更をしても、
他の素材mi（素材m7と素材m8以外の素材）は余り位置を
変更する必要がない。したがって、配置の変更を繰り返
しても、どの様に配置を変更したかを管理することがで
きる。しかしながら、位置を交換する素材mi同士（たと
ば素材m7と素材m9) がかなり異なる大きさの場合には、
素材miが位置の変更をすると、他の素材miも大きく位置
を変更する必要がある。したがって、配置の変更を繰り
返すと、どの様に素材miの配置を変更したかを管理する
ことが困難となる。その結果、最小の枠Ｗを系統立てて
捜し出すことが困難である。
において、素材mi同士の位置を互いに変更する際に、位
置を交換する素材mi同士（たとば素材m7と素材m8) が略
同じ大きさの場合には、素材miが位置の変更をしても、
他の素材mi（素材m7と素材m8以外の素材）は余り位置を
変更する必要がない。したがって、配置の変更を繰り返
しても、どの様に配置を変更したかを管理することがで
きる。しかしながら、位置を交換する素材mi同士（たと
ば素材m7と素材m9) がかなり異なる大きさの場合には、
素材miが位置の変更をすると、他の素材miも大きく位置
を変更する必要がある。したがって、配置の変更を繰り
返すと、どの様に素材miの配置を変更したかを管理する
ことが困難となる。その結果、最小の枠Ｗを系統立てて
捜し出すことが困難である。
【０００８】また、提唱されている他の方法において
も、系統立てて行うことが困難であるとともに、膨大な
計算を行う必要がある。
も、系統立てて行うことが困難であるとともに、膨大な
計算を行う必要がある。
【０００９】本発明は、以上のような課題を解決するた
めのもので、素材を配置することができる最小の面積
を、系統立てて探すことができる素材の配置および切り
出し方法を提供することを目的としている。また、素材
を配置することができる最小の面積を、少ない計算量で
捜し出すことができる素材の配置および切り出し方法を
提供することを二次的目的としている。
めのもので、素材を配置することができる最小の面積
を、系統立てて探すことができる素材の配置および切り
出し方法を提供することを目的としている。また、素材
を配置することができる最小の面積を、少ない計算量で
捜し出すことができる素材の配置および切り出し方法を
提供することを二次的目的としている。
【００１０】
【課題を解決するための手段】前記目的を達成するため
に、本発明の素材の配置方法は、複数個の任意の大きさ
の略矩形の素材（mi）を配列し、かつ、下記の第１工程
から第４工程までの工程で構成されている。 １）前記素材の数よりも多い区画を有する格子（Ａ）を
下記のａ，ｂ，ｃの条件のもとで描く第１工程。（な
お、この格子は、実施の形態における素材配置用格子Ａ
に相当し、境界条件用格子Ｃは含まないものである。） ａ．格子周縁の区画を除く格子中央の区画は、隣接する
左右２区画に渡る横線（Ｂ）と、隣接する上下２区画に
わたる縦線（Ｌ）とを複数用いて描かれていること。 ｂ．前記横線の端部は前記縦線の中央部に対向し、ま
た、前記縦線の端部は前記横線の中央部に対向している
こと。 ｃ．格子周縁の区画は、上記ｂの条件を満たした状態
で、可能な限り２区画に渡る横線および縦線で描かれ、
残余の横線および縦線は、１区画のみを横切る横線また
は縦線で描かれていること。
に、本発明の素材の配置方法は、複数個の任意の大きさ
の略矩形の素材（mi）を配列し、かつ、下記の第１工程
から第４工程までの工程で構成されている。 １）前記素材の数よりも多い区画を有する格子（Ａ）を
下記のａ，ｂ，ｃの条件のもとで描く第１工程。（な
お、この格子は、実施の形態における素材配置用格子Ａ
に相当し、境界条件用格子Ｃは含まないものである。） ａ．格子周縁の区画を除く格子中央の区画は、隣接する
左右２区画に渡る横線（Ｂ）と、隣接する上下２区画に
わたる縦線（Ｌ）とを複数用いて描かれていること。 ｂ．前記横線の端部は前記縦線の中央部に対向し、ま
た、前記縦線の端部は前記横線の中央部に対向している
こと。 ｃ．格子周縁の区画は、上記ｂの条件を満たした状態
で、可能な限り２区画に渡る横線および縦線で描かれ、
残余の横線および縦線は、１区画のみを横切る横線また
は縦線で描かれていること。
【００１１】２）第１工程で描かれた区画に前記各素材
を配置する第２工程。 ３）区画内の素材の縦方向の長さを確保した状態で、前
記縦線を縮めて、前記横線を前記格子の上辺または下辺
に近づける第３工程。 ４）区画内の素材の横方向の長さを確保した状態で、前
記横線を縮めて、前記縦線を前記格子の左辺または右辺
に近づける第４工程。
を配置する第２工程。 ３）区画内の素材の縦方向の長さを確保した状態で、前
記縦線を縮めて、前記横線を前記格子の上辺または下辺
に近づける第３工程。 ４）区画内の素材の横方向の長さを確保した状態で、前
記横線を縮めて、前記縦線を前記格子の左辺または右辺
に近づける第４工程。
【００１２】また、前記第２工程における素材の配置を
変更して、再び、前記第３工程から第４工程までの工程
を繰り返す場合がある。
変更して、再び、前記第３工程から第４工程までの工程
を繰り返す場合がある。
【００１３】そして、前記格子の縦および横が、素材の
数を２倍して１減算した数に分割されている場合があ
る。
数を２倍して１減算した数に分割されている場合があ
る。
【００１４】さらに、前記素材が略矩形が合体した形状
であり、この略矩形が合体した形状である素材を略矩形
のパーツ（ａ，ｂ）に分割して、前述と略同様にして、
前記第１工程から第４工程までの工程を行うことがあ
る。この際に、略矩形の素材も存在している時には、こ
の略矩形の素材は一個の略矩形のパーツとなる。
であり、この略矩形が合体した形状である素材を略矩形
のパーツ（ａ，ｂ）に分割して、前述と略同様にして、
前記第１工程から第４工程までの工程を行うことがあ
る。この際に、略矩形の素材も存在している時には、こ
の略矩形の素材は一個の略矩形のパーツとなる。
【００１５】また、前記素材は複数存在するが、その素
材の一部を任意の大きさの矩形の空間（Ｓ）に置き換え
て、前述と略同様にして、前記第１工程から第４工程ま
での工程を行うことがある。
材の一部を任意の大きさの矩形の空間（Ｓ）に置き換え
て、前述と略同様にして、前記第１工程から第４工程ま
での工程を行うことがある。
【００１６】そして、前記素材に代えて、素材切り出し
パターンを配置し、この切り出しパターンに基づいて素
材を切り出す場合がある。
パターンを配置し、この切り出しパターンに基づいて素
材を切り出す場合がある。
【００１７】
【発明の実施の形態】次に、本発明における素材の配置
および切り出し方法の実施の一形態を図１ないし図３を
用いて説明する。図１は本発明における素材の配置およ
び切り出し方法に用いる格子の説明図である。図２は素
材を配置する際の工程を説明するための説明図で、
（ａ）は初期状態の図、（ｂ）は次の段階の図である。
図３は図２の続きの説明図で、（ｃ）は（ｂ）の次の段
階の図、（ｄ）は素材が集結した最終状態の図である。
および切り出し方法の実施の一形態を図１ないし図３を
用いて説明する。図１は本発明における素材の配置およ
び切り出し方法に用いる格子の説明図である。図２は素
材を配置する際の工程を説明するための説明図で、
（ａ）は初期状態の図、（ｂ）は次の段階の図である。
図３は図２の続きの説明図で、（ｃ）は（ｂ）の次の段
階の図、（ｄ）は素材が集結した最終状態の図である。
【００１８】まず第１工程として、図１に図示するよう
な格子を描く。図１において、縦方向に７個で、横方向
に７個の区画を有する、いわゆる７Ｘ７の矩形の格子が
描かれている。この格子の縦線Ｌおよび横線Ｂは、細か
く分断されており、各々２区画分の長さになっており、
この縦線Ｌおよび横線Ｂが各々２区画に渡って配置され
ている。また、横方向において隣接する縦線Ｌ同士は、
位相がずれて配置されており、たとえば区画の左辺が縦
線Ｌの上部で構成されていると、この区画の右辺は隣接
する縦線Ｌの下部で構成されている。同様にして、縦方
向において隣接する横線Ｂ同士は、位相がずれて配置さ
れており、たとえば区画の上辺が横線Ｂの左部で構成さ
れていると、この区画の下辺は隣接する横線Ｂの右部で
構成されている。したがって、横線Ｂの端部は縦線Ｌの
中央部に対向し、一方、縦線Ｌの端部は横線Ｂの中央部
に対向していることになる。
な格子を描く。図１において、縦方向に７個で、横方向
に７個の区画を有する、いわゆる７Ｘ７の矩形の格子が
描かれている。この格子の縦線Ｌおよび横線Ｂは、細か
く分断されており、各々２区画分の長さになっており、
この縦線Ｌおよび横線Ｂが各々２区画に渡って配置され
ている。また、横方向において隣接する縦線Ｌ同士は、
位相がずれて配置されており、たとえば区画の左辺が縦
線Ｌの上部で構成されていると、この区画の右辺は隣接
する縦線Ｌの下部で構成されている。同様にして、縦方
向において隣接する横線Ｂ同士は、位相がずれて配置さ
れており、たとえば区画の上辺が横線Ｂの左部で構成さ
れていると、この区画の下辺は隣接する横線Ｂの右部で
構成されている。したがって、横線Ｂの端部は縦線Ｌの
中央部に対向し、一方、縦線Ｌの端部は横線Ｂの中央部
に対向していることになる。
【００１９】この様にして構成された７Ｘ７の格子は、
中央部の黒く色付けされた素材配置用格子Ａと、この素
材配置用格子Ａの周囲に形成されている境界条件用格子
Ｃとから成っている。したがって、素材配置用格子Ａは
５Ｘ５の格子となっており、その周囲には境界条件用格
子Ｃの区画が配置される。そして、素材配置用格子Ａの
中央部の区画を構成する縦線Ｌおよび横線Ｂは、前述の
ように素材配置用格子Ａの２区画に渡って設けられてい
る。しかしながら、素材配置用格子Ａの周縁部の区画を
構成する縦線Ｌおよび横線Ｂの一部は、境界条件用格子
Ｃの区画に張り出し、素材配置用格子Ａに関しては１区
画のみを横切っている状態で設けられている。
中央部の黒く色付けされた素材配置用格子Ａと、この素
材配置用格子Ａの周囲に形成されている境界条件用格子
Ｃとから成っている。したがって、素材配置用格子Ａは
５Ｘ５の格子となっており、その周囲には境界条件用格
子Ｃの区画が配置される。そして、素材配置用格子Ａの
中央部の区画を構成する縦線Ｌおよび横線Ｂは、前述の
ように素材配置用格子Ａの２区画に渡って設けられてい
る。しかしながら、素材配置用格子Ａの周縁部の区画を
構成する縦線Ｌおよび横線Ｂの一部は、境界条件用格子
Ｃの区画に張り出し、素材配置用格子Ａに関しては１区
画のみを横切っている状態で設けられている。
【００２０】次いで、第２工程として、この様に構成さ
れた素材配置用格子Ａに、任意の大きさの矩形の素材mi
を複数配置する。この配置の方法を図２において説明す
る。図２においては、説明が簡単な様に３Ｘ３の素材配
置用格子Ａを用いる。そして、図２（ａ）に図示するよ
うに、この素材配置用格子Ａに６個の素材miを適宜配置
する。この配置は適当に行えば良いが、最小の面積に配
置できそうな配置を推定して行うことや、電算機で乱数
表を用いて並べることも可能である。ただし、各素材mi
は１個の区画に配置され、同じ素材miが、２か所の区画
に配置されることはない。また、１個の区画には１個の
素材miが配置され、同じ区画に２個の素材miが配置され
ることはない。したがって、素材miと、素材miが配置さ
れている区画とは１対１の関係となる。なお、同じ形状
の素材miを複数個配置する場合には、同じ形状の異なる
素材miが異なる区画に配置されることになる。
れた素材配置用格子Ａに、任意の大きさの矩形の素材mi
を複数配置する。この配置の方法を図２において説明す
る。図２においては、説明が簡単な様に３Ｘ３の素材配
置用格子Ａを用いる。そして、図２（ａ）に図示するよ
うに、この素材配置用格子Ａに６個の素材miを適宜配置
する。この配置は適当に行えば良いが、最小の面積に配
置できそうな配置を推定して行うことや、電算機で乱数
表を用いて並べることも可能である。ただし、各素材mi
は１個の区画に配置され、同じ素材miが、２か所の区画
に配置されることはない。また、１個の区画には１個の
素材miが配置され、同じ区画に２個の素材miが配置され
ることはない。したがって、素材miと、素材miが配置さ
れている区画とは１対１の関係となる。なお、同じ形状
の素材miを複数個配置する場合には、同じ形状の異なる
素材miが異なる区画に配置されることになる。
【００２１】この様に素材miを並べおえると、第３工程
および第４工程として、素材配置用格子Ａの区画の空間
が小さくなるように、横線Ｂおよび縦線Ｌを移動する。
たとえば、縦線L2を縮めて、横線B3を上方に移動する
（第３工程）。この横線B3の移動は、素材m3の縦方向の
長さを確保して行われる。この様にして、図２（ｂ）の
状態になる。
および第４工程として、素材配置用格子Ａの区画の空間
が小さくなるように、横線Ｂおよび縦線Ｌを移動する。
たとえば、縦線L2を縮めて、横線B3を上方に移動する
（第３工程）。この横線B3の移動は、素材m3の縦方向の
長さを確保して行われる。この様にして、図２（ｂ）の
状態になる。
【００２２】ついで、図２（ｂ）において、横線B3を縮
めて、縦線L7を左に移動する（第４工程）。この縦線L7
の移動は、素材m3および素材m5の横方向の長さを確保し
て行われる。この様にして、図３（ｃ）の状態になる。
この様に横線Ｂおよび縦線Ｌの移動を繰り返して、素材
miを図３（ｄ）に図示するように集結させる。
めて、縦線L7を左に移動する（第４工程）。この縦線L7
の移動は、素材m3および素材m5の横方向の長さを確保し
て行われる。この様にして、図３（ｃ）の状態になる。
この様に横線Ｂおよび縦線Ｌの移動を繰り返して、素材
miを図３（ｄ）に図示するように集結させる。
【００２３】そして、素材配置用格子Ａの周囲には、図
１で説明したように、境界条件用格子Ｃが設けられてお
り、この境界条件用格子Ｃを構成する横線Ｂおよび縦線
Ｌも各区画が小さくなるように移動させる。ところで、
詰める際には、どちら側にも詰めることができる。しか
しながら、実際に詰める際には、計算が簡単な様に、上
詰めまたは下詰めの何れかを優先させ、同様に、右詰め
または左詰めの何れかを優先させることになる。する
と、境界条件用格子Ｃの枠は、優先した側が直線とな
る。たとえば、上詰めおよび左詰めを優先すると、境界
条件用格子Ｃの上辺および左辺が直線になる。したがっ
て、境界条件用格子Ｃは全周にわたって設けられている
が、素材配置用格子Ａの周囲にＬ字状に設けられていれ
ば良い。すなわち、素材配置用格子Ａの上辺または下辺
の何れか一方の周囲と、左辺または右辺の何れか一方の
周囲とに設けられていれば充分である。この様に、素材
配置用格子Ａと同様な格子を具備する境界条件用格子Ｃ
を配置しているので、境界条件を簡単に得ることがで
き、電算機による計算が容易となる。
１で説明したように、境界条件用格子Ｃが設けられてお
り、この境界条件用格子Ｃを構成する横線Ｂおよび縦線
Ｌも各区画が小さくなるように移動させる。ところで、
詰める際には、どちら側にも詰めることができる。しか
しながら、実際に詰める際には、計算が簡単な様に、上
詰めまたは下詰めの何れかを優先させ、同様に、右詰め
または左詰めの何れかを優先させることになる。する
と、境界条件用格子Ｃの枠は、優先した側が直線とな
る。たとえば、上詰めおよび左詰めを優先すると、境界
条件用格子Ｃの上辺および左辺が直線になる。したがっ
て、境界条件用格子Ｃは全周にわたって設けられている
が、素材配置用格子Ａの周囲にＬ字状に設けられていれ
ば良い。すなわち、素材配置用格子Ａの上辺または下辺
の何れか一方の周囲と、左辺または右辺の何れか一方の
周囲とに設けられていれば充分である。この様に、素材
配置用格子Ａと同様な格子を具備する境界条件用格子Ｃ
を配置しているので、境界条件を簡単に得ることがで
き、電算機による計算が容易となる。
【００２４】この様にして、素材miを集結させると、素
材miを配置するのに必要な大きさが判明するので、この
判明した大きさよりも大きな基材や容器を用意すると、
この基材や容器に素材miを配置したり、基材から素材mi
を切り出したりする（第５工程）ことができる。なお、
素材miを切り出す場合には、素材miではなく、素材miの
切り出しパターンが各区画に配置されることになる。
材miを配置するのに必要な大きさが判明するので、この
判明した大きさよりも大きな基材や容器を用意すると、
この基材や容器に素材miを配置したり、基材から素材mi
を切り出したりする（第５工程）ことができる。なお、
素材miを切り出す場合には、素材miではなく、素材miの
切り出しパターンが各区画に配置されることになる。
【００２５】ところで、この大きさでは不満で、基材を
さらに小さな大きさにしたい場合には、図２（ａ）にお
ける素材miの配置を変更すればよい。そして、満足でき
る大きさの基材を得ることができた時点で作業を終了す
ればよい。また、当然全ての配置を検討することもでき
る。この配置の変更は、無作為に行うことも可能である
し、変更後と変更前とを比較して改善しそうな配置を推
定して行うことも可能である。
さらに小さな大きさにしたい場合には、図２（ａ）にお
ける素材miの配置を変更すればよい。そして、満足でき
る大きさの基材を得ることができた時点で作業を終了す
ればよい。また、当然全ての配置を検討することもでき
る。この配置の変更は、無作為に行うことも可能である
し、変更後と変更前とを比較して改善しそうな配置を推
定して行うことも可能である。
【００２６】なお、この図２の場合には、素材miの数Ｍ
は６個であり、格子は３Ｘ３である。この場合には、素
材mi相互間の自由度が少なく、必ずしも最適の解がでる
とは限らない。最適解を得るためには、全ての配置にお
いて、たとえば、縦または横に一列に並べた場合におい
ても、素材mi相互の間に少なくとも１個の空洞の区画が
配置可能な状態にすればよい。したがって、素材miがＭ
個ある場合には、素材mi相互の間に配置すべき空洞が
（Ｍ−１）個存在するので、合計で（２Ｍ−１）個の区
画を形成する。その結果、（２Ｍ−１）Ｘ（２Ｍ−１）
の格子を用いると、必ず最適解が求められる。しかしな
がら、格子を大きくすると、計算量が増大して計算が困
難となるので、大きくても（Ｍ）Ｘ（Ｍ）程度の格子で
行うことが現実的であると思われる。
は６個であり、格子は３Ｘ３である。この場合には、素
材mi相互間の自由度が少なく、必ずしも最適の解がでる
とは限らない。最適解を得るためには、全ての配置にお
いて、たとえば、縦または横に一列に並べた場合におい
ても、素材mi相互の間に少なくとも１個の空洞の区画が
配置可能な状態にすればよい。したがって、素材miがＭ
個ある場合には、素材mi相互の間に配置すべき空洞が
（Ｍ−１）個存在するので、合計で（２Ｍ−１）個の区
画を形成する。その結果、（２Ｍ−１）Ｘ（２Ｍ−１）
の格子を用いると、必ず最適解が求められる。しかしな
がら、格子を大きくすると、計算量が増大して計算が困
難となるので、大きくても（Ｍ）Ｘ（Ｍ）程度の格子で
行うことが現実的であると思われる。
【００２７】次に、素材配置用格子Ａに、矩形が結合さ
れた形状であるＬ字状の素材ｍを割り振る場合につい
て、図４および図５を用いて、説明する。図４はＬ字状
の素材ｍの割り振り方法を説明するための説明図で、
（ａ）が素材ｍの平面図、（ｂ）が素材ｍの切断図、
（ｃ）が素材ｍの割り振り図である。図５は素材の配置
結果を示す配置図である。
れた形状であるＬ字状の素材ｍを割り振る場合につい
て、図４および図５を用いて、説明する。図４はＬ字状
の素材ｍの割り振り方法を説明するための説明図で、
（ａ）が素材ｍの平面図、（ｂ）が素材ｍの切断図、
（ｃ）が素材ｍの割り振り図である。図５は素材の配置
結果を示す配置図である。
【００２８】図４において、図４（ａ）に図示するＬ字
状の素材ｍを、図４（ｂ）に図示するように、２個の矩
形パーツａ，ｂに分割する。この分割は、図４（ｂ）に
図示する上下でもよいし、左右でも可能である。そし
て、このパーツａ，ｂを、図４（ｃ）に図示するよう
に、素材ｍを分割した方向において隣接する区画に各々
割り当てる。
状の素材ｍを、図４（ｂ）に図示するように、２個の矩
形パーツａ，ｂに分割する。この分割は、図４（ｂ）に
図示する上下でもよいし、左右でも可能である。そし
て、このパーツａ，ｂを、図４（ｃ）に図示するよう
に、素材ｍを分割した方向において隣接する区画に各々
割り当てる。
【００２９】その際に、パーツａ，ｂを結合した時に直
線を維持すべき辺（この場合には、左辺）は、同じ縦線
Ｌまたは横線Ｂに対向するように配置する。したがっ
て、この辺が異なる縦線Ｌまたは横線Ｂに対向した場合
には、配置し直す必要がある。ただし、パーツａ，ｂを
隣接した区画に割り当てて、素材miを集結した後、Ｌ字
状の素材ｍが復元できた配置と、復元できなかった配置
とを取捨選択することも可能である。この様にして、図
５に図示するような配置図を得ることができた。
線を維持すべき辺（この場合には、左辺）は、同じ縦線
Ｌまたは横線Ｂに対向するように配置する。したがっ
て、この辺が異なる縦線Ｌまたは横線Ｂに対向した場合
には、配置し直す必要がある。ただし、パーツａ，ｂを
隣接した区画に割り当てて、素材miを集結した後、Ｌ字
状の素材ｍが復元できた配置と、復元できなかった配置
とを取捨選択することも可能である。この様にして、図
５に図示するような配置図を得ることができた。
【００３０】ところで、基材Ｋにネジ止め用の空間Ｓな
どを配置したり、ビデオなどのケースなどに装填するた
めに、基材Ｋの形状を矩形ではなく、その周囲が欠けた
形状にしたい場合がある。この様な場合には、基材Ｋす
なわち素材配置用格子Ａに空間Ｓを配置する必要があ
る。
どを配置したり、ビデオなどのケースなどに装填するた
めに、基材Ｋの形状を矩形ではなく、その周囲が欠けた
形状にしたい場合がある。この様な場合には、基材Ｋす
なわち素材配置用格子Ａに空間Ｓを配置する必要があ
る。
【００３１】そこで、次に、素材配置用格子Ａに、任意
の大きさの矩形の空間Ｓを配置する場合について、図６
および図７を用いて、説明する。図６は空間の割り振り
方法を説明するための説明図で、（ａ）が割り振られる
空間の平面図、（ｂ）が空間の割り振り図である。図７
は空間の配置結果を示す配置図である。
の大きさの矩形の空間Ｓを配置する場合について、図６
および図７を用いて、説明する。図６は空間の割り振り
方法を説明するための説明図で、（ａ）が割り振られる
空間の平面図、（ｂ）が空間の割り振り図である。図７
は空間の配置結果を示す配置図である。
【００３２】図６（ａ）に図示する空間を、図６（ｂ）
に図示するように矩形の空間Ｓに分割して配置する。こ
の空間Ｓは、縦横の長さは固定されており変形すること
はない。そして、空間Ｓは素材配置用格子Ａの端部だけ
ではなく、中央部にも配置することができる。この様
に、素材miが位置するスペースと、空間Ｓが位置するス
ペースとは同等に取り扱うことができ、その結果とし
て、図７に図示する略「Ｄ」の形状の配置などを得るこ
とができる。
に図示するように矩形の空間Ｓに分割して配置する。こ
の空間Ｓは、縦横の長さは固定されており変形すること
はない。そして、空間Ｓは素材配置用格子Ａの端部だけ
ではなく、中央部にも配置することができる。この様
に、素材miが位置するスペースと、空間Ｓが位置するス
ペースとは同等に取り扱うことができ、その結果とし
て、図７に図示する略「Ｄ」の形状の配置などを得るこ
とができる。
【００３３】以上、本発明の実施の形態を詳述したが、
本発明は、前記実施の形態に限定されるものではなく、
特許請求の範囲に記載された本発明の要旨の範囲内で、
種々の変更を行うことが可能である。本発明の変更例を
下記に例示する。 （１）実施の形態においては、素材配置用格子Ａは５Ｘ
５の格子で構成されているが、素材配置用格子Ａは区画
の数が素材の総数よりも多ければ良く、格子の形状は適
宜変更可能である。たとえば、４Ｘ８にする事も可能で
ある。
本発明は、前記実施の形態に限定されるものではなく、
特許請求の範囲に記載された本発明の要旨の範囲内で、
種々の変更を行うことが可能である。本発明の変更例を
下記に例示する。 （１）実施の形態においては、素材配置用格子Ａは５Ｘ
５の格子で構成されているが、素材配置用格子Ａは区画
の数が素材の総数よりも多ければ良く、格子の形状は適
宜変更可能である。たとえば、４Ｘ８にする事も可能で
ある。
【００３４】（２）実施の形態においては、素材miの向
きを変更していないが、素材miの縦横の向きを変更する
ことも可能である。 （３）実施の形態では、境界条件用格子Ｃを設けている
が、これは電算機で計算する際に、境界条件の設定を容
易にするために成されたもので、必ずしも設ける必要は
なく、他の手段により、境界条件を設定することも可能
である。
きを変更していないが、素材miの縦横の向きを変更する
ことも可能である。 （３）実施の形態では、境界条件用格子Ｃを設けている
が、これは電算機で計算する際に、境界条件の設定を容
易にするために成されたもので、必ずしも設ける必要は
なく、他の手段により、境界条件を設定することも可能
である。
【００３５】（４）実施の形態では、矩形が結合された
形状はＬ字であるが、他の形状でも可能である。たとえ
ば、クランク状に配置する事も可能である。そして、分
割された各パーツは、元の矩形が結合された形状が復元
できる様に、隣接した区画に配置する。また、矩形が結
合された形状に凹部が存在する場合には、所定の大きさ
を有する矩形形状の空間Ｓを配置し、凹部を確保する。
形状はＬ字であるが、他の形状でも可能である。たとえ
ば、クランク状に配置する事も可能である。そして、分
割された各パーツは、元の矩形が結合された形状が復元
できる様に、隣接した区画に配置する。また、矩形が結
合された形状に凹部が存在する場合には、所定の大きさ
を有する矩形形状の空間Ｓを配置し、凹部を確保する。
【００３６】（５）素材や基材の対象物は、特に限定さ
れるものではない。しかしながら、回路素子を素材とし
回路基板を基材とする半導体集積回路やプリント配線基
板の配置設計工程が適用分野として最適である。また、
素材である物品を容器に詰めたり、布地や鉄板などの平
面基材から各種大きさの複数の素材を切り出したりする
場合にも適している。
れるものではない。しかしながら、回路素子を素材とし
回路基板を基材とする半導体集積回路やプリント配線基
板の配置設計工程が適用分野として最適である。また、
素材である物品を容器に詰めたり、布地や鉄板などの平
面基材から各種大きさの複数の素材を切り出したりする
場合にも適している。
【００３７】（６）素材配置用格子Ａなどは、紙などに
現実的に形成する必要はなく、電子計算機などが創り出
す仮想空間上に形成することも可能である。 （７）第３工程と第４工程とは、その順序を逆に行うこ
とも、また同時に行うことも可能である。
現実的に形成する必要はなく、電子計算機などが創り出
す仮想空間上に形成することも可能である。 （７）第３工程と第４工程とは、その順序を逆に行うこ
とも、また同時に行うことも可能である。
【００３８】（８）実施の形態では、素材は矩形である
が、素材の配置のために確保する空間が矩形であれば、
素材自体は必ずしも矩形である必要はない。 （９）素材配置用格子Ａに素材miを配置する際に、素材
配置用格子Ａの区画が小さくて素材miが入らないことが
物理的にはあるが、この様な場合には、区画を広げる必
要がある。ただし、電算機においては、区画に素材miを
配置し、素材miの縦横の大きさを入力して、素材miに対
応した区画の大きさを数値的に確保している。したがっ
て、電算機においては、イメージ的には、無限の大きさ
の区画が形成されていることになり、区画を広げるとい
う作業は不要である。
が、素材の配置のために確保する空間が矩形であれば、
素材自体は必ずしも矩形である必要はない。 （９）素材配置用格子Ａに素材miを配置する際に、素材
配置用格子Ａの区画が小さくて素材miが入らないことが
物理的にはあるが、この様な場合には、区画を広げる必
要がある。ただし、電算機においては、区画に素材miを
配置し、素材miの縦横の大きさを入力して、素材miに対
応した区画の大きさを数値的に確保している。したがっ
て、電算機においては、イメージ的には、無限の大きさ
の区画が形成されていることになり、区画を広げるとい
う作業は不要である。
【００３９】
【発明の効果】本発明によれば、２区画に渡る縦線また
は横線により描かれている格子に、複数の素材を配置し
た後、素材を集結している。したがって、素材の大きさ
に応じて、縦線または横線を移動しているだけであるの
で、配置計算などの配置作業を容易に行うことができ
る。
は横線により描かれている格子に、複数の素材を配置し
た後、素材を集結している。したがって、素材の大きさ
に応じて、縦線または横線を移動しているだけであるの
で、配置計算などの配置作業を容易に行うことができ
る。
【００４０】また、得られた配置に満足できない場合に
は、縦横に区画を有する格子において、素材の位置を配
置換えする作業を行っている。したがって、この配置換
えにより他の素材の配置を必ずしも変更する必要がな
い。その結果、素材の配置の管理が簡単であり、素材の
配置換えを系統立てて行うことができる。
は、縦横に区画を有する格子において、素材の位置を配
置換えする作業を行っている。したがって、この配置換
えにより他の素材の配置を必ずしも変更する必要がな
い。その結果、素材の配置の管理が簡単であり、素材の
配置換えを系統立てて行うことができる。
【００４１】そして、格子の縦および横が、素材の数を
２倍して１減算した数に分割されている場合がある。こ
の場合には、最小の面積の配置構造を得ることができ
る。
２倍して１減算した数に分割されている場合がある。こ
の場合には、最小の面積の配置構造を得ることができ
る。
【００４２】さらに、略矩形が合体した形状である素材
を略矩形のパーツに分割しているので、略矩形の素材だ
けではなく、複雑な形状の素材も取り扱うことができ
る。
を略矩形のパーツに分割しているので、略矩形の素材だ
けではなく、複雑な形状の素材も取り扱うことができ
る。
【００４３】また、素材の一部を任意の大きさの矩形の
空間に置き換えているので、配置された素材の周囲や内
部に空間を形成することができる。その結果、素材が配
置される基材に、ビス止め用の空間や、切欠きなどを形
成することができる。
空間に置き換えているので、配置された素材の周囲や内
部に空間を形成することができる。その結果、素材が配
置される基材に、ビス止め用の空間や、切欠きなどを形
成することができる。
【００４４】そして、素材に代えて、素材切り出しパタ
ーンを配置した場合には、この切り出しパターンに基づ
いて素材を切り出すことができる。
ーンを配置した場合には、この切り出しパターンに基づ
いて素材を切り出すことができる。
【図１】図１は本発明における素材の配置および切り出
し方法に用いる格子の説明図である。
し方法に用いる格子の説明図である。
【図２】図２は素材を配置する際の工程を説明するため
の説明図で、（ａ）は初期状態の図、（ｂ）は次の段階
の図である。
の説明図で、（ａ）は初期状態の図、（ｂ）は次の段階
の図である。
【図３】図３は図２の続きの説明図で、（ｃ）は（ｂ）
の次の段階の図、（ｄ）は素材が集結した最終状態の図
である。
の次の段階の図、（ｄ）は素材が集結した最終状態の図
である。
【図４】図４はＬ字状の素材ｍの割り振り方法を説明す
るための説明図で、（ａ）が素材ｍの平面図、（ｂ）が
素材ｍの切断図、（ｃ）が素材ｍの割り振り図である。
るための説明図で、（ａ）が素材ｍの平面図、（ｂ）が
素材ｍの切断図、（ｃ）が素材ｍの割り振り図である。
【図５】図５は素材の配置結果を示す配置図である。
【図６】図６は空間の割り振り方法を説明するための説
明図で、（ａ）が割り振られる空間の平面図、（ｂ）が
空間の割り振り図である。
明図で、（ａ）が割り振られる空間の平面図、（ｂ）が
空間の割り振り図である。
【図７】図７は空間の配置結果を示す配置図である。
【図８】図８は素材の配置の決定方法を説明するための
説明図で、（ａ）は素材が分散している状態の図、
（ｂ）は素材が集結している状態の図である。
説明図で、（ａ）は素材が分散している状態の図、
（ｂ）は素材が集結している状態の図である。
Ａ 素材配置用格子（格子) ａ パーツ Ｂ 横線 ｂ パーツ Ｌ 縦線 mi 素材 Ｓ 空間
Claims (9)
- 【請求項１】 複数個の任意の大きさの略矩形の素材を
配列する素材の配置方法において、 前記素材の数よりも多い区画を有する格子を下記のａ，
ｂ，ｃの条件のもとで描く第１工程と、 ａ．格子周縁の区画を除く格子中央の区画は、隣接する
左右２区画に渡る横線と、隣接する上下２区画にわたる
縦線とを複数用いて描かれていること、 ｂ．前記横線の端部は前記縦線の中央部に対向し、ま
た、前記縦線の端部は前記横線の中央部に対向している
こと、 ｃ．格子周縁の区画は、上記ｂの条件を満たした状態
で、可能な限り２区画に渡る横線および縦線で構成さ
れ、残余の横線および縦線は、１区画のみを横切る横線
または縦線で描かれていること、 第１工程で描かれた区画に前記各素材を配置する第２工
程と、 区画内の素材の縦方向の長さを確保した状態で、前記縦
線を縮めて、前記横線を前記格子の上辺または下辺に近
づける第３工程と、 区画内の素材の横方向の長さを確保した状態で、前記横
線を縮めて、前記縦線を前記格子の左辺または右辺に近
づける第４工程とからなることを特徴とする素材の配置
方法。 - 【請求項２】 前記第２工程における素材の配置を変更
して、再び、前記第３工程から第４工程までの工程を繰
り返すことを特徴とする請求項１記載の素材の配置方
法。 - 【請求項３】 前記格子の縦および横が、素材の数を２
倍して１減算した数に分割されていることを特徴とする
請求項１または請求項２記載の素材の配置方法。 - 【請求項４】 略矩形が合体した形状の複数個の素材を
配列する素材の配置方法において、 前記素材を略矩形のパーツに分割し、その分割されたパ
ーツの数よりも多い区画を有する格子を下記のａ，ｂ，
ｃの条件のもとで描く第１工程と、 ａ．格子周縁の区画を除く格子中央の区画は、隣接する
左右２区画に渡る横線と、隣接する上下２区画にわたる
縦線とを複数用いて描かれていること、 ｂ．前記横線の端部は前記縦線の中央部に対向し、ま
た、前記縦線の端部は前記横線の中央部に対向している
こと、 ｃ．格子周縁の区画は、上記ｂの条件を満たした状態
で、可能な限り２区画に渡る横線および縦線で描かれ、
残余の横線および縦線は、１区画のみを横切る横線また
は縦線で描かれていること、 第１工程で描かれた区画に前記各パーツを配置するとと
もに、同一素材を構成する各パーツは隣接している区画
に配されている第２工程と、 区画内のパーツの縦方向の長さを確保した状態で、前記
縦線を縮めて、前記横線を前記格子の上辺または下辺に
近づける第３工程と、 区画内のパーツの横方向の長さを確保した状態で、前記
横線を縮めて、前記縦線を前記格子の左辺または右辺に
近づける第４工程とからなることを特徴とする素材の配
置方法。 - 【請求項５】 前記第２工程におけるパーツの配置を変
更して、再び、前記第３工程から第４工程までの工程を
繰り返すことを特徴とする請求項４記載の素材の配置方
法。 - 【請求項６】 任意の大きさの略矩形の素材が各々位置
する複数個のスペースと、任意の大きさの矩形の空間が
位置するスペースの両方を配列する素材の配置方法にお
いて、 前記スペースの数よりも多い区画を有する格子を下記の
ａ，ｂ，ｃの条件のもとで描く第１工程と、 ａ．格子周縁の区画を除く格子中央の区画は、隣接する
左右２区画に渡る横線と、隣接する上下２区画にわたる
縦線とを複数用いて描かれていること、 ｂ．前記横線の端部は前記縦線の中央部に対向し、ま
た、前記縦線の端部は前記横線の中央部に対向している
こと、 ｃ．格子周縁の区画は、上記ｂの条件を満たした状態
で、可能な限り２区画に渡る横線および縦線で描かれ、
残余の横線および縦線は、１区画のみを横切る横線また
は縦線で描かれていること、 第１工程で描かれた区画に前記各スペースを配置する第
２工程と、 区画内のスペースの縦方向の長さを確保した状態で、前
記縦線を縮めて、前記横線を前記格子の上辺または下辺
に近づける第３工程と、 区画内のスペースの横方向の長さを確保した状態で、前
記横線を縮めて、前記縦線を前記格子の左辺または右辺
に近づける第４工程とからなることを特徴とする素材の
配置方法。 - 【請求項７】 前記第２工程におけるスペースの配置を
変更して、再び、前記第３工程から第４工程までの工程
を繰り返すことを特徴とする請求項６記載の素材の配置
方法。 - 【請求項８】 複数個の任意の大きさの略矩形の素材を
切り出す素材の切り出し方法において、 前記切り出す素材の数よりも多い区画を有する格子を下
記のａ，ｂ，ｃの条件のもとで描く第１工程と、 ａ．格子周縁の区画を除く格子中央の区画は、隣接する
左右２区画に渡る横線と、隣接する上下２区画にわたる
縦線とを複数用いて描かれていること、 ｂ．前記横線の端部は前記縦線の中央部に対向し、ま
た、前記縦線の端部は前記横線の中央部に対向している
こと、 ｃ．格子周縁の区画は、上記ｂの条件を満たした状態
で、可能な限り２区画に渡る横線および縦線で描かれ、
残余の横線および縦線は、１区画のみを横切る横線また
は縦線で描かれていること、 第１工程で描かれた区画に前記各素材の切り出しパター
ンを配置する第２工程と、 区画内の切り出しパターンの縦方向の長さを確保した状
態で、前記縦線を縮めて、前記横線を前記格子の上辺ま
たは下辺に近づける第３工程と、 区画内の切り出しパターンの横方向の長さを確保した状
態で、前記横線を縮めて、前記縦線を前記格子の左辺ま
たは右辺に近づける第４工程と、 上記第２工程から第４工程までの工程により配置された
素材切り出しパターンに基づいて素材を切り出す第５工
程とからなることを特徴とする素材の切り出し方法。 - 【請求項９】 前記第２工程における切り出しパターン
の配置を変更して、再び、前記第３工程から第４工程ま
での工程を繰り返し、最良の切り出しパターンの配置を
検索したのち、前記第５工程を行うことを特徴とする請
求項１記載の素材の切り出し方法。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP7293798A JPH09108933A (ja) | 1995-10-18 | 1995-10-18 | 素材の配置および切り出し方法 |
| US08/547,440 US5808898A (en) | 1995-10-18 | 1995-10-24 | Method of placing and extracting modules |
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP7293798A JPH09108933A (ja) | 1995-10-18 | 1995-10-18 | 素材の配置および切り出し方法 |
| US08/547,440 US5808898A (en) | 1995-10-18 | 1995-10-24 | Method of placing and extracting modules |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH09108933A true JPH09108933A (ja) | 1997-04-28 |
Family
ID=26559563
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP7293798A Ceased JPH09108933A (ja) | 1995-10-18 | 1995-10-18 | 素材の配置および切り出し方法 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5808898A (ja) |
| JP (1) | JPH09108933A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7584445B2 (en) | 2007-03-29 | 2009-09-01 | Shigetoshi Nakatake | Sequence-pair creating apparatus and sequence-pair creating method |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7448012B1 (en) | 2004-04-21 | 2008-11-04 | Qi-De Qian | Methods and system for improving integrated circuit layout |
| JP4410088B2 (ja) * | 2004-11-29 | 2010-02-03 | 富士通株式会社 | 半導体装置の設計支援方法、プログラム及び装置 |
| US8599218B1 (en) | 2011-09-30 | 2013-12-03 | Google Inc. | Methods and apparatus for unification of space mechanisms in toolkits using a generic space component |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4500963A (en) * | 1982-11-29 | 1985-02-19 | The United States Of America As Represented By The Secretary Of The Army | Automatic layout program for hybrid microcircuits (HYPAR) |
| US4630219A (en) * | 1983-11-23 | 1986-12-16 | International Business Machines Corporation | Element placement method |
| JP3220250B2 (ja) * | 1992-01-09 | 2001-10-22 | 株式会社東芝 | セル自動配置方法 |
| JPH06102659A (ja) * | 1992-09-22 | 1994-04-15 | Toshiba Corp | マスク・レイアウト生成方法 |
| US5625568A (en) * | 1993-12-22 | 1997-04-29 | Vlsi Technology, Inc. | Method and apparatus for compacting integrated circuits with standard cell architectures |
-
1995
- 1995-10-18 JP JP7293798A patent/JPH09108933A/ja not_active Ceased
- 1995-10-24 US US08/547,440 patent/US5808898A/en not_active Expired - Fee Related
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7584445B2 (en) | 2007-03-29 | 2009-09-01 | Shigetoshi Nakatake | Sequence-pair creating apparatus and sequence-pair creating method |
Also Published As
| Publication number | Publication date |
|---|---|
| US5808898A (en) | 1998-09-15 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6230306B1 (en) | Method and apparatus for minimization of process defects while routing | |
| US6289495B1 (en) | Method and apparatus for local optimization of the global routing | |
| US6154874A (en) | Memory-saving method and apparatus for partitioning high fanout nets | |
| US6324674B2 (en) | Method and apparatus for parallel simultaneous global and detail routing | |
| US6253363B1 (en) | Net routing using basis element decomposition | |
| Cheng et al. | The cutting stock problem—a survey | |
| US6260183B1 (en) | Method and apparatus for coarse global routing | |
| US5072402A (en) | Routing system and method for integrated circuits | |
| DE69305981T2 (de) | Geringbenachbarte dreidimensionale verbindung. | |
| US5486775A (en) | Multiplexer structures for use in making controllable interconnections in integrated circuits. | |
| US6038385A (en) | Physical design automation system and process for designing integrated circuit chip using "chessboard" and "jiggle" optimization | |
| US5796625A (en) | Physical design automation system and process for designing integrated circuit chip using simulated annealing with "chessboard and jiggle" optimization | |
| JPH09108933A (ja) | 素材の配置および切り出し方法 | |
| JPS6330784B2 (ja) | ||
| US5838585A (en) | Physical design automation system and method using monotonically improving linear clusterization | |
| Martin et al. | Packing paths and Steiner trees: routing of electronic circuits | |
| US5731985A (en) | Chip sizing for hierarchical designs | |
| JP2604469B2 (ja) | 半導体集積回路装置及びその構成方法 | |
| JP7702927B2 (ja) | パーツの自動配置方法およびパーツの自動配置プログラム | |
| JPH09108934A (ja) | 素材の配置および切り出し方法 | |
| JPH0439776A (ja) | 半導体マクロセルのレイアウト方法 | |
| Ahuja | Efficient planar embedding of trees for VLSI layouts | |
| JP2956271B2 (ja) | 集積回路設計方法 | |
| van Kreveld et al. | Cutting a country for smallest square fit | |
| KR0163781B1 (ko) | 한개이상의 공통길이를 갖는 사각형의 기능블락을 포함하고 있는 반도체 장치 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20060118 |
|
| A045 | Written measure of dismissal of application [lapsed due to lack of payment] |
Free format text: JAPANESE INTERMEDIATE CODE: A045 Effective date: 20060530 |