周期的なタイムスロット付きジャストインタイムスケジューリング問題のヒューリスティックアルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
与えられた納期ちょうどにジョブの処理を完了する様なスケジュールを求める問題をジャストインタイムスケジューリング問題と呼ぶ.我々は周期的なタイムスロットという現実的な仮定を設けたジャストインタイムスケジューリング問題を取り扱う.本稿ではまず,P〓NPの仮定の下で近似不可能であることを証明する.次に,機械数が1である場合のヒューリスティックアルゴリズムを提案する.アイデアは最小費用流問題への帰着であり,最小費用流を求める以外はフロー値の単純な更新をするだけなので,ヒューリスティックアルゴリズムは高速である.実際に計算機実験も行って確かめた.また,ある制約の下でヒューリスティックアルゴリズムが最適解を返すことを示す.さらに,ある制約の下でヒューリスティックアルゴリズムの近似比を与える.
- 社団法人情報処理学会の論文
- 2004-03-19
著者
-
平石 邦彦
北陸先端科学技術大学院大学 情報科学研究科
-
千葉 英史
北陸先端科学技術大学院大学情報科学研究科
-
平石 邦彦
北陸先端科学技術大学院大学情報科学研究科
-
平石 邦彦
北陸先端科学技術大学院大学
関連論文
- ブーリアンネットワークにおける可制御性判定のための多項式時間アルゴリズム(システムバイオロジー,システムバイオロジー,一般)
- ICカードを利用した教育環境における報奨システムの提案(e-Learningにおける学習評価/一般)
- 整数計画法を用いた確率ブーリアンネットワークの最適制御 (SSI2009特集--次世代のシステム知を拓くシステム・情報技術)
- 搬送計画問題に対するネットワーク理論を利用したアプローチ
- 形式検証技術の数理 : 安心・安全なシステム構築に向けて
- カラードペトリネットによるワークフローシステムのモデル化と検証
- 有限時間区間に対するハイブリッドシステムの離散抽象化
- 離散状態の流体化によるシステム検証(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般)
- ブーリアンネットワークモデルによる遺伝子発現ネットワークの可制御性解析 (第21回 回路とシステム軽井沢ワークショップ論文集) -- (ネットとシステム)
- 連続化近似を用いたワークフローの性能評価(グラフ,ペトリ,ニューラルネット及び一般)
- 混合論理動的システム表現の改良に関する研究(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般)
- 研究室配属のためのシラバスシステムの提案と試作(セッション4 : 教育・学習支援)
- AP-4-9 これからのコンカレント技術 : システムバイオロジー(AP-4.コンカレント技術の現在・過去・未来,パネル討論,ソサイエティ企画)
- A-3-9 温度並列SAのシーケンスペアによるパッキング問題への適用(A-3.VLSI設計技術,一般講演)
- 記号計算に基づくハイブリッドシステムの解析
- 周期的なタイムスロット付きジャストインタイムスケジューリング問題のヒューリスティックアルゴリズム
- D-7-6 遺伝子転写制御領域に含まれる特異的文字列の解析とDNAマイクロアレイデータを用いた遺伝子間の依存関係推定(D-7. MEとバイオサイバネティックスA)
- D-7-7 転写制御領域の解析と破壊株データからの遺伝子の依存関係推定
- ハイブリッドシステムの定性的解析について
- エージェント指向ペトリネットPN^2の効率的解析について : 動作を保存する縮約法
- 連続化近似を用いたワークフローの性能評価(グラフ,ペトリ,ニューラルネット及び一般)
- ハイブリッドシステムの定性的解析について
- エージェント指向ペトリネットPN^2の効率的解析について : 動作を保存する縮約法
- エージェント指向ペトリネットの理論的解析について
- 離散事象システムの言語安定性について
- ペトリネットによるマルチエージェントシステムのモデル化(ペトリネットの応用特集号)
- 量子計算によるプトリネットの解析について
- 時間付き離散事象システムの時間付き安定性
- 繰り返し囚人のジレンマゲームにおける競合共進化モデルの特性について
- CST2000-1 自動搬送車の動作計画問題のグラフ理論的解法について
- 複数の評価構造の統合について
- A-12-2 キャッシングを用いた状態空間探索におけるダブルワークを抑制する為の状態管理方法
- エージェント侵略の過程と中間的な手をとる戦略の有利性について
- SA-7-5 並行システムの理論モデルにおける並行性の表現について
- フォーシブルな事象をもつ時間付き離散事象システムの時間付き安定性
- 正規言語の学習アルゴリズムを用いたスーパバイザの合成
- 繰り返し連続化囚人のジレンマゲームの提案
- エージェント侵略の過程における中間的な手をとる戦略の有利性について
- ペトリネットは便利な道具
- 時間付き離散事象システムの時間付き安定性
- ペトリネットによるコンカレントシステムの効率的解析について (コンカレント・コラボレーション技術論文小特集)
- グループ意志決定におけるAHP重要度の感度係数を用いたトレードオフ分析支援法
- グループ意思決定における重要度の感度係数を用いたトレードオフ分析支援について(意思決定・AHP(2))
- 高水準ペトリネットによるソフトウェア開発方法論
- 確率ブーリアンネットワークの解析と制御のための計算手法
- 会議システムと合意ベース手法を用いた意思決定支援について
- 時間ペトリネットの状態空間の縮約について
- A-12-12 遷移関係に基づくハイブリッドモデル予測制御の近似事前解法(A-12.コンカレント工学,一般セッション)
- A-12-11 確率ハイブリッドシステムの確率拘束付き最適制御(A-12.コンカレント工学,一般セッション)
- ハイブリッドシステムにおけるモデル予測制御--遷移関係に基づく近似事前解法 (システム数理と応用)
- ハイブリッドシステムにおけるモデル予測制御--遷移関係に基づく近似事前解法 (信号処理)
- ハイブリッドシステムにおけるモデル予測制御--遷移関係に基づく近似事前解法 (VLSI設計技術)
- ハイブリッドシステムにおけるモデル予測制御--遷移関係に基づく近似事前解法 (回路とシステム)
- 2分決定グラフを用いた離散事象システムの効率的な検証方式について
- 整数計画法を用いた確率ブーリアンネットワークの最適制御
- ペトリネットモデルに対する線形論理の完全性
- AS-3-2 時間,資源の制約を考慮したビジネスプロセスの検証(AS-3.ワークフローとビジネスプロセス管理への数理的アプローチ,シンポジウムセッション)
- システムと信号処理サブソの新たな展開を目指して(システムと信号処理及び一般)
- システムと信号処理サブソの新たな展開を目指して(システムと信号処理及び一般)
- システムと信号処理サブソの新たな展開を目指して(システムと信号処理及び一般)
- システムと信号処理サブソの新たな展開を目指して(システムと信号処理及び一般)
- 研究の特性情報を用いた研究者グループ生成支援システム
- 半順序法による並行システムの効率的な検証について
- 性能評価モデルとしてのペトリネットについて
- 関連度行列とファジィ理論を統合した意思決定について
- 非有界な状態空間をもつ並行システムに対する縮約状態空間の生成について
- TA-2-1 「高水準ペトリネットのシステムとソフトウェア開発への応用」1.高水準ペトリネットとは(コンカレント工学研究専門委員会チュートリアル,TA-2. 高水準ペトリネットのシステムとソフトウェア開発への応用,チュートリアル講演)
- 構造的性質を用いて並行システムを効率的に検証する方法について
- ネット理論の現状と課題
- ハイブリッドシステムにおけるモデル予測制御 : 遷移関係に基づく近似事前解法(システムと信号処理及び一般)
- ハイブリッドシステムにおけるモデル予測制御 : 遷移関係に基づく近似事前解法(システムと信号処理及び一般)
- ハイブリッドシステムにおけるモデル予測制御 : 遷移関係に基づく近似事前解法(システムと信号処理及び一般)
- ハイブリッドシステムにおけるモデル予測制御 : 遷移関係に基づく近似事前解法(システムと信号処理及び一般)
- システム部門からシステム・情報部門への展開
- 1-D-7 医療・介護サービスにおける音声つぶやきコミュニケーションによる連携業務のモデル化(特別セッション サービスサイエンス)
- 看護・介護サービスにおける複雑なプロセスのモデル化にむけて (回路とシステム)
- 看護・介護サービスにおける複雑なプロセスのモデル化にむけて (システム数理と応用)
- 計算ツールを用いた確率ブーリアンネットワークの解析と制御 (特集 確率システム制御 : 基礎理論,アプローチ,そして新展開)
- 仮想フィールドを用いた看護・介護サービスにおける音声つぶやきコミュニケーションの評価実験について (システム数理と応用)
- ハイブリッドシステムにおけるモデル予測制御遷移関係に基づく近似事前解法
- 計算ツールを用いた確率ブーリアンネットワークの解析と制御
- 看護・介護サービスにおける複雑なプロセスのモデル化にむけて(グラフ,ペトリネット,ニューラルネット,及び一般)
- 看護・介護サービスにおける複雑なプロセスのモデル化にむけて(グラフ,ペトリネット,ニューラルネット,及び一般)
- 複数の確率的遅延を有するネットワーク化システムの制御
- 複数の確率的遅延を有するネットワーク化システムの制御
- 離散値入力をもつ大規模システムに対する最適制御問題の一解法 (信号処理)
- 外部刺激を考慮した遺伝子ネットワークの最適制御
- 音声つぶやきによる看護・介護の時空間コミュニケーション : 情報スーパーバイザ制御の提案
- 音声つぶやきによる看護・介護の時空間コミュニケーション : 情報スーパーバイザ制御の提案
- 遷移関係に基づくハイブリッドシステムの近似双模倣
- ネットワーク化制御系のためのSelf-Triggeredモデル予測制御
- 確率的拘束を有する確率ハイブリッドシステムのモデル予測制御 (最適化とその応用)
- 離散値入力をもつ大規模システムに対する最適制御問題の一解法 (システム数理と応用)
- 離散値入力をもつ大規模システムに対する最適制御問題の一解法 (VLSI設計技術)
- 離散値入力をもつ大規模システムに対する最適制御問題の一解法 (回路とシステム)
- AS-4-7 1ステップ予測区間の最適化によるSelf-Triggered制御(AS4.高信頼制御を支える無線通信技術,シンポジウムセッション)
- Diagnosis of Stochastic Discrete Event Systems Based On N-gram Models With Wildcard Characters (システム数理と応用)
- 仮想フィールドを用いた看護・介護サービスにおける音声つぶやきコミュニケーションの評価実験について
- 看護・介護サービスにおける複雑なプロセスのモデル化にむけて
- イベントログに基づいた行動型サービスの分析(システムと信号処理及び一般)