直線ブロックパッキング問題に関する分割に基づく発見的アルゴリズム

HU Yannan; HASHIMOTO Hideki; IMAHORI Shinji; UNO Takeaki; YAGIURA Mutsunori

文献

J-GLOBAL ID：201602213586422090 整理番号：16A0215219

直線ブロックパッキング問題に関する分割に基づく発見的アルゴリズム

A PARTITION-BASED HEURISTIC ALGORITHM FOR THE RECTILINEAR BLOCK PACKING PROBLEM

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=16A0215219&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=16A0215219&from=J-GLOBAL&jstjournalNo=G0402A") }}

著者 (5件)： , , , ,
資料名：
巻： 59 号： 1 ページ： 110-129 (J-STAGE) 発行年： 2016年
JST資料番号： G0402A ISSN： 0453-4514 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：日本 (JPN) 言語：英語 (EN)

本論文は一連の任意形状直線ブロックを重複無しにより大きな長方形コンテナにパッキングする必要がある,2次元ストリップ包装問題に焦点を当てた。直線ブロックは内角が90°または270°の多角形ブロックである。この問題はVLSI設計,木材/ガラス切断および新聞レイアウトなど,多くの工業アプリケーションを含む。筆者らは以前の論文で,直線ブロックパッキング問題に対する左下および最良適合アルゴリズムを一般化した。これらアルゴリズムの強み弱み分析に基づき,左下および最良適合アルゴリズム双方を活用する,分割ベース最良適合アルゴリズム(PBFアルゴリズム)と呼ぶ新構成発見的アルゴリズムを提案した。PBFアルゴリズムの基本アイデアは,全品目をグループに分割した後,それらをグループバイグループ方式でパッキングすることにある。各グループの内部戦術として最良適合アルゴリズムを採る。ベンチマーク事例から生成される,一連のインスタンスにおいて提案アルゴリズムを試験した。計算結果は提案アルゴリズムが現存の構成発見的アルゴリズムの性能を大幅に改良し,付与形状のサイズに大きな違いのある事例に特に有効であることを示した。

, , , , , , , , , , ,

その他のオペレーションズリサーチの手法

引用文献 (17件)：

[1] R.C. Art: An approach to the two dimensional irregular cutting stock problem. IBM Cambridge Science Center, 36 (1966), Y08.
[2] B.S. Baker, E.G. Coffman Jr. and R.L. Rivest: Orthogonal packings in two dimensions. SIAM Journal on Computing, 9 (1980), 846-855.
[3] E.K. Burke, G. Kendall and G. Whitwell: A new placement heuristic for the orthogonal stock-cutting problem. Operations Research, 52 (2004), 655-671.
[4] D. Chen, J. Liu, Y. Fu and M. Shang: An efficient heuristic algorithm for arbitrary shaped rectilinear block packing problem. <i>Computers & Operations Research</i>, 37 (2010), 1068-1074.
[5] K. Fujiyoshi and H. Murata: Arbitrary convex and concave rectilinear block packing using sequence-pair. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 19 (2000), 224-233.

, ,

前のページに戻る