n/m/I/L_<max>及びn/2/F/L_<max>スケジューリング問題に対する近似アルゴリズムのバウンドについて
スポンサーリンク
概要
- 論文の詳細を見る
本論文では、最大納期遅れを最小にする、2種のNP一完全なスケーシェリング問題に対する近似アルゴリズムを提案したうえで、そのワーストケースバウンド等について考察する。(i〕最初は、n個の独立で、納期と処理時間が既知の仕事を、m台の等価並列機械で処理する時に、最大納期遅れを最小にする問題(n/m/I/L_<max>)について考察する。この問題はNP一完全であるので、2つの近似アルゴリズムEDDとLPTを提案し、それぞれのワースケースバウンドを与える。(ii〕次に、(i〕と同様な仕事を、2機械のフローショップにおいて処理する時に、最大納期遅れを最小にする問題(n/2/F/L_<max>)について考察する。(i)と同様に、この問題もNP一完全である。そこで、まず、この問題に対して、最適解が容易に求められる場合を与え、次に、一般のn/2/F/L_<max>に対して近似アルゴリズムを提案し、そのワーストケースバウンドを与える。
著者
-
西田 俊夫
大阪大学
-
石井 博昭
大阪大学
-
石井 博昭
大阪大学大学院情報科学研究科情報数理学専攻
-
西田 俊夫
大阪大学工学部数理工学教室
-
益田 照雄
帝塚山大学経営情報学部
-
益田 照雄
大阪府立大学
関連論文
- An inconsistency problem in data discretion using equal width interval approach (21世紀の数理計画--アルゴリズムとモデリング--RIMS研究集会報告集)
- 2-G-8 カーネル型SIRMsファジィ推論法による判別分析への応用(意思決定(2))
- Combined Model for Clustering Observations of Systems Subject to Inefficiency(DEA(2))
- 確率的線形ナップザック問題とポートフォリオ選択問題(II)(ポートフォリオ)
- 確率計画問題における信頼域によるアプローチ
- 関所のあるネットワークの流れ
- ファジイランダム変数を係数にもつ線形計画問題(数理計画法(1))
- ファジイランダム変数とその応用(連続と離散の最適化数理)
- ファジィランダム線形計画問題(確率・ファジィ)
- 必然性測度に基づくファジイ・スパニング・ツリー問題の一解法
- ファジィ最短経路問題の2目的定式化(ファジィ)
- 1-C-12 クラスタリングに基づく類似性分析法と医療診断への応用(政策・行政・医療・福祉)
- 新薬開発のための多目的コンジョイント解析(多変量)
- 1-B-3 投資家の主観性を考慮したポートフォリオ選択問題(つくばOR学生発表(2))
- 各需要点への輸送コストの最適化を目的としたファジィ輸送問題(生産・在庫管理(2))
- DEAにおける特異値分解の活用について(意思決定(2))
- 1-B-5 Copulaを用いた競合リスクの識別可能性問題の応用解析(つくばOR学生発表(6))
- A Simple Relationship with the Number of Cells on a Coverage Process in the Boolean Model of CDMA Wireless Commmunications
- 1-E-8 ファジィクラスタリングを用いた食材分類による献立作成支援(組合せ最適化(2))
- 環境整備計画策定における評価者の曖昧さを合意形成に活用できる情報システム(食糧・環境問題とOR)
- 消費者動向を考慮した環境配慮型製品の開発支援システム(食料と環境問題のOR)
- 作物栽培環境・品質データからのデータマイニング手法(食料と環境問題のOR)
- 施設の勧誘力を考慮した競合施設配置問題(都市・地域(3))
- ファジィ配置問題
- ファジィ距離をもつ施設配置問題(確率・ファジィ)
- 需要点の位置がファジィである施設配置問題(ファジィ)
- ファジィ概念を用いた非対称距離施設配置問題
- 障害物のある非対称距離施設配置問題(配置問題)
- 方向制約を伴う施設配置問題(数理計画モデルにおける最適化理論)
- A-距離によるMINI MAX型施設配置問題(組合せ)
- 方向制約のあるMIN MAX型施設配置問題II : 距離が非対称な場合(グラフ・ネットワーク)
- 腐敗し易い商品に対するLIFO配分問題
- 燃料制限のある車の径路決定
- 先行関係のある1機械スケジューリング問題の解法
- 確率的納入リードタイムを有するPerishable Inventory Controlに関する特性
- 重み付きミニマックス実数値フロー
- 重み付きミニマックス・フローの多項式アルゴリズム
- 2-G-5 多目的確率計画問題に対する重み幅を考慮した重み係数法による効率的解法(意思決定(2))
- 不確実・不確定状況下でのマルチシナリオポートフォリオ選択問題 (特集 複雑かつ多様な社会システムの最適化)
- 収益率にいくつかの可能性を考慮したポートフォリオ選択問題(モデリングと最適化の理論)
- 2-F-11 線形計画問題に推定式制約を含んだ逆凸計画問題の大域最適解の導出(数理計画(2))
- 1-C-6 コンジョイント解析を用いた離散構造解析(意思決定)
- 劣化システムに対する, 小修理を考慮した最適保全政策
- 2変量ショックモデル : NBU及びNBUE性と正の相関性
- 修理人一人で同時故障が存在する場合のM+1-of-N:Gシステムの解析
- 必要不可欠でない需要に対する競合施設配置問題(線形計画・非線形計画(1))
- ファジィランダムコストをもつボトルネック型スパニングツリー問題(線形計画・非線形計画(1))
- 貨物輸送形態転換問題の非線形計画法による解析(公共問題(1))
- 2種類の需要と曖昧な固定費用を持つ腐敗しやすい商品の在庫問題(生産・在庫(1))
- 予防保全を考慮した1ユニットシステムの最適検査方策
- A Project Network Scheduling Problems with Fuzzy Precedence Relation
- FUZZY RESOURCE CONSTRAINED MULTI-MACHINE SCHEDULING PROBLEM
- ファジィコストをもつ最小木問題の一定式化(グラフ・ネットワーク(1))
- CAPMを用いたファジィポートフォリオ問題(金融(1))
- ファジィランダム・ミニマムスパニングツリー問題(グラフネットワーク(1))
- コヒーレント・システム(信頼性とOR)
- 2-ユニットシステムの最適取替政策
- 一般分布をもつ2-ユニット並列システム
- DEAを用いたConjoint解析(DEA(1))
- 多目的等価並列機械スケジューリング問題(スケジューリング(2))
- 2目的 MPM オープンショップスケジューリング問題(連続と離散の最適化数理)
- 2目的MPMオープンショップスケジューリング問題(生産計画(1))
- n/m/I/L_及びn/2/F/L_スケジューリング問題に対する近似アルゴリズムのバウンドについて
- 特集にあたって(食料問題とOR)
- 2-E-3 ウェーブレット変換を用いた音声電子透かし埋め込み位置の最適化(組合せ最適化と応用(2))
- 設置に費用を伴う施設の競合配置問題(組合せ最適化(1))
- 設置に費用を伴う施設の競合配置問題(組合せ最適化(4))
- ファジィ数の表現とファジィ微分
- ネットワーク信頼性重要度を計算するアルゴリズムの拡張(信頼性(1))
- グラフ変換によるmarginal reliability importance計算の効率化(信頼性(2))
- 競合環境の下で施設の質を考慮した最適配置問題(多目的計画・施設配置)
- 計画期間がランダムな逐次配分問題
- 劣化する製品の逐次配分問題
- 並列冗長システムにおける逐次部品取替え問題
- ターゲットが2種類の逐次配分問題
- 全部分ネットワークの信頼度計算アルゴリズム(組合せ(2))
- 総合信頼度を考慮したネットワーク設計問題(信頼性)
- ネットワーク信頼度計算における変換・分割の適用(信頼性)
- ネットワーク信頼度計算におけるネットワーク分割(信頼性(2))
- 競合状態の下での施設配置問題(都市(1))
- 提携の組まれ易さを考慮したある交渉集合について(ゲーム理論(2))
- 不確実性を含む交渉集合について(不確実性を含むシステムにおける最適化手法)
- 不確実要素を含む協力ゲームの解について(ゲーム理論(1))
- 可能性測度に基づくFuzzy Sharing Problem(区間解析・ファジィ)
- The Extention of the Fuzzy Two Stage Problem(ファジィ(1))
- ファジィ二段階問題(数理計画)
- ファジィ・スパニング・ツリー問題(グラフ・ネットワーク)
- 動的職捜しモデルにおける不確実性効果
- 設備配置問題におけるサンプル情報の期待価値
- OA雑感
- 確率ネットワークのグラフ的分解
- 競合環境下における施設配置問題(組合せ最適化(1))
- 確率条件スパニング・ツリー問題
- 正規変量を重みに持つ最小張り木
- マルコフ解析, 森村英典・高橋幸雄 著, 日科技連出版社
- 部分的に確率的制約条件をもつE-モデルの一解法
- 一般化確率条件計画問題
- ファジィランダム線形ナップサック問題
- Hideo Tanaka and Peijun Guo 著, Possibilistic Data Analysis for Operations Research, Physica-Verlag (A Springer-Verlag Company), 1999年2月, B6判, DM98'
- 確率計画法 : 多様化時代の数理計画法 第3回