{"links":{},"id":225654,"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00225654","sets":["1164:2592:11085:11247"]},"path":["11247"],"owner":"44499","recid":"225654","title":["Reallocation Problems with Minimum Completion Time"],"pubdate":{"attribute_name":"公開日","attribute_value":"2023-05-03"},"_buckets":{"deposit":"762977ce-fdc9-47ce-a60d-973cdfc10ce3"},"_deposit":{"id":"225654","pid":{"type":"depid","value":"225654","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"Reallocation Problems with Minimum Completion Time","author_link":["597571","597567","597564","597569","597565","597566","597568","597570"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Reallocation Problems with Minimum Completion Time"},{"subitem_title":"Reallocation Problems with Minimum Completion Time","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"招待講演","subitem_subject_scheme":"Other"}]},"item_type_id":"4","publish_date":"2023-05-03","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"Graduate School of Economics and Business Administration, Hokkaido University"},{"subitem_text_value":"Graduate School of Informatics, Kyoto University"},{"subitem_text_value":"RIMS, Kyoto University"},{"subitem_text_value":"Graduate School of Informatics, Nagoya University"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Graduate School of Economics and Business Administration, Hokkaido University","subitem_text_language":"en"},{"subitem_text_value":"Graduate School of Informatics, Kyoto University","subitem_text_language":"en"},{"subitem_text_value":"RIMS, Kyoto University","subitem_text_language":"en"},{"subitem_text_value":"Graduate School of Informatics, Nagoya University","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/225654/files/IPSJ-AL23193003.pdf","label":"IPSJ-AL23193003.pdf"},"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-AL23193003.pdf","filesize":[{"value":"764.5 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"9"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_login","version_id":"0da4e4fa-550a-4e9d-b160-7bb78ac17558","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2023 by the Institute of Electronics, Information and Communication Engineers This SIG report is only available to those in membership of the SIG."}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Toshimasa, Ishii"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Jun, Kawahara"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Kazuhisa, Makino"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Hirotaka, Ono"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Toshimasa, Ihii","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Jun, Kawahara","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Kazuhisa, Makino","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Hirotaka, Ono","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN1009593X","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"2188-8566","subitem_source_identifier_type":"ISSN"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"Reallocation scheduling is one of the most fundamental problems in various areas such as supply chain management, logistics, and transportation science. In this paper, we introduce the reallocation problem that models the scheduling in which products are with fixed cost (e.g., transition time), non-fungible, and reallocated among warehouses in parallel, and comprehensively study the complexity of the problem under various settings of the transition time, product size, and capacities. We show that the problem can be solved in polynomial time for a fundamental setting where the product size and transition time are both uniform. We also show that the feasibility of the problem is NP-complete even for little more general settings, which implies that no polynomial-time algorithm constructs a feasible schedule of the problem unless P=NP. We then consider to solve the problem by relaxing capacity constraints, which we call the capacity augmentation, and derive a reallocation schedule feasib le with the augmentation such that the completion time is at most the optimal of the original problem. When the warehouse capacity is sufficiently large, we design constant-factor approximation algorithms. We also show the relationship between the reallocation problem and the bin packing problem when the warehouse and carry-in capacities are sufficiently large.","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"Reallocation scheduling is one of the most fundamental problems in various areas such as supply chain management, logistics, and transportation science. In this paper, we introduce the reallocation problem that models the scheduling in which products are with fixed cost (e.g., transition time), non-fungible, and reallocated among warehouses in parallel, and comprehensively study the complexity of the problem under various settings of the transition time, product size, and capacities. We show that the problem can be solved in polynomial time for a fundamental setting where the product size and transition time are both uniform. We also show that the feasibility of the problem is NP-complete even for little more general settings, which implies that no polynomial-time algorithm constructs a feasible schedule of the problem unless P=NP. We then consider to solve the problem by relaxing capacity constraints, which we call the capacity augmentation, and derive a reallocation schedule feasib le with the augmentation such that the completion time is at most the optimal of the original problem. When the warehouse capacity is sufficiently large, we design constant-factor approximation algorithms. We also show the relationship between the reallocation problem and the bin packing problem when the warehouse and carry-in capacities are sufficiently large.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"1","bibliographic_titles":[{"bibliographic_title":"研究報告アルゴリズム（AL）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2023-05-03","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"3","bibliographicVolumeNumber":"2023-AL-193"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"created":"2025-01-19T01:25:09.543503+00:00","updated":"2025-01-19T12:43:40.413902+00:00"}