グラフ上の搬送スケジューリング問題の計算の複雑さについて
スポンサーリンク
概要
- 論文の詳細を見る
本論文では,1台の搬送車が無向グラフG上を移動しながら各節点に位置する仕事を効率よく処理するための搬送スケジューリングについて考察する.グラフG=(V,E)の各節点vには,処理すべき仕事が位置し,それぞれ準備時間r(v)および処理時間h(v)が与えられている.すなわち,どの節点でもその準備時間より以前の時刻には仕事を開始することはできず,その仕事を開始してから終了するまでに所定の処理時間がかかる.また,Gの各辺{u,v}には,その辺をuからvへ(vからuへ)通過するための移動時間w(u,v)(w(v,u))が決められている.このような条件の下で,1台の搬送車が指定された節点sから出発し,G上の全ての節点の仕事を終え、指定された終着点集合Q⊆Vのどれかに到達するまでにかかる最短の完了時間を求める搬送スケジューリング問題(G,w,r,h,s,Q)を考える.論文では,まずこの搬送スケジューリング問題を巌密に解く動的計画法を構築する.一般にこの巌密解法は,n点からなるグラフGに対しO(n^22^n)時間で動作するが,処理時間がすべて0である場合には、調べるべき状態数を大きく減らすことができる。特に、Gが木であり、その葉の数bが定数である場合には,O(n^b+1>logn)時間で作動することが示せる。最後に,この搬送スケジューリング問題は,Gが木であり、どの処理時間が0であっても,強NP完全であることを示す.
- 1994-06-16
著者
関連論文
- 給油施設操業スケジューリング (企業事例)
- 特集にあたって (ユーザのための数理計画応用)
- 多次元直方体被覆問題および充足可能性問題を解くアルゴリズム
- 緩和法による演繹データベースの問合せ評価
- 多変数同世代問題に対する問い合わせ評価法
- 多変数同世代問題に対する問合せ評価法
- 緩和法による演繹データベースの問い合わせ評価
- 多変数線形再帰型演繹データベースに対する逆数え上げ評価法
- 自己双対正論理関数の分解について
- 格子型光波網におけるパス割り当て問題に関する考察
- Serializable Classesの構造について(計算機構に関する数学的基礎理論とその応用)
- 先読みスケジューラによる分散型データベースシステムの並行処理制御(計算アルゴリズムと計算量の基礎理論)
- 版数制限をもつ先読みスケジュ-ラ
- グラフパッキング問題の計算複雑度(計算機科学の基礎理論とその応用)
- 内点法
- ランダム有向グラフにおける到達可能性と推移閉包の大きさについて
- 関係の推移閉包の大きさの近似的推定法
- 演えきデータベースにおける質問処理コストの近似的評価法
- Complexity of the Optimum Join Order Problem in Deductive Databases
- 辺連結度増加関数をO^^〜(mn)時間で計算するアルゴリズム
- フローゲームの凸性について(ゲーム理論(2))
- マトロイド上の最小基ゲーム
- 多次元コスト関数をもつ有限オートマトンについて (情報科学の数学的基礎理論と応用)
- ある種の平面有向ネットワークの多品種流問題について(計算アルゴリズムと計算量の基礎理論)
- タブー探索による直交ラテン方陣の構成(連続と離散の最適化数理)
- 中間経由節点をもつKサーバー問題(計算機構とアルゴリズム)
- 最小容量カットアルゴリズムのプログラムによる効率の良い実現法
- 多重グラフにおける(λ+1)-カット
- 領域制約の下でのゲーム木探索(計算アルゴリズムと計算量の基礎理論)
- ゲーム木探索法SSSの非劣性について(計算アルゴリズムの基礎理論)
- 無向グラフ上の辺分離問題を解く簡単なO(mn)時間アルゴリズム
- 高信頼性ユニットからなる並-直列システムの漸近的に最適な保全政策(信頼性)
- 経済状態を考慮したアメリカンオプションの最適行使問題(ポートフォリオ)
- 33. 線形計画問題の高速解法 (アルゴリズムの最近の動向)
- Learning Algorithms for 2 × 2 Stochastic Games with Incomplete Information
- グラフ上の搬送スケジューリング問題の計算の複雑さについて(スケジューリング(2))
- グラフ上の搬送スケジューリング問題の計算の複雑さについて
- 遺伝アルゴリズムにおける交叉法に対する一考察(計算量理論)
- 1機械スケジューリング問題に対するSSDP法(動的計画法)
- 部分定義論理関数の正論理関数とHorn関数における関数分解について
- サブツアー交換交叉に対する二つのコメント
- サブツアー交換交叉に対する2つのコメント
- 不完全例題に対するプール的解析
- 鎖パッキング問題について(アルゴリズムの数学的基礎理論とその応用)
- ジャンケンのトーナメント表現と意味のある拡張(アルゴリズムと計算量理論)
- T-混合カットにおける領域間連結度の性質(グラフ・ネットワーク(5))
- 最小カット問題の簡潔かつ構成的な証明
- 平面グラフにおける辺遊離操作と辺連結度増大問題について
- Primal-Dual Proximal Point Algorithm for Multicommodity Network Flow Problems(MATHEMATICAL OPTIMIZATION AND ITS APPLICATIONS)
- 非線形最小費用流問題に対する双対ニュートン法(決定理論とその周辺)
- 年齢に依存した費用を持つ小修理・取替え問題についてII(信頼性)
- 年齢に依存した費用を持つ小修理・取替え問題について(信頼性)
- 平均費用規範最適小修理・取替え問題について(最適化理論とその関連分野)
- ある信頼性システムに対する修理限界取替え政策の最適性について(マルコフ解析)
- 平均費用規範最適小修理・取替え問題について(マルコフ解析)
- 多項過程モデルによるルックバックオプションの価格の上・下界評価(数理計画モデルにおける最適化理論)
- 多項過程モデルによるルックバックオプションの価格の上・下界評価(金融)
- 組合せ最適化ゲーム
- 反復ラインダイグラフの深さの浅い独立全域木
- 資産の収益率の相関がある構造を持つポートフォリオ選択問題について(資金・資本の流れ)
- ポートフォリオ選択問題における投資家の危険回避性と初期の富の影響(ポートフォリオ)
- ポートフォリオ選択問題における資産の収益率の確立順序(最適化の数理とその応用)
- グラフのサム数に対する上下界について
- 多期間ポートフォリオ選択問題における分離定理(計画数学とその関連分野)
- リーダー選出問題における時間最小アルゴリズムについて(計算アルゴリズムと計算量の基礎理論)
- 格子型光波ネットワークの再構成アルゴリズムについて
- 光波ネットワークのノード再配置アルゴリズムについて
- 双方向マンハッタン・ストリート・ネットワークの網再構成について
- データの論理的解析とブール関数
- データの論理的解析とブール関数
- 部分定義論理関数の内核関数と外核関数
- 2-単調正論理関数の同定問題に対する単純な高速アルゴリズム
- 論理関数の内包関数と外包関数について
- 不完全に定義された正論理関数の最大潜伏度について
- 正論理関数の最大潜伏度について(計算機構とアルゴリズム)
- 大規模非線形計画問題に対する逐次2次計画分解法