17

序章

動的な複数のタイムライン キューを実装したいと思います。ここでのコンテキストは、一般的なスケジューリングです。

タイムライン キューとは何ですか?

これはまだ単純です。これはタスクのタイムラインであり、各イベントには開始時刻と終了時刻があります。タスクはジョブとしてグループ化されます。このグループのタスクは、その順序を維持する必要がありますが、全体として時間内に移動できます。たとえば、次のように表すことができます。

 --t1--   ---t2.1-----------t2.2-------
 '    '   '        '                  '
20    30  40       70                120

これをヒープ キューとして実装し、いくつかの制約を追加します。Pythonschedモジュールには、この方向へのいくつかの基本的なアプローチがあります。

複数のタイムライン キューの定義

1 つのキューはリソースを表し、リソースはタスクに必要です。グラフィカルな例:

R1  --t1.1----- --t2.2-----      -----t1.3--    
            /  \                /
R2  --t2.1--     ------t1.2-----


「ダイナミック」を解説

タスクが複数のリソースの 1 つを使用できる場合、興味深いものになります。追加の制約として、同じリソースで実行できる連続するタスクは同じリソースを使用する必要があります。

例: (上から) タスクがまたはでt1.3実行できる場合、キューは次のようになります。R1R2

R1  --t1.1----- --t2.2-----      
            /  \                
R2  --t2.1--     ------t1.2----------t1.3--


機能性（優先順）

  • FirstFreeSlot(duration, start)start : 空き時間がある場所から始まる最初の空き時間スロットを見つけますduration(最後の詳細な説明を参照してください)。
  • 制約(主に、タスクの正しい順序、同じリソースでの連続したタスク) を考慮し、FirstFreeSlot.
  • 特定の時間にジョブを投入し、テールを後方に移動します
  • ジョブを削除する
  • 再計算: 削除後、一部のタスクを以前に実行できるかどうかをテストします。


重要な質問

ポイントは、この情報をどのように表現して機能を効率的に提供できるかということです。実装は私次第です;-)

更新: 考慮すべきさらなる点: 典型的な間隔構造は、「点 X には何があるか?」に焦点を当てています。しかし、この場合、enqueue「期間 D の最初の空きスロットはどこにあるのか?」という質問となります。ははるかに重要です。したがって、セグメント/インターバルツリーまたはこの方向の他の何かは、おそらく正しい選択ではありません.

空き時間枠についてさらに詳しく説明すると、複数のリソースがあり、グループ化されたタスクの制約により、一部のリソースに空き時間枠が存在する可能性があります。簡単な例: t1.1R1 で 40 をt1.2実行してから、R2 で実行します。[0, 40]そのため、次のジョブで埋めることができる R2の空の間隔があります。

更新 2 :別の SO の質問に興味深い提案があります。誰かがそれを私の問題に移植し、このケースで機能していることを示すことができれば（特に複数のリソースに詳しく説明されている場合）、これはおそらく有効な答えになるでしょう。

4

4 に答える 4

2

まず、最も単純なケースに限定しましょう。FirstFreeSlot（）の高速実装を可能にする適切なデータ構造を見つけます。

空きタイムスロットは2次元空間に存在します。1つの次元は開始時間sで、もう1つの次元は長さdです。FirstFreeSlot（D）は、次のクエリに効果的に答えます。

min s：d> = D

sとdをデカルト空間（d = x、s = y）と考えると、これは垂直線で囲まれたサブプレーンの最低点を見つけることを意味します。おそらく各ノードにいくつかの補助情報（つまり、すべてのリーフの分）を持つ四分木は、このクエリに効率的に答えるのに役立ちます。

リソースの制約に直面したEnqueue（）の場合は、リソースごとに個別のクアッドツリーを維持することを検討してください。クワッドツリーは、次のようなクエリにも答えることができます

min s：s> = S＆d> = D

（開始データを制限するために必要）同様の方法で：長方形（左上で開いている）が切り取られ、その長方形で最小値が検索されます。

Put（）とDelete（）は、クワッドツリーの単純な更新操作です。

Recalculate（）は、 Delete（） + Put（）によって実装できます。不要な操作の時間を節約するために、再計算をトリガーするための十分な（または理想的には十分+必要な）条件を定義します。ここではオブザーバーパターンが役立つ場合がありますが、再スケジュールするタスクをFIFOキューまたは開始時刻でソートされた優先キューに入れることを忘れないでください。（次のタスクに引き継ぐ前に、現在のタスクの再スケジュールを終了する必要があります。）

より一般的な注意点として、ほとんどの種類のスケジューリングの問題、特にリソースの制約がある問題は、少なくともNP完全であることに気付いていると思います。したがって、一般的なケースでは、適切なランタイムのアルゴリズムを期待しないでください。

于 2012-06-29T01:17:18.580 に答える
2 
class Task:
    name=''
    duration=0
    resources=list()

class Job:
    name=''
    tasks=list()

class Assignment:
    task=None
    resource=None
    time=None

class MultipleTimeline:
    assignments=list()
    def enqueue(self,job):
        pass
    def put(self,job):
        pass
    def delete(self,job):
        pass
    def recalculate(self):
        pass

これはあなたが探している方向、つまり Python で書かれたデータ モデルへの第一歩ですか?

アップデート：

これにより、私のより効率的なモデル:

基本的に、すべてのタスクを終了時間順にリンクされたリストに配置します。

class Task:
    name=''
    duration=0    # the amount of work to be done
    resources=0   # bitmap that tells what resources this task uses
# the following variables are only used when the task is scheduled
    next=None     # the next scheduled task by endtime
    resource=None # the resource this task is scheduled
    gap=None      # the amount of time before the next scheduled task starts on this resource

class Job:
    id=0
    tasks=list() # the Task instances of this job in order 

class Resource:
    bitflag=0       # a bit flag which operates bitwisely with Task.resources
    firsttask=None  # the first Task instance that is scheduled on this resource
    gap=None        # the amount of time before the first Task starts

class MultipleTimeline:
    resources=list()
    def FirstFreeSlot():
            pass
    def enqueue(self,job):
        pass
    def put(self,job):
        pass
    def delete(self,job):
        pass
    def recalculate(self):
        pass

による更新のため、ツリーを使用しないことにしましたenqueue。put時間内にタスクを移動するため、put絶対時間を使用しないことにしました。

FirstFreeSlot空きスロットを持つタスクを返すだけでなく、終了時刻を持つ他の実行中のタスクも返します。

enqueue次のように動作します: ここで空きスロットを探しFirstFreeSlot、タスクをスケジュールします。次のタスクに十分なスペースがある場合は、それもスケジュールできます。そうでない場合: 実行中の他のタスクに空き容量があるかどうかを確認します。そうでない場合:FirstFreeSlotこの時間と実行中のタスクのパラメーターを使用して実行します。

改善:putあまり頻繁に使用されずenqueue、ゼロから実行される場合、他の実行中のタスクを含むタスクごとに dict() を含めることで、重複するタスクを追跡できます。次に、リソースごとに list() を保持することも簡単です。これには、スケジュールされたタスクと、このリソースの絶対時間が endtime 順に並べられたものが含まれます。以前よりもタイムギャップが大きいタスクのみが含まれます。これで空きスロットを簡単に見つけることができます。

質問: によってスケジュールされたタスクputは、その時点で実行する必要がありますか? はいの場合: put によってスケジュールされる別のタスクが重複する場合はどうなりますか? すべてのリソースが同じ速度でタスクを実行しますか?

于 2012-06-25T17:36:56.843 に答える
1

これについてしばらく考えた後。このタイムライン キューをモデル化するには、セグメント ツリーの方が適していると思います。ジョブの概念は LIST データ構造のようなものです。

タスクはこのようにモデル化できると思います (PSEUDO CODE)。ジョブ内のタスクの順序は、start_time によって保証できます。

class Task:
    name=''

    _seg_starttime=-1; 
    #this is the earliest time the Task can start in the segment tree, 
    #a lot cases this can be set to -1, which indicates its start after its predecessor,
    #this is determined by its predecessor in the segment tree.
    #if this is not equal -1, then means this task is specified to start at that time
    #whenever the predecessor changed this info need to be taken care of

    _job_starttime=0; 
    #this is the earliest time the Task can start in the job sequence, constrained by job definition

    _duration=0;      
    #this is the time the Task cost to run

    def get_segstarttime():
       if _seg_starttime == -1 :
           return PREDESSOR_NODE.get_segstarttime() + _duration
       return __seg_startime + _duration

    def get_jobstarttime():
       return PREVIOUS_JOB.get_endtime()

    def get_starttime():
       return max( get_segstarttime(), get_jobstarttime() )
  • エンキューは単にタスク ノードをセグメント ツリーに追加するだけです。_seg_startime が -1 に設定されていることに注意して、先行ノードの直後に開始されることを示します。
  • セグメントをツリーに挿入すると、セグメントは start_time と duration で示されます。
  • 削除 ツリー内のセグメントを削除し、必要に応じてその後継を更新します (削除されたノードに _seg_start_time が存在する場合など)
  • get_starttime () を再度呼び出して再計算すると、最も早い開始時刻が直接取得されます。

例（仕事の制約を考慮しない場合）

                  t1.1( _segst = 10, du = 10 )
                      \
                      t2.2( _segst = -1, du = 10 ) meaning the st=10+10=20
                        \
                        t1.3 (_segst = -1, du = 10 ) meaning the st = 20+10 = 30

プットを行う場合:

                    t1.1( _segst = 10, du = 10 )
                        \
                        t2.2( _segst = -1, du = 10 ) meaning the st=20+10=30
                        /  \
t2.3(_segst = 20, du = 10)  t1.3 (_segst = -1, du = 10 ) meaning the st = 30+10 = 30

元のシナリオに t1.1 を削除する場合

                      t2.2( _segst = 20, du = 10 ) 
                        \
                        t1.3 (_segst = -1, du = 10 ) meaning the st = 20+10 = 30

各リソースは、この間隔ツリーの卵の 1 つのインスタンスを使用して表すことができます。

セグメント ツリー (タイムライン) の観点から:

t1.1                      t3.1
  \                        / \
  t2.2                  t2.1  t1.2

仕事の観点から：

t1.1 <- t1.2
t2.1 <- t2.2
t3.1

t2.1 と t2.2 は、次のようにリンク リストを使用して接続されています。派生。

于 2012-06-27T04:38:49.203 に答える
0

最後に、キュー アイテム用の単純なリストと、空のスロットを格納するためのインメモリ SQLite データベースを使用しました。これは、多次元のクエリと更新が SQL で非常に効率的であるためです。フィールドstart、duration、およびindexをテーブルに格納するだけで済みます。

于 2012-11-09T07:03:09.287 に答える