同一並列機械ロットスケジューリング問題への列生成法の適用
スポンサーリンク
概要
- 論文の詳細を見る
同一性能の機械が複数並ぶ一工程並列機械問題をとりあげ, 複数品種の所与の需要を最小費用で満たす生産ロットサイズとスケジュールを, バックオーダと段取り時間を考慮して決定する問題を考える.本研究では, この問題を一般集合分割問題とみなし, この問題の連続緩和問題の最適性の判定の際に必要な列を逐次生成する「列生成法」によって下界値を算出する方法を適用する.その際に, 最適性判定の問題が各品種毎の並列機械問題になることを示し, これを動的計画法によって定式化する.そして, これらをもって下界値を計算しつつ, 生成された列を用いて実行可能解を生成する手順を組み合わせて, 上界と下界の両者を算出するするアルゴリズムを構築する.数値実験によって, この手順とラグランジュ緩和法による近似解法を比較する.その結果, ラグランジュ緩和法に比べて計算時間はかかるが, 元の問題の線形緩和問題の最適性が判定できたと同時に元の問題の最適解が得られる公算が高く, ラグランジュ緩和法に対してパラメータの設定が不要であるなどの点で, 安定して良い精度のスケジュールを生成可能であることを明らかにした.
- 社団法人日本経営工学会の論文
- 2004-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))
- 鉄道乗務員スケジューリング問題に対する解法とその評価