時間効用関数

時間/効用関数( TUF )、旧称時間/価値関数は、アクション(計算タスク、機械動作など) が完了時間に応じて生み出すアプリケーション固有の効用を指定します。[ 1 ] ^{[ 2 ] TUFとその}効用解釈 (意味論)、尺度、値は、アプリケーション領域固有の主題知識から導き出されます。効用の解釈の例 (ただし、唯一のものではありません) は、アクションの相対的な重要性であり、これは通常、その適時性とは無関係です。TUF として表される従来の期限は特殊なケースであり、期限時に効用が 1 から 0 に下がるステップ、つまり重要性のない適時性です。TUF はより一般的で、アプリケーション固有の形状と効用値が両側にある臨界時間があり、その後は増加しません。さまざまな研究者や実務家による確実なリアルタイムとソフトなリアルタイムの定義も、TUF モデルの特殊なケースとして表すことができます。

複数の TUF 制約付きアクションのスケジューリングの最適性基準は、これまで文献では最大効用蓄積( UA ) のみでした。たとえば、個々のアクションの完了効用の (おそらく期待される) 加重和です。これは、重要な時間に関する適時性を考慮に入れています。TUF/UA パラダイムとそのユースケースが進化するにつれて、追加の基準 (たとえば、エネルギー、予測可能性)、制約 (たとえば、依存関係)、システム モデル、スケジューリング アルゴリズム、および保証が追加されました。より明確に言うと、TUF/UA では、適時性そのものとは対照的に、状況に応じたアプリケーションのQoS ^{[ a ]}が得られるように、蓄積効用、適時性、予測可能性、およびその他のスケジューリング基準と制約を互いにトレードオフすることができます。TUF/UA パラダイムのインスタンスは、さまざまなアプリケーション ドメインで使用されており、最も頻繁には軍事システムで使用されています。

TUF/UA パラダイムは、従来型のリアルタイムの概念や手法では十分に表現できないさまざまな軍事アプリケーションの特定のアクションの適時性、適時性の予測可能性、およびアプリケーションの QoSベースのスケジューリングのニーズ (たとえば、期限のない動的に適時性が重要なシステム) や負荷耐性 (たとえば、ルーチンアクションの過負荷を受けるシステム) に対処するために最初に作成されました。このようなアプリケーションの重要な一般的な例のクラスは、ミサイル防衛 (概念的には^{[ 3 ] [ 4 ] [ 5 ]} ) です。

その後、オリジナルのTUFモデル、TUF/UAパラダイムのシステムモデル、そしてスケジューリング技術とアルゴリズムに関する数多くのバリエーションが学術文献で研究され（例：^{[ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ]）}、民間分野で応用されてきた。

後者の例としては、サイバーフィジカルシステム^{[ 11 ]}、AI ^{[ 12 ]} 、マルチロボットシステム^{[ 13 ]} 、ドローンスケジューリング^{[ 14} ]、自律型ロボット^{[ 15 ]} 、インテリジェントな車両からクラウドへのデータ転送^{[ 16 ]} 、産業プロセス制御^{[ 17 ]} 、トランザクションシステム[18 ^] 、高性能コンピューティング[19]、^{クラウドシステム[} 20]、^{異種クラスタ[} 21 ^{]、サービス}指向コンピューティング[22]、^{ネットワーキング[ 23 ]、および}実機^{[ 24 ]}と仮想機^{[ 25 ]}のメモリ管理などが挙げられる^{。製鉄所の例は、}クラークの博士論文の序論で簡単に説明されている^{[ 26 ] 。}

TUF とその有用性の解釈 (意味論)、尺度、値は、ドメイン固有の主題知識から導き出されます。^{[ 27 ] [ 5 ]}歴史的によく見られる有用性の解釈は、行動の相対的な重要性です。^{[ b ]}システム モデルに対する強い制約の下で静的な有用性値を事前に割り当てるためのフレームワークが考案されましたが、^{[ 8 ]}その後の (以前の TUF/UA の研究開発では、より一般的なフレームワークを作成しようとするよりも、アプリケーション固有性を活用することに依存する方が好ましいとされてきました。しかし、そのようなフレームワークとツールは、依然として重要な研究テーマです。

従来の慣例では、TUFは線形関数を含め、凹関数である。いくつかのTUFの例を図で示す。

研究文献の TUF/UA 論文は、例外はいくつかありますが、例えば^{[ 28 ] [ 6 ] [ 29 ] [ 30 ] [ 8 ] [ 10 ]は、線形または区分線形[ 31 ]} (従来の期限ベースを含む) TUFのみを対象としています。これは、指定とスケジュールが容易であるためです。多くの場合、TUF は単調減少のみです。

定数関数は、行動の完了時間とは無関係な行動の効用を表します。例えば、行動の相対的な重要度が一定である場合などです。これにより、時間依存の行動と時間非依存の行動の両方を整合性をもってスケジュールすることが可能になります。

TUFにはグローバル臨界時間があり、この時間を超えると効用は増加しません。TUFが一度も減少しない場合、そのグローバル臨界時間は効用が最大に達する最初の時間です。定数TUFには、スケジューリングの目的で任意の臨界時間があります。たとえば、アクションのリリース時間やTUFの終了時間などです。グローバル臨界時間の後にはローカル臨界時間が続く場合があります^{[ 2 ]。}たとえば、滑らかな下降曲線を近似するために、一連の下降ステップを持つTUFを考えてみましょう。^{[ c ]}

TUFの効用値は通常、整数または有理数である。

TUFユーティリティには負の値が含まれる場合があります。（範囲に負の値が含まれるTUFは、必ずしもスケジューリング対象から除外されたり、実行中に中止されたりするわけではありません。その判断はスケジューリングアルゴリズムに依存します。）

TUF として表される従来の期限時間 ( d ) は、単位ペナルティを持つ下降ステップ TUF ^{[ d ]}という特殊なケースです (つまり、臨界時間前は効用値が1 、臨界時間後は0になります)。

より一般的に言えば、TUFは下降（および上昇）ステップ関数が、臨界前および臨界後の任意の時間効用を持つことを可能にする。

TUF として表現される遅延^{[ 32 ]}は、非ゼロ効用が線形関数C - dとなる特殊なケースです。ここで、Cはアクションの完了時間（現在、予想、または想定）です。^{[ e ]}より一般的には、TUF は非ゼロの早期完了と遅延が非線形であることを許容します。たとえば、脅威を検出する場合など、遅延が増加すると効用が非線形に減少する可能性があります。

このように、TUFはリアルタイムコンピューティングにおける従来のアクション完了時間制約の豊富な一般化を提供する。

あるいは、TUF/UAパラダイムは、適時性そのものを目的とするのではなく、グローバルなクリティカルタイムに対する適時性を、ユーティリティ蓄積の目的、すなわちアプリケーションレベルのサービス品質（QoS）を達成するための手段として利用するために使用できる。

TUF（その形状と値）は、アプリケーションまたはその運用環境によって動的に適応される可能性があり、^{[ 2 ]}現在待機中または実行中のアクションとは独立して適応されます。^{[ f ]}

これらの適応は通常、離散的なイベントで発生します。たとえば、弾道ミサイルの飛行段階などのアプリケーションモードの変更時です。^{[ 5 ]}

あるいは、これらの適応は、動作期間と TUF が、それらの動作がリリースされるか動作を開始するかのアプリケーション固有の関数である動作のように、継続的に発生する可能性があります。動作期間は増加または減少するか、あるいはその両方であり、単調ではない可能性があります。この継続的なケースは、時間依存スケジューリングと呼ばれます。^{[ 33 ] [ 34 ]}時間依存スケジューリングは、レーダー追跡システムなどの特定のリアルタイム軍事アプリケーション向けに導入されました（ただし、これに限定されません）。^{[ 35 ] [ 36 ] [ g ]}

システム内の複数のアクションは、プロセッサ、ネットワーク、外部アプリケーション デバイス (センサー、アクチュエータなど) などの物理的な共有リソース、および同期装置、データなどの論理的な共有リソースへのアクセスを順次排他的に競合^{する可能性}があります。

TUF/UAパラダイムは、スケジューリングイベント（例えば、アクションの到着や完了などの時間や状態）でスケジュールを作成（または更新）するアプリケーション固有のアルゴリズム技術を使用して、この競合の各インスタンスを解決します。インスタンスの競合するアクションは、スケジュールの先頭から順番にリソースアクセス用にディスパッチされます。したがって、アクションUAシーケンスは貪欲ではありません。^{[ i ]}

このアルゴリズム的手法は、1つ以上のアプリケーション固有の目標（すなわち、最適性基準）に基づいてスケジュールを作成する。

TUF（タスク実行頻度）を持つアクションのスケジューリングにおける主な目的は、効用蓄積（UA）を最大化することです。蓄積された効用は、スケジュール内の完了したアクションの効用をアプリケーション固有の多項式で合計したものです。アクションに1つ以上の確率的パラメータ（例えば、操作時間）がある場合、蓄積された効用も確率的になります（つまり、期待される多項式の合計となります）。

効用と累積効用は一般的だが、その解釈（意味論）と尺度は用途によって異なる。^{[ 27 ]}

アクションの実行時間は、システム構成時に固定され、既知である場合がある。より一般的には、固定されている場合もあれば、確率的である場合もあるが、実行時間（確実性または予測値）は、実行が完了または解除されるまで不明である。

操作の所要時間は、アクションの操作開始時間のアプリケーション固有の関数である場合があり、増加または減少、あるいはその両方になる可能性があり、単調ではない可能性があります。このケースは時間依存スケジューリングと呼ばれます。^{[ 33 ] [ 34 ] [ 35 ] [ 36 ]}

• 現実世界のためのリアルタイム。
• 2006年～2009年、システムソフトウェア研究グループ、ビノイ・ラビンドラン、電気・コンピュータ工学科、バージニア工科大学。
• Michael L. Pindo著、『スケジューリング：理論、アルゴリズム、およびシステム』第5版、2015年。
• スタニスワフ・ガヴィエノヴィッチ著、『時間依存スケジューリングのモデルとアルゴリズム』第2版、電子書籍ISBN 978-3-662-59362-2Springer、2020年。
• クリス・N・ポッツ、ヴィタリー・A・ストルセヴィッチ著『スケジューリングの50年：マイルストーンの概観』（2009年）
• スケジューリングジャーナル。
• スケジューリングに関する学際的国際会議。
• 動的スケジューリング問題に関する国際ワークショップ。