대기 작업을 최소화하기 위해 동시 작업을 주문하십시오.

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은 쉽지만 그래프 채색은 NP 완성이므로 채워집니다.

레지스터 할당과 같은 OTOH 문제는 그래프 채색으로 축소되어 거의 실제적으로 해결되므로 그래프 채색에 사용 된 스키마 중 하나가 사용자에게 효과적 일 수 있습니다. 예 : http://en.wikipedia.org/wiki/Register_allocation.

Answer 2

명확한 계층 구조가 없으면 프로그래밍 방식으로 적용하기가 어렵습니다. 예를 들어, 보통 다음 자원을 확보하려면 자원을 보유해야합니다. IOW는 "B"를 얻으려면 먼저 "A"를 잡아야합니다. "C"를 얻으려면 "A"와 "B"를 모두 잡고 있어야합니다. 이것이 사실이 아니라면, 내가 할 수있는 최선의 방법은 항상 같은 순서로 자원을 요청하는 공통 루틴을 작성한 다음 A와 B를 누른 다음 C 등이며이 루틴을 통해 모든 태스크를 라우트하는 것입니다. 이상적으로는 큐에 대기 전에 리소스를 할당하는 것이 가장 이상적이라고 생각합니다.

리소스가 모두 동일한 경우 개수가 5 인 세마포를 사용할 수 있습니다 (예 : DB 연결 풀). 그래도 당신의 경우는 아닌 것 같습니다.

Answer 3

편집 : 주어진 목적 함수는 commonets에서 Moron이 지적한대로 비선형 함수입니다. 따라서이 대답은 이 아니라이 사용됩니다.

가능한 한 가지 방법은 선형 프로그래밍을 사용하여 해결하는 것입니다. 여기 내가 마음에 두었던 것이있다. 시간 j에서 작업 i를 시작하면 1로 설정된 결정 변수 T_i_j를 도입합니다 (0에서 3까지의 작업을 계산할 것임). 또한 동일한 리소스가 필요한 경우 서로 가까이있는 작업을 "처벌"하고 싶습니다. 예에서 주어진 우리는

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를 사용하여 우리는 다음 문제를 모델링 할 수 m과 n, (3)의 차이에 따라 T0_m 및 T1_n을 처벌 할 에서 작업.

이상이 생성 된 모델 몇 가지주의 할

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 완료되면 문제가 해결됩니다. 싸구려 휴리스틱 스를 사용하는 것이 훨씬 낫고 (솔루션을 미리 계산하고 여러 번 사용하지 않는 한) 신속하게 작업을 시작할 수 있습니다.