ピンホイールスケジューリング

数学およびコンピュータ科学において、ピンホイールスケジューリング問題は、単位長さの繰り返しタスクと、繰り返し間の時間に関する厳しい制約を伴うリアルタイムスケジューリングの問題である。

ピンホイールスケジューリング問題に解が存在する場合、その解はスケジュールが周期的に繰り返されるものである。この繰り返しパターンは、ピンホイール暗号機の歯車上のピンがセットされたり解除されたりする繰り返しパターンに似ており、その名前の由来となっている。^{[ 1 ]}各タスクに必要な時間の合計が全体の時間の 5/6 未満であれば、必ず解が存在するが、タスクが全体の時間の 5/6 をわずかに超える時間を使用するピンホイールスケジューリング問題の中には、解が存在しないものもある。

ピンホイールスケジューリング問題の特定の定式化はNP困難である。

ピンホイールスケジューリングへの入力はタスクのリストで構成され、各タスクはインスタンス化ごとに単位時間かかると想定されます。各タスクには、最大繰り返し時間（タスクのインスタンス化の開始から次のインスタンス化までの最大時間）という正の整数値が関連付けられています。任意の時点で実行できるタスクは1つだけです。^{[ 1 ]}

望ましい出力は、各時間単位で実行するタスクを指定する無限シーケンスです。各入力タスクはシーケンス内に無限回出現し、タスクの連続する2つのインスタンス間の最大の間隔は、タスクの繰り返し時間以下である必要があります。^{[ 1 ]}

例えば、無限に繰り返されるシーケンスABACABACABAC ... は、繰り返し時間がそれぞれ少なくとも 2、4、4 である 3 つのタスク A、B、C の有効なピンホイール スケジュールになります。

スケジュールするタスクに番号を付ける場合${\displaystyle 1}$に${\displaystyle n}$、 させて$t_i$タスクの繰り返し時間を表す${\displaystyle i}$有効なスケジュールでは、タスク${\displaystyle i}$使用しなければならない$1/t_{i}}$総時間の割合、つまり、そのタスクを指定された繰り返し時間に正確に繰り返すスケジュールで使用される量。ピンホイールスケジューリング問題の密度は、これらの割合の合計として定義されます。$\displaystyle \textstyle \sum 1/t_{i}}$解が存在するためには、各タスクに費やされる時間の合計が利用可能な総時間を超えてはならないので、密度は最大で${\displaystyle 1}$[ ^{2 ]​}

この密度条件は、すべての繰り返し時間が互いに倍数である特殊な場合にもスケジュールが存在するための十分条件となります。たとえば、すべての繰り返し時間が2のべき乗である場合、これは真となります。この場合、互いに素な被覆システムを使用して問題を解決できます。^{[ 1 ]}密度が最大で${\displaystyle 1}$繰り返し時間がちょうど 2 つある場合にも十分である。^{[ 2 ]}しかし、密度が最大 1 であることは、他のいくつかのケースでは十分ではない。特に、繰り返し時間が 3 つのアイテムの場合、スケジュールは存在しない。${\displaystyle t_{1}=2}$、${\displaystyle t_{2}=3}$、 そして$t3$どんなに大きくても$t3$おそらく、このシステムの密度はわずかですが${\displaystyle 5/6+1/t_{3}}$[ ^{3 ]​}

1993年に、ピンホイールスケジューリングの密度が最大で${\displaystyle 5/6}$解決策は存在する。^{[ 3 ]}これは2024年に証明された。^{[ 4 ]}

解が存在する場合、それは周期的であると仮定でき、その周期は繰り返し回数の積に最大で等しい。しかし、指数関数以下の長さの繰り返しスケジュールを見つけることが常に可能であるとは限らない。^{[ 2 ]}

各繰り返し時間ごとに、その繰り返し時間を持つオブジェクトの数を指定するコンパクトな入力表現を用いると、ピンホイールスケジューリングはNP困難である。^{[ 2 ]}

一般的な入力に対するピンホイールスケジューリング問題はNP困難であるにもかかわらず、一部のタイプの入力は効率的にスケジューリングできます。その例として、入力が（ソート順にリストされている場合）各繰り返し時間が次の繰り返し時間を均等に割り切り、密度が最大で1である場合が挙げられます。この場合、タスクをソート順にスケジュールし、各タスクをその繰り返し時間とまったく同じタイミングで繰り返すようにスケジュールする貪欲アルゴリズムによって問題を解決できます。このアルゴリズムの各ステップで、既に割り当てられているタイムスロットは、最も最近スケジュールされたタスクの繰り返し時間と等しい周期を持つ繰り返しシーケンスを形成します。このパターンにより、各後続タスクを貪欲にスケジュールし、同じ不変条件を維持することができます。^{[ 1 ]}

同じ考え方は、密度が最大で 1/2 の任意のインスタンスにも適用できます。各繰り返し時間を、それ以下の 2 のべき乗に切り捨てることで実現できます。この丸め処理により密度は最大で 2 倍になり、最大でも 1 に保たれます。丸め後、すべての密度は互いに倍数になるため、貪欲アルゴリズムが機能します。結果として得られるスケジュールでは、各タスクが丸められた繰り返し時間で繰り返されます。これらの丸められた時間は入力時間を超えないため、スケジュールは有効です。^{[ 1 ]} 2 のべき乗に丸める代わりに、次の形式の数などの他の倍数のシーケンスに丸めることで、より大きな密度の閾値を実現できます。${\displaystyle x\cdot 2^{i}}$係数を慎重に選択するために${\displaystyle x}$[ ^{3 ]}または、2つの異なる等比数列に丸め、2つの異なる繰り返し時間を持つタスク^は密度1までスケジュールできるという考え方を一般化することによって。^{[ 3 ] [ 5 ]}

ピンホイールスケジューリングに関する最初の研究では、単一の基地局が複数の衛星またはリモートセンサーと、それぞれ異なる通信要件で一度に1つずつ通信する必要があるアプリケーション向けに提案されました。このアプリケーションでは、各衛星がピンホイールスケジューリング問題のタスクとなり、十分な帯域幅を確保するために繰り返し時間が選択されます。結果として得られるスケジュールは、各衛星が基地局と通信するためのタイムスロットを割り当てるために使用されます。^{[ 1 ]}

ピンホイールスケジューリングのその他の応用例としては、オブジェクトの集合に対するメンテナンスセッションのスケジューリング（自動車のオイル交換など）、ラインプリンタの印刷チェーン上の繰り返しシンボルの配置[ 3 ^{]、マルチ}メディアデータのコンピュータ処理^{[ 6 ]}、リアルタイム無線コンピュータネットワークにおける競合解決^{[ 7 ]などがある。}

• ピンホイール・スケジューリング（1989年）、ダグラス・B・ウェスト、イリノイ大学