複数の求解戦略を持つリアルタイムスケジューリング法
スポンサーリンク
概要
- 論文の詳細を見る
本稿では,リアノレタイムスケジューリング(real-time scheduling)問題に対するヒューリステイックアルゴリズムRTSAを新たに提案し,既存解法との比較実験により有効性を示す.スケジューリング問題は組み合わせ段通化問題の1つで古くから研究されており,既に多くの結果が知られている,これらの大部分は,処理すべきタスク集合,各タスクを処理する際の制約(資源制約やタスク間の先行関係等),処理時間や納期等のスケジューリングに必要な情穀が全て既知であることを前提としたものである.これを静的(static)スケジューリングと呼ぶ.それに対して,近年リアルタイムスケジューリングと呼ばれる動的(dynamic)スケジューリングが注目されている.例えば,処理すべきタスクが随時到着してくる場合や,タスクの処理時間が明確にわかっていない(最悪処理時間は既知であるがそれが実際の処理時間とは異なり,実際の処理時間は処理してみないとわからない)場合などのように,スケジューリングに必要な情報の全てが予めわかっている訳ではなく,必要に応じてスケジューリングの更新を繰り返すことになる.これが動的スケジューリングであるが,これに更にタスクを処理しつつ再スケジューリングを行う(すなわち,次に処理すべきタスクを決定していく)といった,リアルタイム性が要求される場合をリアルタイムスケジューリングと呼んでいる.リアルタイムスケジューリングに関する既知結果は,例えば[9]等を参照されたい.実行可能なスケジュールを得るために,次に処理すべきタスクの決め方を求解戦略(strategy)と呼ぶ.既存のリアルタイムスケジューリング法では,求解戦略に利用するための種々の評価基準等は用意されてはいるものの,求解戦略自体は固定されている.タスクの生成,消滅をはじめとしてスケジューリングの対象環境が刻々変化する場合には,状況に応じた求解戦略に変えることは極めて自然なことと思われる.この立場から本稿では,幾つかの評価基準に基づいて,複数の求解戦略を切り換えて適用するスケジューリング法RTSAを提案する。スケジューリングモデルは時間付きペトリネットを用いる.
- 1996-03-11
著者
関連論文
- 抑止辺を持つペトリネットの発火系列問題の解法について(デモ展示・ポスター講演,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 抑止辺を持つペトリネットの発火系列問題の解法について(デモ展示・ポスター講演,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 抑止辺を持つペトリネットの発火系列問題の解法について(デモ展示・ポスター講演,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- A-12-4 トランジション改良選択法に基づくペトリネット最小初期マーキングの効率的構成法(A-12.コンカレント工学,一般講演)
- ペトリネットの最小初期マーキング探索におけるトランジションの効果的選択法(コンカレントシステム, 一般)
- ペトリネットの最小初期マーキングのための動作的デッドロック回避に基づく高速な発見的解法(コンカレントシステム, 離散事象システム, ハイブリッドシステム, 及び一般)
- ペトリネットのサイフォン・トラップ抽出効率化のためのサブネット縮約法(グラフ,ペトリ,ニューラルネット,及び一般)
- ペトリネットのサイフォン・トラップ抽出効率化のためのサブネット縮約法(グラフ,ペトリ,ニューラルネット,及び一般)
- ペトリネットのサイフォン・トラップ抽出効率化のためのサブネット縮約法
- グラフの3-辺連結化について(計算アルゴリズムと計算量の基礎理論)
- グラフの局所辺連結度増加問題に対する近似解法
- グラフのk辺連結化問題に対する新しい近似解法
- 領域分割に基づく並列配線手法
- アナログ回路用多層プリント基板の分離型設計
- 多層プリント基板設計における回路分割の一手法
- 広島大学工学部第二類(電気系)回路システム工学大講座情報回路網工学研究室
- グラフの辺付加問題による耐故障ネットワ-クの構成
- 耐故障ネットワークと辺付加問題(計算アルゴリズムと計算量の基礎理論)
- マ-クグラフの初等P-インバリアントとP-基底
- 予測・修正混雑コスト方式によるスイッチボックス配線手法 (最適化)
- 固定ルーティングネットワークにおける無故障な経由ルート数の評価
- 辺の付加によるグラフの拡大構成問題(グラフ理論とその応用)
- 辺付加によるグラフの拡大構成問題(計算機科学の基礎理論)
- 3-連結グラフの連結点被覆問題 (形式言語理論とオートマトン理論)
- 辺短絡除去問題のNP-困難性について(技術談話室)
- 辺開放除去問題のNP-困難性について
- 平面グラフの点除去による2端子直並列グラフの構成問題(技術談話室)
- 辺の短絡除去による平面グラフ化問題について
- 辺の短絡除去による平面グラフ化問題--最大節点次数がたかだか3の場合(技術談話室)
- 辺の短絡除去による2端子直並列グラフの構成問題(技術談話室)
- 辺の開放除去による2端子直並列グラフの構成問題(技術談話室)
- ステートマシンの接続構造を持つペトリネットの発火系列問題
- ペトリネットの最小初期部分マーキング問題について(グラフ,ネットワークとアルゴリズムおよび一般)
- 階層型グラフに対応したグラフアルゴリズムの視覚的トレースツールの開発(グラフ,ペトリ,ニューラルネット及び一般)
- 階層型グラフに対応したグラフアルゴリズムの視覚的トレースツールの開発(グラフ,ペトリ,ニューラルネット及び一般)
- ペトリネットの最小初期マーキング問題に対する発見的解法
- ペトリネットの最大発火系列問題に対する発見的アルゴリズムFSDB
- ペトリネットインバリアント算出のためのFourier-Motzkin法の改良実装
- ペトリネット発火系列問題に対する発見的アルゴリズムFSDTとMAX SAT解法への応用
- ペトリネット発火系列問題に対する発見的アルゴリズムFSDTとMAX SAT解法への応用
- A-12-5 時間付ペトリネットによるスケジューリングに対する発見的解法SDS
- A-12-4 指定プレース集合を含むサポートを持つペトリネットインバリアントの算出法
- 指定ノード集合を含むサポートを持つペトリネットインバリアントの算出アルゴリズムFMSN
- 指定ノード集合を含むサポートを持つペトリネットインバリアントの算出アルゴリズムFMSN
- グラフの最小コスト3-点連結化問題に対する近似アルゴリズム
- ペトリネット発火系列問題の概説
- ペトリネット発火系列問題の概説
- 複数の求解戦略を持つリアルタイムスケジューリング法
- A-12-4 サイフォン・トラップ台に基づくインバリアント算出法
- 指定ノード集合を含むサポートを持つペトリネットインバリアントの算出アルゴリズム FMSN
- 時間付きペトリネットによるスケジューリングのための発見的アルゴリズムSDS
- 時間付きペトリネットによるスケジューリングのための発見的アルゴリズムSDS
- A-12-3 ペトリネットの最適発火系列問題に対する発見的解法OFSD
- On Forming a Series-Parallel Graph by Removing Nodes of a Planar Graph (Studies on Computational Complexities and Related Topics)
- 一般ペトリネットにおける単一指定プレースを含む極小サイフォン抽出法
- 一般ペトリネットにおける極小デッドロック抽出法
- ペトリネットの発火系列問題に対する近似アルゴリズム
- グラフの多重辺付加を許さない4辺連結化問題
- グラフの指定点集合に対するk辺連結化問題
- グラフの多重辺付加を許さない辺連結化問題
- グラフの多重辺付加を許さない4辺連結化問題
- ペトリネット発火系列問題に対する発見的アルゴリズムFSDTとMAX SAT解法への応用
- ペトリネット発火系列問題に対する発見的アルゴリズムFSDTとMAX SAT解法への応用
- ペトリネットの発火系列問題に対する新しい発見的解法FSD
- ペトリネットの指定プレース集合を含むサイフォン抽出法
- ペトリネットの発火系列問題に対する発見的解法FSD
- ペトリネットの発火系列問題に対する新しいヒューリスティックアルゴリズム
- ペトリネットの発火系列問題に対する新しいヒューリスティックアルゴリズム