n 個のジョブと m 個のマシンがあります。各ジョブ i にはリリース時刻 r[i] があります。マシン j でのジョブ i の処理には p[i][j] 時間がかかります。1 つのジョブ k に対して |{p[i][j] | 私 == k}| <= c、ここで c << m。ジョブ i の遅延を f[i] - r[i] と定義します。ここで、f[i] はジョブ i が終了する時間です。システムはプリエンプティブではありません。つまり、あるマシンで 1 つのジョブが開始されると、終了する前に中断することはできません。目標は、すべてのジョブの遅延の合計を最小限に抑えるスケジューリング アルゴリズムを提供することです。何か案が？
1 に答える
1
これが3 分割問題からの縮小です。
S = {x 1 , …, x 3m } を、すべての i について B/4 < x i < B/2 となるような 3 分割のインスタンスとします。ここで、B = ∑x i /m は目標の合計です。
同一の機械が m台あるとします。時間 0 で、長さ x 1、…、x 3mの 3m ジョブをリリースします。B、B + 1、…、B + 4mB - 1 のたびに、長さ 1 の m 個のジョブを解放し、合計 4m 2個のB ジョブを解放します。
3 パーティションのインスタンスには、初期ジョブのメイクスパンが B 以下である場合にのみ解があります。解がある場合、初期ジョブのオブジェクトへの寄与は最大 3mB です。他のジョブの貢献度は 4m 2 Bです。
makespan が B よりも長い場合、4mB ジョブのチェーンは少なくとも 1 ユニット遅延し、目標に 4mB 貢献します。したがって、目標は、3 分割問題が解ける場合は最大 3mB + 4m 2 B であり、3 分割問題が解けない場合は少なくとも 4mB + 4m 2 B です。
于 2011-12-06T05:11:42.830 に答える