3

たとえば、5days *(8hourWorkday-2hoursForUnexpectedWork)=週に30時間使用する場合、その30時間を埋めるためにプログラムでタスクをスケジュールするにはどうすればよいですか?

たとえば、5つのタスクがあり、それぞれに次の時間がかかると見積もっています。

#1:  2h
#2:  4h
#3:  6h
#4:  8h
#5: 10h

どのように私はそれを言うように分類しますか:

M: #1 @ 2h + #2 @ 4h
T: #3 @ 6h
W: #4 @ 6h
H: #4 @ 2h + #5 @ 4h
F: #5 @ 6h

言い換えれば、「反復合計コンテナオーバーフロー」をどのように説明するのでしょうか。

最終的には、週をオーバーフローするタスクも考慮する必要があります。たとえば、前の例でタスクがあった場合#6: 40h(それ自体が週より10時間多く、週の合計が40時間余分になり、流出する必要があります)。過去2週間に)。

編集:

2番目のより複雑な例。ここでも5つのタスクがあり、今回は(オプションの)曜日の要件があります。

#1:  2h, W[0][M]
#2:  4h, W[0][T]
#3:  6h, W[0][M]
#4:  8h, W[0][F]
#5: 40h, W[0][F]

これをどのように分類しますか?

W[-1][M]: #5 @ 6h
W[-1][T]: #5 @ 6h
W[-1][W]: #5 @ 6h
W[-1][H]: #5 @ 6h
W[-1][F]: #3 @ 2h + #5 @ 4h
W[ 0][M]: #1 @ 2h + #3 @ 4h
W[ 0][T]: #2 @ 4h + #5 @ 2h
W[ 0][W]: #5 @ 6h
W[ 0][H]: #4 @ 2h + #5 @ 4h
W[ 0][F]: #4 @ 6h

イラスト#1

最良のシナリオは、実際には、ここに示すように、#3が#1を1日押し戻すことです。 イラスト#2

さらなる解明:

  • 指定された曜日(MTWHF)ごとに、最大6時間の時間を入力します。
  • オーバーフローがある場合は、前日にこぼしてください。
  • 理想的には、この流出はナップザックまたは同様に最適化された方法で発生するため、6時間は完全な/中断されていないタスクで可能な限り完全に満たされます。
  • 同様に、こぼれた日については、こぼれたものを調整して、タスク全体が中断されないようにする必要があります。
4

2 に答える 2

2

何かが欠けていない限り、これは解決済みの問題のようです。タスクが動的に割り当てられる場合 (実際の環境ではありそうですが)、使用率が管理可能であれば、最早締切優先スケジュールですべての締切を満たすことができます。ジョブは新しいジョブが入ったときにのみプリエンプトされるため、コンテキスト切り替えのオーバーヘッドが低くなり、作業の連続性がかなり向上します。これは単純なヒューリスティックであり、文献で注目を集めているため、方程式から多くの当て推量が取り除かれています。

編集:例。

#1:  2h, W[0][M]
#2:  4h, W[0][T]
#3:  6h, W[0][M]
#4:  8h, W[0][F]
#5: 40h, W[0][F]

EDF order: #1, #3, #2, #4, #5.

Schedule: 113333332222444444445555555555555555555555555555555555555555

In days: 113333 332222 444444 445555 555555 555555 555555 555555 555555 555555

このアプリオリなスケジュールを採用し、EDF スケジューリングの結果を後処理することにより、連続性の点でより良い結果が得られることに注意してください。1 日の開始時と数値が変わるたびにコンテキスト スイッチのオーバーヘッドがあると仮定すると、このスケジュールでは 13 回のコンテキスト スイッチが発生し、そのうち 10 回だけが必須です。スケジュール #3、#1、#2、#4、#5 では、12 回のコンテキスト スイッチが発生します。質問はもともと、コンテキストの切り替えを最小限に抑えたいと思っていたことを知っています。ただし、その点での最適なスケジューリング アルゴリズムは、義務的なコンテキスト スイッチ (1 日の開始時に発生する) に本物のコンテキスト スイッチを隠すことによって、EDF よりもうまく機能します。EDF には、締め切りに間に合う可能性がある場合、常に締め切りに間に合うことが保証されるという利点があります。それはトレードオフですが、うなずきはEDFに行くと思います。

また、特に割り当てられたタスクに規則性がある場合は、静的に決定されるスケジュールに適したレートの単調なスケジューリング(締め切りを期間とする) を検討してください。

于 2013-01-30T20:42:09.760 に答える
1

ナップザック問題のようですね。wiki はこの問題に対するいくつかの解決策を提供していますが、ほとんどの場合、これは動的プログラミングで解決されます。

于 2013-01-24T23:26:55.863 に答える