| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2023-05-10 14:30 ［招待講演］Reallocation Problems with Minimum Completion Time ○Toshimasa Ishii（Hokkaido Univ.）・Jun Kawahara・Kazuhisa Makino（Kyoto Univ.）・Hirotaka Ono（Nagoya Univ.）  COMP2023-1 |
|
| 抄録 | （和） | (まだ登録されていません) |
| （英） | 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 feasible 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. | |
| キーワード | （和） | / / / / / / / |
| （英） | Algorithm / NP-hardness / Capacity augmentation / Approximation / Scheduling / Bin packing / / | |
| 文献情報 | 信学技報, vol. 123, no. 12, COMP2023-1, pp. 1-1, 2023年5月. | |
| 資料番号 | COMP2023-1 | |
| 発行日 | 2023-05-03 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2023-1 |
|
| 研究会情報 | |
| 研究会 | COMP IPSJ-AL |
| 開催期間 | 2023-05-10 - 2023-05-11 |
| 開催地（和） | 北海道大学 |
| 開催地（英） | Hokkaido University |
| テーマ（和） | 理論計算機科学，一般 |
| テーマ（英） | Theoretical Computer Science, etc |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2023-05-COMP-AL |
| 本文の言語 | 英語 |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | Reallocation Problems with Minimum Completion Time |
| サブタイトル（英） | |
| キーワード(1)（和/英） | / Algorithm |
| キーワード(2)（和/英） | / NP-hardness |
| キーワード(3)（和/英） | / Capacity augmentation |
| キーワード(4)（和/英） | / Approximation |
| キーワード(5)（和/英） | / Scheduling |
| キーワード(6)（和/英） | / Bin packing |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 石井 利昌 / Toshimasa Ishii / |
| 第1著者 所属（和/英） | 北海道大学 (略称： 北大) Hokkaido University (略称： Hokkaido Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 川原 純 / Jun Kawahara / |
| 第2著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto University (略称： Kyoto Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 牧野 和久 / Kazuhisa Makino / |
| 第3著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto University (略称： Kyoto Univ.) |
| 第4著者 氏名（和/英/ヨミ） | 小野 廣隆 / Hirotaka Ono / |
| 第4著者 所属（和/英） | 名古屋大学 (略称： 名大) Nagoya University (略称： Nagoya Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2023-05-10 14:30:00 |
| 発表時間 | 60分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2023-1 |
| 巻番号（vol） | vol.123 |
| 号番号（no） | no.12 |
| ページ範囲 | p.1 |
| ページ数 | 1 |
| 発行日 | 2023-05-03 (COMP) |
[研究会発表申込システムのトップページに戻る]