訂購併發任務以儘量減少等待時間

Question

在一個有多個併發任務操作數據的系統中，我想要排定這些任務，使得等待時間最短。 系統中的每個任務都使用一組特定的資源，任務按特定順序發出（這個順序就是我想要計算的），任務只有在能夠鎖定所有需要的資源時纔會啓動。任務按順序發出，所以第三個任務在第二個任務獲得所有鎖之前不會啓動，依此類推。

Task 1, Resources [A, B] 
Task 2, Resources [B, C] 
Task 3, Resources [C, D] 
Task 4, Resources [E] 

Best Solution 
Task 1, [A, B] 
Task 3, [C, D] //No waiting is possibly required 
Task 4, [E] //Put this before task 3, to maximise the distance between uses of the same resource (minimise chances of lock contention) 
Task 2, [B, C] //Some waiting *might* be required here 

什麼算法可以用來計算最佳排序，以便在使用的資源之間存在最大差距，然後再次使用？

Nb。這是語言不可知的，但在C＃中的實現的獎勵點數爲

Answer 1

我認爲，如果我有一個盒子解決了你的問題的任意實例，我可以給它僞裝的圖着色問題（http://en.wikipedia.org/wiki/Graph_coloring），並讓它解決它們。我會將每個鏈接轉換爲鏈接兩側的節點共享的資源。然後同一時間安排的所有節點的顏色可以相同。所以如果你的問題很簡單，那麼Graph Coloring很容易，但Graph Coloring是NP-complete的，所以你幾乎是塞滿了。

像寄存器分配等OTOH問題被簡化爲圖着色並在實踐中大致解決，因此用於圖着色的一種方案也可能適用於您。見例如http://en.wikipedia.org/wiki/Register_allocation。

Answer 2

除非您有明確的層次結構，否則將難以通過編程實施。例如，您通常必須持有資源才能獲得下一個資源。 IOW得到「B」你必須先拿着「A」。要獲得「C」，您必須同時持有「A」和「B」等。如果情況並非如此，那麼我認爲你所能做的最好的是編寫一個通用例程，它總是以相同的順序請求你的資源，然後是B，然後是C等等，並通過這個例程路由你所有的任務。我認爲理想情況下，您將在排隊任務之前分配資源。

如果資源完全相同，則可以使用計數爲5的信號量。例如，一個數據庫連接池。這似乎不是你的情況，但。

Answer 3

編輯：給出的目標函數是非線性的，正如Moron在commmets中指出的那樣。因此，這個答案可以使用而不是。

一種可能的方法是使用線性規劃來解決它。這是我的想法。引入一個決策變量T_i_j，如果我們在時間j開始任務i（我將計算從0到3的任務），那麼它將被設置爲1。此外，如果他們需要相同的資源，我們想「懲罰」彼此靠近的調度任務。在這個例子給我們希望基於m和n，3之間的差異來懲罰T0_m和T1_n然後，我們可以按照如下

Minimize: 
    3 * T0_0 * T1_1 + 2 * T0_0 * T1_2 + 1 * T0_0 * T1_3 
+ 3 * T0_1 * T1_2 + 2 * T0_1 * T1_3 
+ 3 * T0_2 * T1_3 

+ 3 * T1_0 * T2_1 + 2 * T1_0 * T2_2 + 1 * T1_0 * T2_3 
+ 3 * T1_1 * T2_2 + 2 * T1_1 * T2_3 
+ 3 * T1_2 * T2_3 

Subject to 
// We start a task exactly once. 
T0_0 + T0_1 + T0_2 + T0_3 = 1 
T1_0 + T1_1 + T1_2 + T1_3 = 1 
T2_0 + T2_1 + T2_2 + T2_3 = 1 
T3_0 + T3_1 + T3_2 + T3_3 = 1 

// We can only start a single task at a given time. 
T0_0 + T1_0 + T2_0 + T3_0 = 1 
T0_1 + T1_1 + T2_1 + T3_1 = 1 
T0_2 + T1_2 + T2_2 + T3_2 = 1 
T0_3 + T1_3 + T2_3 + T3_3 = 1 

模型的問題然後我們可以使用一個integer programming solver尋找到啓動的最佳組合作業英寸

上述模型與此產生的（相當可怕的，但應該給你的想法）代碼

class Program 
{ 
    private static string[][] s_tasks = new string[][] 
    { 
     new string[] { "A", "B"}, 
     new string[] { "B", "C"}, 
     new string[] { "C", "D"}, 
     new string[] { "E" } 
    }; 

    static void Main(string[] args) 
    { 
     string filePath = Path.Combine(Environment.GetEnvironmentVariable("USERPROFILE"), @"Desktop\lin_prog.txt"); 
     using (TextWriter writer = new StreamWriter(filePath, false)) 
     { 
      Console.SetOut(writer); 
      Console.WriteLine("Given tasks"); 
      PrintTasks(); 
      Console.WriteLine(); 

      Console.WriteLine("Minimize:"); 
      PrintObjectiveFunction(); 
      Console.WriteLine(); 

      Console.WriteLine("Subject to"); 
      PrintConstraints(); 
     } 
    } 

    static void PrintTasks() 
    { 
     for (int taskCounter = 0; taskCounter < s_tasks.Length; taskCounter++) 
     { 
      Console.WriteLine("Task {0}: [ {1} ]", taskCounter, String.Join(", ", s_tasks[taskCounter])); 
     } 
    } 

    static void PrintConstraints() 
    { 
     Console.WriteLine("// We start a task exactly once."); 
     for (int taskCounter = 0; taskCounter < s_tasks.Length; taskCounter++) 
     for (int timeCounter = 0; timeCounter < s_tasks.Length; timeCounter++) 
     { 
      Console.Write("T{0}_{1}", taskCounter, timeCounter); 
      if (timeCounter != s_tasks.Length - 1) 
      { 
       Console.Write(" + "); 
      } 
      else 
      { 
       Console.WriteLine(" = 1"); 
      } 
     } 

     Console.WriteLine(); 
     Console.WriteLine("// We can only start a single task at a given time."); 
     for (int timeCounter = 0; timeCounter < s_tasks.Length; timeCounter++) 
     for (int taskCounter = 0; taskCounter < s_tasks.Length; taskCounter++) 
     { 
      Console.Write("T{0}_{1}", taskCounter, timeCounter); 
      if (taskCounter != s_tasks.Length - 1) 
      { 
       Console.Write(" + "); 
      } 
      else 
      { 
       Console.WriteLine(" = 1"); 
      } 
     } 

    } 

    static void PrintObjectiveFunction() 
    { 
     StringBuilder objective = new StringBuilder(); 
     for (int currentTaskCounter = 0; currentTaskCounter < s_tasks.Length; currentTaskCounter++) 
     { 
      string[] currentTask = s_tasks[currentTaskCounter]; 
      for (int otherTaskCounter = currentTaskCounter + 1; otherTaskCounter < s_tasks.Length; otherTaskCounter++) 
      { 
       string[] otherTask = s_tasks[otherTaskCounter]; 
       if (ShouldPunish(currentTask, otherTask)) 
       { 
        int maxPunishment = s_tasks.Length; 
        for (int currentTimeCounter = 0; currentTimeCounter < s_tasks.Length; currentTimeCounter++) 
        { 
         string currentTaskDecisionVar = String.Format("T{0}_{1}", currentTaskCounter, currentTimeCounter); 
         for (int otherTimeCounter = currentTimeCounter + 1; otherTimeCounter < s_tasks.Length; otherTimeCounter++) 
         { 
          string otherTaskDecisionVar = String.Format("T{0}_{1}", otherTaskCounter, otherTimeCounter); 
          // Punish tasks more in objective function if they are close in time when launched. 
          int punishment = maxPunishment - (otherTimeCounter - currentTimeCounter); 
          if (0 != objective.Length) 
          { 
           objective.Append(" + "); 
          } 

          objective.AppendFormat 
          (
           "{0} * {1} * {2}", 
           punishment, currentTaskDecisionVar, otherTaskDecisionVar 
          ); 
         } 
         objective.AppendLine(); 
        } 
       } 
      } 
     } 

     // Nasty hack to align things. 
     Console.Write(" " + objective.ToString()); 
    } 

    static bool ShouldPunish(string[] taskOne, string[] taskTwo) 
    { 
     bool shouldPunish = false; 
     foreach (string task in taskOne) 
     { 
      // We punish tasks iff. they need some of the same resources. 
      if(taskTwo.Contains(task)) 
      { 
       shouldPunish = true; 
       break; 
      } 
     } 

     return shouldPunish; 
    } 
} 

幾件事情要注意

• 上面的代碼運行在類似O（n^5）的地方，其中n是任務的數量。這只是爲了生成模型;整數規劃是NP完全的。
• 我不是一個或專家。我只是嘗試了一下。
• 上面概述的解決方案不使用問題可能包含的固有約束。我很容易想象一個專門的作業調度算法會表現得好多了（儘管我仍然認爲這個問題是NP完全的）
• 如果我說得對，事實上這個問題是NP完全的，那麼你很可能使用廉價的啓發式技術會更好，並且可以快速啓動任務（除非您可以預先計算解決方案並多次使用）。