総所要時間最小制約二機械フローショップ問題に対する分枝限定法の改善
スポンサーリンク
概要
- 論文の詳細を見る
本稿では,総所要時間最小のスケジュールの中で総滞留時間を最小化するものを求める二機械フローショップ問題を考える.この問題は,複数の目的関数に優先順位が与えられる,階層的多目的スケジューリング問題の一つとして知られている.一般にこの問題はNP困難であり,分枝限定法がT'kindt et al.により提案され,ジョブ数23の問題まで効率的に解くことができたと報告している.本稿では,子問題表現の一般化と新しい優越関係に基づく分枝限定法の改善を行う.この改善により,ジョブ数29の問題まで効率的に解くことができるようになった.さらに,提案した分枝限定法は,T'kindt et al.の分枝限定法および混合整数計画問題を解く商用ソフトウェアと比較した結果,最も高速であり,かつ最も大規模な問題を扱うことができた.
- 2005-10-15
著者
関連論文
- 汎用並列分枝限定法ツールPUBBを用いた最大クリーク問題の厳密解法(整数計画(1))
- 高次元空間における安定集合多面体(整数計画(1))
- 混合整数計画ソルバーの並列化(パラレルコンピューティングの応用)
- 2次割当て問題への適用におけるIntegral Basis Methodの改良の提案
- 2-F-10 Integral Basis Methodにおける変数選択規則と緩和問題(数理計画(2))
- 2次割当問題への適用によるIntegral Basis Methodの改良の提案(セッション3)
- 総所要時間最小制約二機械フローショップ問題に対する分枝限定法の改善
- 総完了時刻最小化二機械フローショップ問題に対する優越条件(組合せ最適化)
- A Branch-and-Bound Algorithm for a Class of Three-machine Flowshop Problems (Essays in Commemoration of the Fortieth Anniversary of Department of Management Science)
- A Branch-and-Bound Algorithm for a Class of Three-machine Flowshop Problems (〔神戸商科大学〕管理科学科創立40周年記念号)
- 総滞留時間最小化1機械スケジューリング問題に対する優越テストについて(スケジューリング)
- 小売業におけるサービスタイム開始の判断基準に関する一考察(在庫管理)
- 階層的3機械フローショップ問題(スケジューリング)
- 2次錐計画法によるディジタルフィルタの設計法
- 2次割当問題に対するIntegral Basis Method(離散最適化)
- CPLEX MIP OptimizerのPUBB2フレームワークによる並列化について(整数計画(2))
- 混合整数計画問題の解法における前処理の効果検証(整数計画(2))
- ON GROTSCHEL-LOVASZ-SCHRIJVER'S RELAXATION OF STABLE SET POLYTOPES
- PUBBによるPCクラスタ環境における並列分枝限定法 (新しいパラダイムとしてのアルゴリズム工学)
- PCクラスタ環境における並列分枝限定法(数理計画(2))
- 汎用並列分枝限定法ツールPUBBによる組合せ最適化問題の厳密解法 (特集「計算と最適化」)
- 最近の混合整数計画ソルバーの進展について(最適化技術の深化と広がり)
- 1機械,1種類ジョブの最適バッチスケジューリング(スケジューリング)
- 平成23年秋季研究発表会ルポ(情報の窓)
- 整数計画法による定式化入門(はじめよう整数計画)