不均一なマシンの異種タスクをスケジュールします

Question

NジョブとMマシンがあります。各ジョブはリリース時間r [i]があります。マシンJでジョブIを処理します。P[i] [j]時間がかかります。 1つのジョブkの場合| {p [i] [j] | i == k} | <= c、ここでc << m。ジョブIの遅延をf [i] -r [i]として定義します。ここで、f [i]はジョブIが終了する時間です。システムは先制的ではありません。つまり、あるマシンで1つのジョブが開始されると、終了する前に中断することはできません。目標は、すべてのジョブの遅延合計を最小限に抑えるスケジューリングアルゴリズムを提供することです。何か案が？

Answer 1

これがからの削減です 3パーティションの問題.

s = {xとします₁, 、 …、 バツ_3m}すべてのiの場合、b/4 <xの場合、3パーティションのインスタンスになります。_私 <b/2、ここでb = ∑x_私/mはターゲット合計です。

mがあるようにします 同一 マシン。時間0に、長さxの3Mジョブをリリースします₁, 、 …、 バツ_3m. 。 b、b + 1、…、b + 4mb -1、b + 4mb -1、長さ1のジョブをリリースするたびに、合計4m²Bジョブ。

3パーティションのインスタンスには、最初のジョブのメイクスパンがBよりも低い場合にのみ解決策があります。解決策がある場合、目的への最初のジョブの貢献は最大3MBです。他のジョブの貢献は4mです²B.

MASKPANがBよりも長い場合、4MBのジョブのチェーンが少なくとも1つのユニットを遅らせ、目的に4MBに寄与します。したがって、目的はせいぜい3MB + 4mです²b 3パーティションの問題が解決可能で、少なくとも4MB + 4mの場合²b 3パーティションの問題が解決できない場合。