文献

J-GLOBAL ID：202102236466632159   整理番号：21A2956395

単一列設備レイアウト問題を解くためのGPU上の2optベースヒューリスティックスの最適化【JST・京大機械翻訳】

Optimizing 2-opt-based heuristics on GPU for solving the single-row facility layout problem

著者 (5件)： Sun Xue (College of Urban Rail Transit and Logistics, Joint Jiaotong College of Beijing Union University & Russian University of Transport, Beijing Union University, Beijing 100101, China) ,  Chou Ping (Department of Management Information Systems, National Chengchi University, Taipei 11605, Taiwan) ,  Koong Chorng-Shiuh (Department of Computer Science, National Taichung University of Education, Taichung 40359, Taiwan) ,  Wu Chao-Chin (Department of Computer Science and Information Engineering, National Changhua University of Education, Changhua 50007, Taiwan) ,  Chen Liang-Rui (Department of Electrical Engineering, National Changhua University of Education, Changhua 50007, Taiwan)
資料名： Future Generation Computer Systems  (Future Generation Computer Systems)
巻： 126  ページ： 91-109  発行年： 2022年 
JST資料番号： A0620C  ISSN： 0167-739X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： ほとんどの組合せ問題の最適化は,NP困難であり,それは,特に大規模問題に対して,近似的に最適解を得るための発見的アルゴリズムによって解くことができる。多くの発見的アルゴリズムは,より良い解法を見つけるために2-opt局所探索を適用することができる。完全な2-opt局所探索において,スワッピング機構のあらゆる有効な隣接解を比較し,特に逐次アルゴリズムを採用するとき,非常に時間がかかる。今日,グラフィック処理ユニット(GPU)は,NP困難問題の解決を加速するために広く使用されている強力で柔軟な並列計算プラットフォームに進化してきた。したがって,本研究では,2optベースシミュレーテッドアニーリング(SA)発見的アルゴリズムによる単一列施設レイアウト問題(SRFLP)を解くためにGPUを使用する方法に焦点を当てた。知る限りでは,本研究は,GPUを用いてSRFLPを解く初めてである。親と子の解の間の適応度関数と移動利得計算を分析した後に,著者らは,大量の複製計算を取り除くために,プレフィックス和式テーブルを提案する。各反復中の2opt局所探索に対する移動利得を計算するために,多くのGPUスレッドを作成し,それらを並列にテーブルを構築,検索した。実験結果に従って,プレフィックス和式テーブルが採用されないならば,GPUバージョンは,123の最良高速化で,逐次CPU対応物より優れている。しかし,テーブルをGPUバージョンで使用するならば,最良の高速化は3208に達することができる。プレフィックス和式テーブルによる提案並列化アプローチは,2-opt局所探索とSRFLP適応度関数の特徴に基づいているので,SAアルゴリズムが本研究で使用されたとしても,SRFLPを解くための任意の2-optベースの発見的アルゴリズムに適用できる。Copyright 2021 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  *最適化 ,  複製 ,  近似法 ,  *配置問題 ,  並列演算 ,  利得 ,  NP困難 ,  シミュレーテッドアニーリング ,  スレッド ,  近傍探索法
準シソーラス用語： 最適解 ,  プレフィックス ,  発見的アルゴリズム ,  GPU【プロセッサ】 , 【Automatic Indexing@JST】

著者キーワード (5件)： 2-最適局所探索 ,  設備レイアウト ,  シミュレーテッドアニーリング ,  グラフィック処理装置(GPU) ,  発見的アルゴリズム

分類 (5件)： ディジタル計算機方式一般  (JC02010O) ,  専用演算制御装置  (JC04030Y) ,  計算機網  (JC03000K) ,  計算機システム開発  (JD02010R) ,  人工知能  (JE08000Z)

タイトルに関連する用語 (5件)： 設備 ,  レイアウト問題 ,  GPU ,  ヒューリスティックス ,  最適化