| 講演名 | 2002/11/22 搬送計画問題に対するネットワーク理論を利用したアプローチ 浅野 哲夫, 千葉 英史, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 搬送計画問題は,多品種製造ラインにおける最適な搬送計画を求める問題であって,製造の担当者にとっては切実である.本稿では,まずこの問題を最適化問題,及び決定問題として定式化する.そ.して,この問題がNP完全であることを証明する.その際,ビンパッキング問題が搬送計画問題に多項式時間帰着可能であることを利用する.次に,ある種の強い制約を加えた搬送計画問題の解法を示す.この制約によって,入力サイズnの一次元コンパクション問題に変換されるので,ネットワーク理論を利用してO(nlogn)時間で解くことができる.LEDAによるアルゴリズムの実装も行った. |
| 抄録(英) | Transportation Scheduling Problem is the problem to find an optimal transportation scheduling in multi-commodity manufacture lines. In this paper, we formulate this problem as an optimization problem and a decision problem. And we prove that this problem is NP-complete. The proof is based on the polynomial-time reduction from the Bin-Packing Problem to the Transportation Scheduling Problem. Next, we show an algorithm for the problem under some strong constraints. This problem reduces to the one-dimensional compaction problem with n input sizes because of constraints. It can be solved in O(nlogn) time using network theory. We have implemented the algorithm using LEDA. |
| キーワード(和) | NP完全問題 / コンパクションアルゴリズム / 最短経路アルゴリズム |
| キーワード(英) | NP-complete problem / compaction algorithm / shortest path algorithm |
| 資料番号 | COMP2002-49 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2002/11/22(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 搬送計画問題に対するネットワーク理論を利用したアプローチ |
| サブタイトル（和） | |
| タイトル（英） | An Approach Based on Network Theory to Transportation Scheduling Problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | NP完全問題 / NP-complete problem |
| キーワード(2)（和/英） | コンパクションアルゴリズム / compaction algorithm |
| キーワード(3)（和/英） | 最短経路アルゴリズム / shortest path algorithm |
| 第 1 著者 氏名（和/英） | 浅野 哲夫 / Tetsuo ASANO |
| 第 1 著者 所属（和/英） | 北陸先端科学技術大学院大学情報科学研究科 School of Information Science Japan Advanced Institute of Science and Technology |
| 第 2 著者 氏名（和/英） | 千葉 英史 / Eishi CHIBA |
| 第 2 著者 所属（和/英） | 北陸先端科学技術大学院大学情報科学研究科 School of Information Science Japan Advanced Institute of Science and Technology |
| 発表年月日 | 2002/11/22 |
| 資料番号 | COMP2002-49 |
| 巻番号（vol） | vol.102 |
| 号番号（no） | 490 |
| ページ範囲 | pp.- |
| ページ数 | 5 |
| 発行日 | |