遺伝的局所探索法によるジョブショップスケジューリング問題の解法
スポンサーリンク
概要
- 論文の詳細を見る
ジョブショップスケジューリング問題(JSSP)はNP-困難な組合せ最適化問題の中でも特に難しい問題の1つとされている. 本論文では, JSSPの近似解法として, 局所近傍探索と遺伝的アルゴリズム(GA)との組合せによる多段階探索交叉GA (MSXF-GA)を提案する. MSXF-GAは, アクティブスケジュールのクリティカルブロック(CB)上の作業の移動に基づく近傍であるアクティブCB近傍に基づく近傍探索と, 問題空間の距離と近傍構造に基づく交叉である多段階探索交叉(MSXF)を用いたGAから構成される. さらに, アクティブスケジュールに対し「スケジュールの反転」という概念を導入し, 与えられた問題に適した方向を適応的に選択する機構を取り入れて, 解法の高速化を図る. MSXF-GAを含むいくつかの解法をジョブショップスケジューリング問題(JSSP)のべンチマーク問題に適用したところ, 高品質の解が高速かつ安定して求まるという, MSXF-GAの優れた性能が明らかになった.
- 一般社団法人情報処理学会の論文
- 1997-06-15
著者
-
山田 武士
NTTコミュニケーション科学基礎研究所
-
中野 良平
Ntt コミュニケーション科学基礎研究所
-
中野 良平
NTTコミュニケーション科学基礎研究所
-
中中 良平
Nttコミュニケーション科学基礎研究所
関連論文
- 購買行動解析のためのトピック追跡モデル(人工知能,データマイニング)
- 文書集合と著者集合の依存関係を説明する潜在変数モデル(データ工学,Web情報システム)
- ユーザの嗜好の時系列性と先行性に着目した協調フィルタリング(コンテンツ技術,Web情報システム)
- ユーザの興味とオブジェクトのトピックに着目した情報検索モデル(コンテンツ技術,Web情報システム)
- 顧客生涯価値を高めるためのリコメンデーション法(一般セッション,データ工学とメディア理解との融合)
- 顧客生涯価値を高めるためのリコメンデーション法(一般セッション,データ工学とメディア理解との融合)
- Innovatorの発見によるリコメンデーションのパーソナライズ手法の提案(「自動化:推論,発見,学習,データマイニング」及び一般)
- 購買順序を考慮した協調フィルタリング(「自動化:推論,発見,学習,データマイニング」及び一般)
- ベイズ階層言語モデルによる教師なし形態素解析(言語モデル・ウェブ解析)
- 誤り訂正学習による動作認識と個人適応への試み
- 方向性特徴は何故有効なのか? : 抽象図形によるアプローチ(一般セッション4,移動カメラ画像処理におけるパターン認識とメディア理解)
- 知識共有サイトにおける投稿数の乗算確率過程的成長モデル
- グラフ索引構造を用いた高速類似探索(人工知能,認知科学)
- D-4-2 大規模タグクラウドを地形図として可視化するTopigraphy(D-4. データ工学,一般セッション)
- ディリクレ過程混合モデルに基づく離散データの共クラスタリング
- ディリクレ混合過程モデルに基づく半教師有り学習(一般セッション,データ工学とメディア理解との融合)
- ノンパラメトリックベイズモデルによるグラフクラスタリング(一般セッション,データ工学とメディア理解との融合)
- ディリクレ過程混合モデルに基づく共クラスタリング (「プリファレンスモデリングと推薦システム」及び一般)
- 分布が変化するデータにおけるモデル学習法(データマイニング)
- 購買順序を効率的に用いた協調フィルタリング
- 内容と関連するタグの教師なし抽出(「Webインテリジェンス」及び一般)
- K-004 学習者の視点に基づく協調学習履歴の構造化(K分野:教育工学・福祉工学・マルチメディア応用)
- 固有楕円ポテンシャルを利用したラベル付きグラフ可視化の座標計算
- 固有楕円ポテンシャルを利用したラベル付きグラフ可視化の座標計算
- 固有楕円ポテンシャルを利用したラベル付きグラフ可視化の座標計算
- 確率的混合部分空間法 : 混合因子分析を用いたパターン認識法
- 内部状態制約を考慮したリカレントニューラルネットワークの学習
- 確定的アニーリングEMアルゴリズム
- リカレントネットによる有限状態機械の適応的βスケジュール学習法
- アフィン神経力学系の一意表現
- 一般化受理確率関数を備えた確率的局所探索法による多目的最適化
- 混合モデルのための併合分割操作付きEMアルゴリズム
- リカレントニューラルネットワークが生成する力学系
- 確率的混合部分空間法 : 混合因子分析によるパターン認識法
- 遺伝的アルゴリズムを用いたオペレータスケジューリング
- 25a-G-12 大域結合カオス力学系の同期を用いた秘匿通信法
- 併合・分割操作付きEMアルゴリズムとその混合分布推定への応用
- HMEの構成的学習アルゴリズム
- アンサンブル学習における汎化誤差解析
- 確定的アニーリング : もうひとつのアニーリング
- リカレントネットが引き起こす力学系の一意表現
- 遺伝的局所探索法によるジョブショップスケジューリング問題の解法
- 最小分類誤り基準に基づく識別関数のアンサンブル学習
- リカレントネットによる有限オートマトンの適応的アニーリング学習法
- 確定的アニーリングEMアルゴリズム
- クロスエントロピー最小化に基づくネットワークデータの埋め込み(知識処理)
- ニューラルネットを用いた法則発見
- 4層パーセプトロンを用いた質的条件付き重回帰(バイオサイバネティックス,ニューロコンピューティング)
- 社会ネットワーク上の情報伝搬における強影響力ノード抽出の効率化(データマイニング)
- 4層パーセプトロンを用いた名義空間自動分割型重回帰
- 重み双方向クラスタリング学習法 : 最適な共有重み構造をもつニューラルネットを求めて(バイオサイバネティックス, ニューロコンピューティング)
- ニューラルネットを用いたテキストの特徴語抽出(一般)(ニューロインフォーマティックスとは何か)
- 多層パーセプトロンを用いた区分的多項式回帰(一般)(ニューロインフォーマティックスとは何か)
- ニューラルネットを用いたテキストの特徴語抽出
- 多層パーセプトロンを用いた区分的多項式回帰
- 線形変数変換に不変な自乗値ペナルティ項の構成法(知識処理)
- 交差検証誤差最小化による重要重みの発見
- NC2000-44 質的条件付き数法則発見法 : RF6.2アルゴリズム
- 法則発見法RF6.2の生化学データへの適用と評価 (テーマ:「データマイニング--共通データからの知識発見」および一般)
- 質的条件付き数法則発見法のVQと決定木を用いた高速化 (小特集 「発見科学」及び一般演題)
- 線形変数変換に不変な自乗値ペナルティ項の構成法 (小特集 「発見科学」及び一般演題)
- 交差検証誤差最小化による重要重みの発見
- 2次学習アルゴリズムBPQによるリカレントネットワーク学習とガウス混合分布推定
- 2次学習アルゴリズムBPQの分類問題への適用法とその評価
- MDL 原理に基づく新正則化法
- 自乗値ペナルティ項を用いた2次学習アルゴリズム
- 著者の興味と文書の内容の依存関係に着目した潜在変数モデル(「Webインテリジェンス」及び一般)
- LD-005 Relative Innovatorの発見によるパーソナライズ手法の提案(データベース)
- ユーザの網羅性を反映したランキング手法の提案(セッション7:ウェブにおける情報処理,社会システムと知能)
- 3層ニューラルネットにおける2階導関数を用いた学習アルゴリズムの高速化
- 誤り訂正学習による動作認識の試み
- ディリクレ過程混合モデルに基づく離散データの共クラスタリング
- ディリクレ過程混合モデルに基づく離散データの共クラスタリング
- ディリクレ混合過程モデルに基づく半教師有り学習(一般セッション,データ工学とメディア理解との融合)
- ノンパラメトリックベイズモデルによるグラフクラスタリング(一般セッション,データ工学とメディア理解との融合)
- コネクショニストアプローチによる数法則の発見
- HMEの構成的学習アルゴリズム
- 準ニュートン法に基づくElmanネットワークの学習アルゴリズム
- クロスエントロピーに基づくネットワークデータの埋め込み
- 階層的独立固有時間刻み法によるグラフ可視化計算の高速化
- トピックモデルに基づく文書群の可視化
- 購買順序を効率的に用いた協調フィルタリング
- 購買順序を効率的に用いた協調フィルタリング
- D-032 最大エントロピー法に基づく推薦システムでのユーザ行動のモデル化(D分野:データベース)
- 複数対象トラッキングにおける,適応的なパラメータ推定手法(一般セッション,データ工学とメディア理解との融合)
- 複数対象トラッキングにおける,適応的なパラメータ推定手法(一般セッション,データ工学とメディア理解との融合)
- ノンパラメトリックベイズに基づく複数対象時系列のクラスタリングとトラッキング(人工知能,認知科学)
- D-040 ネットワーク索引構造を用いた類似探索と可視化(データベース,一般論文)
- ノンパラメトリックベイズモデル
- フローショップスケジューリング問題の地形解析と遺伝的局所探索による解法
- ジョブショップスケジューリング問題とクリティカルブロックSA法
- 質的変数で条件付けられた数法則の発見法
- 24)リカレントネットによる有限オートマトンのアニーリング学習法(ヒューマンインフォメーション研究会)
- リカレントネットによる有限オートマトンのアニーリング学習法
- リカレントネットによる有限オートマトンのアニーリング学習法
- 事例からのルール抽出 : RF2アルゴリズム
- シミュレーテッドアニーリング : 基礎と最新技術
- ノイズを含む事例からのルール抽出 : RF3アルゴリズム
- 統計的機械学習技術による潜在構造の発見(SDN(Software-Defined Network),クラウド,ネットワーク仮想化,サービス品質,コンテンツ配信,一般)
- 統計的機械学習技術による潜在構造の発見(SDN(Software-Defined Network),クラウド,ネットワーク仮想化,サービス品質,コンテンツ配信,一般)