WEKO3
アイテム
{"_buckets": {"deposit": "8f391e3c-2d62-46fd-b52c-470428b1d10a"}, "_deposit": {"created_by": 16, "id": "1751", "owners": [16], "pid": {"revision_id": 0, "type": "depid", "value": "1751"}, "status": "published"}, "_oai": {"id": "oai:oacis.repo.nii.ac.jp:00001751", "sets": ["371", "372", "374"]}, "author_link": ["2892", "2897", "2890", "2898", "2895"], "item_3_biblio_info_6": {"attribute_name": "書誌情報", "attribute_value_mlt": [{"bibliographicIssueDates": {"bibliographicIssueDate": "2016", "bibliographicIssueDateType": "Issued"}, "bibliographicIssueNumber": "1", "bibliographicPageEnd": "129", "bibliographicPageStart": "110", "bibliographicVolumeNumber": "59", "bibliographic_titles": [{"bibliographic_title": "日本オペレーションズ・リサーチ学会論文誌"}, {"bibliographic_title": "Journal of the Operations Research Society of Japan", "bibliographic_titleLang": "en"}]}]}, "item_3_description_4": {"attribute_name": "抄録", "attribute_value_mlt": [{"subitem_description": "This paper focuses on a two-dimensional strip packing problem where a set of arbitrarily shaped rectilinear blocks need be packed into a larger rectangular container without overlap. A rectilinear block is a polygonal block whose interior angles are either 90∘or 270∘. This problem involves many industrial applications, such as VLSI design, timber/glass cutting, and newspaper layout. We generalized a bottom-left and a best-fit algorithms to the rectilinear block packing problem in our previous paper. Based on the analysis of the strength and weakness of these algorithms, we propose a new construction heuristic algorithm called the partition-based best-fit algorithm (PBF algorithm), which takes advantages of both the bottom-left and the best-fit algorithms. The basic idea of the PBF algorithm is that it partitions all the items into groups and then packs the items in a group-by-group manner. The best-fit algorithm is taken as the internal tactics for each group. The proposed algorithm is tested on a series of instances, which are generated from benchmark instances. The computational results show that the proposed algorithm significantly improves the performance of the existing construction heuristic algorithms and is especially effective for the instances having large differences in the sizes of given shapes. ", "subitem_description_type": "Abstract"}]}, "item_3_description_63": {"attribute_name": "研究課題番号", "attribute_value_mlt": [{"subitem_description": "15K16293", "subitem_description_type": "Other"}]}, "item_3_relation_11": {"attribute_name": "DOI", "attribute_value_mlt": [{"subitem_relation_type_id": {"subitem_relation_type_id_text": "https://doi.org/10.15807/jorsj.59.110", "subitem_relation_type_select": "DOI"}}]}, "item_3_relation_13": {"attribute_name": "情報源", "attribute_value_mlt": [{"subitem_relation_name": [{"subitem_relation_name_text": "Publisher\u0027s Version/PDF (OpenAccess)"}], "subitem_relation_type_id": {"subitem_relation_type_id_text": "https://doi.org/10.15807/jorsj.59.110", "subitem_relation_type_select": "DOI"}}, {"subitem_relation_name": [{"subitem_relation_name_text": "日本オペレーションズ・リサーチ学会 "}], "subitem_relation_type_id": {"subitem_relation_type_id_text": "http://www.orsj.or.jp/", "subitem_relation_type_select": "URI"}}, {"subitem_relation_name": [{"subitem_relation_name_text": "KAKEN研究課題: 組合せ最適化問題に対する多点探索型メタ戦略の開発"}], "subitem_relation_type_id": {"subitem_relation_type_id_text": "https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-15K16293/", "subitem_relation_type_select": "URI"}}, {"subitem_relation_name": [{"subitem_relation_name_text": "研究代表者: 橋本 英樹 (東京海洋大学)"}], "subitem_relation_type_id": {"subitem_relation_type_id_text": "https://nrid.nii.ac.jp/ja/nrid/1000070548114/", "subitem_relation_type_select": "URI"}}]}, "item_3_relation_28": {"attribute_name": "論文ID(NAID)", "attribute_value_mlt": [{"subitem_relation_type_id": {"subitem_relation_type_id_text": "130005124579", "subitem_relation_type_select": "NAID"}}]}, "item_3_source_id_7": {"attribute_name": "ISSN", "attribute_value_mlt": [{"subitem_source_identifier": "0453-4514", "subitem_source_identifier_type": "ISSN"}]}, "item_3_source_id_9": {"attribute_name": "書誌レコードID", "attribute_value_mlt": [{"subitem_source_identifier": "AA00703935", "subitem_source_identifier_type": "NCID"}]}, "item_3_subject_62": {"attribute_name": "件名", "attribute_value_mlt": [{"subitem_subject": "科学研究費研究成果", "subitem_subject_scheme": "Other"}]}, "item_3_subject_64": {"attribute_name": "科学研究費研究課題", "attribute_value_mlt": [{"subitem_subject": "組合せ最適化問題に対する多点探索型メタ戦略の開発", "subitem_subject_scheme": "Other"}]}, "item_access_right": {"attribute_name": "アクセス権", "attribute_value_mlt": [{"subitem_access_right": "metadata only access", "subitem_access_right_uri": "http://purl.org/coar/access_right/c_14cb"}]}, "item_creator": {"attribute_name": "著者", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "Hu, Yannan"}], "nameIdentifiers": [{"nameIdentifier": "2892", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "Hashimoto, Hideki"}], "nameIdentifiers": [{"nameIdentifier": "2890", "nameIdentifierScheme": "WEKO"}, {"nameIdentifier": "70548114", "nameIdentifierScheme": "e-Rad", "nameIdentifierURI": "https://kaken.nii.ac.jp/ja/search/?qm=70548114"}]}, {"creatorNames": [{"creatorName": "Imahori, Shinji "}], "nameIdentifiers": [{"nameIdentifier": "2897", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "Uno, Takeaki"}], "nameIdentifiers": [{"nameIdentifier": "2898", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "Yagiura, Mutsunori"}], "nameIdentifiers": [{"nameIdentifier": "2895", "nameIdentifierScheme": "WEKO"}]}]}, "item_keyword": {"attribute_name": "キーワード", "attribute_value_mlt": [{"subitem_subject": "Combinatorial optimization", "subitem_subject_scheme": "Other"}, {"subitem_subject": "strip packing", "subitem_subject_scheme": "Other"}, {"subitem_subject": "rectilinear block", "subitem_subject_scheme": "Other"}, {"subitem_subject": "heuristic", "subitem_subject_scheme": "Other"}, {"subitem_subject": "group-manner", "subitem_subject_scheme": "Other"}]}, "item_language": {"attribute_name": "言語", "attribute_value_mlt": [{"subitem_language": "eng"}]}, "item_resource_type": {"attribute_name": "資源タイプ", "attribute_value_mlt": [{"resourcetype": "journal article", "resourceuri": "http://purl.org/coar/resource_type/c_6501"}]}, "item_title": "A Partition-Based Heuristic Algorithm for the Rectilinear Block Packing Problem", "item_titles": {"attribute_name": "タイトル", "attribute_value_mlt": [{"subitem_title": "A Partition-Based Heuristic Algorithm for the Rectilinear Block Packing Problem"}]}, "item_type_id": "3", "owner": "16", "path": ["371", "372", "374"], "permalink_uri": "https://oacis.repo.nii.ac.jp/records/1751", "pubdate": {"attribute_name": "公開日", "attribute_value": "2019-06-03"}, "publish_date": "2019-06-03", "publish_status": "0", "recid": "1751", "relation": {}, "relation_version_is_last": true, "title": ["A Partition-Based Heuristic Algorithm for the Rectilinear Block Packing Problem"], "weko_shared_id": -1}
A Partition-Based Heuristic Algorithm for the Rectilinear Block Packing Problem
https://oacis.repo.nii.ac.jp/records/1751
https://oacis.repo.nii.ac.jp/records/175179b7e332-f8c4-4738-8ec1-9f189cd262d1
Item type | 学術雑誌論文 / Journal Article(1) | |||||
---|---|---|---|---|---|---|
公開日 | 2019-06-03 | |||||
タイトル | ||||||
タイトル | A Partition-Based Heuristic Algorithm for the Rectilinear Block Packing Problem | |||||
言語 | ||||||
言語 | eng | |||||
キーワード | ||||||
主題 | Combinatorial optimization, strip packing, rectilinear block, heuristic, group-manner | |||||
資源タイプ | ||||||
資源タイプ | journal article | |||||
アクセス権 | ||||||
アクセス権 | metadata only access | |||||
著者 |
Hu, Yannan
× Hu, Yannan× Hashimoto, Hideki× Imahori, Shinji× Uno, Takeaki× Yagiura, Mutsunori |
|||||
書誌情報 |
日本オペレーションズ・リサーチ学会論文誌 en : Journal of the Operations Research Society of Japan 巻 59, 号 1, p. 110-129, 発行日 2016 |
|||||
抄録 | ||||||
内容記述 | This paper focuses on a two-dimensional strip packing problem where a set of arbitrarily shaped rectilinear blocks need be packed into a larger rectangular container without overlap. A rectilinear block is a polygonal block whose interior angles are either 90∘or 270∘. This problem involves many industrial applications, such as VLSI design, timber/glass cutting, and newspaper layout. We generalized a bottom-left and a best-fit algorithms to the rectilinear block packing problem in our previous paper. Based on the analysis of the strength and weakness of these algorithms, we propose a new construction heuristic algorithm called the partition-based best-fit algorithm (PBF algorithm), which takes advantages of both the bottom-left and the best-fit algorithms. The basic idea of the PBF algorithm is that it partitions all the items into groups and then packs the items in a group-by-group manner. The best-fit algorithm is taken as the internal tactics for each group. The proposed algorithm is tested on a series of instances, which are generated from benchmark instances. The computational results show that the proposed algorithm significantly improves the performance of the existing construction heuristic algorithms and is especially effective for the instances having large differences in the sizes of given shapes. | |||||
ISSN | ||||||
収録物識別子タイプ | ISSN | |||||
収録物識別子 | 0453-4514 | |||||
書誌レコードID | ||||||
収録物識別子タイプ | NCID | |||||
収録物識別子 | AA00703935 | |||||
DOI | ||||||
識別子タイプ | DOI | |||||
関連識別子 | https://doi.org/10.15807/jorsj.59.110 | |||||
情報源 | ||||||
関連識別子 | https://doi.org/10.15807/jorsj.59.110 | |||||
関連名称 | Publisher's Version/PDF (OpenAccess) | |||||
情報源 | ||||||
関連識別子 | http://www.orsj.or.jp/ | |||||
関連名称 | 日本オペレーションズ・リサーチ学会 | |||||
情報源 | ||||||
関連識別子 | https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-15K16293/ | |||||
関連名称 | KAKEN研究課題: 組合せ最適化問題に対する多点探索型メタ戦略の開発 | |||||
情報源 | ||||||
関連識別子 | https://nrid.nii.ac.jp/ja/nrid/1000070548114/ | |||||
関連名称 | 研究代表者: 橋本 英樹 (東京海洋大学) | |||||
件名 | ||||||
主題 | 科学研究費研究成果 | |||||
論文ID(NAID) | ||||||
識別子タイプ | NAID | |||||
関連識別子 | 130005124579 | |||||
科学研究費研究課題 | ||||||
主題 | 組合せ最適化問題に対する多点探索型メタ戦略の開発 | |||||
研究課題番号 | ||||||
内容記述 | 15K16293 |