ジョブショップスケジューリングに対する機械分解によるラグランジュ緩和
スポンサーリンク
概要
- 論文の詳細を見る
Luhや米田らは, 納期系の評価尺度を想定した上で, 機械能力制約を緩和することで問題をジョブ毎に分解する(ジョブ分解)ラグランジュ緩和法を提案し, その実用性を立証している.一方, 長谷部らは作業の先行関係制約を緩和して問題を機械毎に分解する(機械分解)ラグランジュ緩和法を提案している.本研究では, ジョブショップスケジューリング問題を取り上げ, 機械分解に基づくラグランジュ緩和法(下界値と上界値の算出法)のプロトタイプを示した.次に, ジョブ分解, 機械分解という2種類のラグランジュ緩和法の特質を整理するとともに, 計算実験をもとに両者の比較評価を行なった.また, 機械分解で発生する解の振動に関して作業納期の導入によるいくつかの対策を施し数値実験を行い, その効果を調べた.これらから, i)振動対策を施さない機械分解は, 極めて振動が大きくジョブ分解に劣る, ii)作業納期の導入は, その納期の設定如何によっては良い上界値を得られることもあるが, 期待されるほどの振動の抑制は望めない, などの結果を得た.
- 社団法人日本経営工学会の論文
- 2003-06-15
著者
-
今泉 淳
東洋大学経営学部
-
森戸 晋
早稲田大学創造理工学部
-
柏木 雅英
東洋大学経営学部
-
今泉 淳
東洋大学
-
森戸 晋
早稲田大学・理工学部・工業経営学科
-
柏木 雅英
九州大学大学院システム情報科学研究科
-
森戸 晋
早稲田大学 創造理工学部
-
新井 智弘
早稲田大学
-
森戸 晋
早稲田大学
関連論文
- 機関車の基地内留置計画に対する整数計画アプローチ
- GPUを利用した非線形方程式の並列全解探索法(実用)
- 鉄道における乗務員運用計画の集合被覆問題に対する Wedelin の解法の適用
- 単純リコースを有する整数確率計画問題の Dynamic Slope Scaling Procedure を用いた解法
- 1-E-1 固定費を含む確率計画問題の解法(数理モデル)
- 2-F-8 リコース関数に固定費を含む確率計画問題(数理計画(2))
- 2-B-8 数理計画法を用いた機関車の基地内留置計画の最適化(交通(2))
- 2-C-2 確率計画法による予防的・緊急的在庫転送併用方策の定式化(在庫管理)
- 1-S-1 鉄道乗務員交番作成に対するCapraraのラグランジュ緩和アプローチ : 日本の鉄道への適用可能性の検討(鉄道とOR)
- 2-E-5 Location-Routing Problemに対するLagrange緩和と列生成法の併用アプローチ(離散最適化(2))
- 分散を考慮した2段階確率計画問題
- 分散を考慮した2段階確率計画問題
- 二段階数理計画アプローチによる鉄道車両運用計画の策定
- 2-B-7 ダイヤ乱れ時の機関車運用計画修正問題に対する列生成アプローチ(交通(2))
- 鉄道乗務員スケジューリング問題に対する解法とその評価
- 2-B-9 分散を考慮した確率計画問題(大域的最適化)
- 2-E-12 列車ダイヤ遅延時の乗務員スケジュール修正問題(スケジューリング(2))
- 2-E-11 数理計画による鉄道車両運用計画の策定(スケジューリング(2))
- 2-D-11 乗務員運用計画問題に対する便乗削減の定式化と解法(輸送・交通(3))
- 2-B-1 乗務員運用計画問題の列生成子問題に対するPull型ラベリング解法と性能評価(数理計画(2))
- モデルが見えるとき(モデリング-最適化モデリング-)
- 乗務員運用計画の集合被覆問題に対するWedelin解法の適用(タイムテーブリング)
- 二段階数理計画アプローチによる鉄道車両運用計画の策定
- 可変バックオーダ比率をもつ確率的な部分バックオーダシステムに関する研究
- GPGPUによる非線形方程式の全解探索法
- 有限ステップで停止する全解探索アルゴリズムの改良について : Newton法の修正量を利用した改良法
- 変数分離形非線形方程式の解の非存在の厳密な数値的検証法と全解探索への応用
- A-2-5 非線形方程式の全解探索問題におけるAffine Arithmeticを用いた非存在領域の除去法
- 多段階ロットサイズ問題に対する妥当な不等式と強い定式化(組合せ理論)
- 定期的輸送調整によるレンタル製品在庫管理のモデル分析(流通・物流)
- 段取りを費用を考慮したカッティング計画問題(生産・スケジューリング)
- 複素解析を用いた高速精度保証付き自動積分法
- Clusteringによるグラフ分割問題へのメタ解法(グラフ・ネットワーク(2))
- Experimental analysis of a semidefinite programming approach to the graph partitioning problem
- Fast Implementation and Experiments of n Queens' Problem
- Parameter Optimization of the Tabu Search for the Maximum Clique Problem
- An Approximate Algorithm for the Maximum Stable Set Problem
- グラフ分割問題に対するTabu Searchの数値実験(グラフ・ネットワーク(2))
- 鉄道の運用計画問題に対する整数計画法によるアプローチ(鉄道のスケジューリング問題)
- 鉄道の乗務員運用計画作成問題に対する列生成法の適用
- アフィン演算を用いた常微分方程式の初期値問題の精度保証付き解法
- アフィン演算の実装方法について(通信と非線形特集及び一般)
- アフィン演算における乗除算について
- アフィン演算における最良乗算について
- ベキ級数演算技法を用いた不定積分の精度保証付き数値計算
- A-21 Affine Arithmeticにおける最良乗算の実現(数値計算,A.アルゴリズム・基礎)
- A-2-24 倍角公式を用いた三角関数の精度保証
- A-2-22 ベキ級数演算を用いた精度保証付き不定積分
- A-2-4 アフィン演算における多項式の評価について
- 新郵便処理システムのシミュレーション分析(公共システムとOR)
- 教育の国際水準達成 : 早稲田大学経営システム工学科における取り組み
- 教育の国際水準達成 : 早稲田大学経営システム工学科における取り組み(JABEE)
- FMSの投入優先順序決定のためのシミュレーション/準最適化アプローチ
- 同種ジョブの反復のあるジョブショップにおける作業時間ベース投入優先規則の実験的評価
- FMSの投入優先順序決定のためのシミュレーション : 最適化アプローチ(特別セッション(3)スケジューリング)
- An FMS Dispatching Priority Problem and Combined Simulation/Optimization
- FMSの納期遅れ最小化のための投入優先順序の決定
- 2-B-7 21世紀モノ造りマネジメント研究部会終了報告(生産管理)
- COM・SCM・スケジューリング研究部会報告(ペーパーフェア)
- 待ち行列型モデルとシミュレーション : シミュレーション・モデル化の理論を目指して(待ち行列-モデリングと解法-)
- シミュレーション・モデル化の「理論」を目指して : 代替モデル/プログラムの認識(シミュレーション)
- 特集に当って(シミュレーション)
- 特集に当って(シミュレーション)
- 数理計画とシミュレーションのハイブリッド法 : ロジスティクス計画への応用を中心として(資源管理の理論と実際)
- 同一並列機械ロットスケジューリング問題への列生成法の適用
- 一般上限制約付き大規模集合被覆問題 : 鉄道の乗務員運用計画に対するラグランジュ緩和アプローチ(鉄道のOR(1))
- 鉄道の多拠点乗務員運用問題に対する列生成アプローチ(鉄道のOR(1))
- ジョブショップスケジューリングに対する機械分解によるラグランジュ緩和
- 同一並列機械ロットスケジューリング問題への列生成法の適用(生産管理(1))
- ジョブの分岐と時間重複生産を許すスケジューリング問題のジョブの諸性質(グラフ・スケジューリング)
- ジョブの分岐と時間重複生産を許す2工程並列機械フローショップスケジューリング問題 : 納期遅れ最小化に対するラグランジュ緩和に基づくヒューリスティックアプローチ
- 最大利得部分木問題に対する近似解法および厳密解法(マルチメディアネットワークシステム)
- ロジスティクス計画におけるシミュレーションと最適化の融合(統合オペレーション)
- 分岐型ジョブのスケジューリング問題に対するラグランジュ分解・調整法 (スケジューリングの革新的アルゴリズム : ラグランジュ分解・調整法)
- 輸送ロットを考慮したパレットの空(から)輸送における必要系内数の決定(生産・在庫管理(1))
- 組立工程が存在するフローショップスケジューリング問題に対する間接列挙アプローチ
- 組立工程が存在するフローショップスケジューリング問題に対する間接列挙アプローチ
- ジョブの分岐と重複生産を許す2工程並列機械フローショップスケジューリング問題 : 分枝限定法によるアプローチ
- ジョブの分岐と重複生産を許す2工程並列機械フローショップスケジューリング問題 : 分枝限定法によるアプローチ
- 郵便輸送における空パレットの効率的回送
- 「離散系シミュレーション」研究部会報告(ペーパーフェア)
- システム・シミュレーション研究部会終了報告(ペーパーフェア)
- パソコン版ダンプトラック運行シミュレータの開発と走路区間のモデル化
- 鉄道の乗務員運用計画作成問題に対する列生成法の適用
- モデル分析に基づく郵便区分輸送形態の最適化(2) : 区分機設置の最適化とシミュレーション(シミュレーション)
- 郵便輸送ネットワークの階層的計画(輸送・配送)
- 郵便輸送におけるパレット交流データの推定と空パレット回送先固定輸送方式の在庫シミュレーション(流通・物流)
- モデル分析に基づく郵便区分輸送形態の最適化(流通・物流)
- 最小滞在時間問題(2) : 分枝限定法の適用と3教員緩和(組合せ最適化(2))
- 最小k部分木問題に対する分枝限定法の適用(グラフ・ネットワーク(1))
- 部分巡回路型の問題に対する有向部分1-木緩和と下界値上昇法(組合せ最適化(4))
- 1つの連結成分を持つ最小有向部分木問題II(グラフ理論)
- 非対称TSPにおける最小有向1-木を用いた下界値上昇法(組合せ)
- 一つの連結成分を持つ最小重み有向部分木問題(数理計画)
- 単一制約付最大集荷問題のアルゴリズム
- ネットワークフローモデルによる鉄道の終端駅の能力評価
- 2-D-4 訪問看護スケジュール作成への数理計画アプローチ(スケジューリング(2))
- 2-D-6 乗務員運用のための最適化モデル分析 : 貨物鉄道における基地の配置と担当範囲を中心として(スケジューリング(2))
- 2-D-5 鉄道における乗務員交番作成問題に対する列生成法の適用(スケジューリング(2))
- 鉄道乗務員スケジューリング問題に対する解法とその評価