N 개의 동일한 프로세서에서의 작업 스케줄링을위한 정확한 알고리즘은 무엇입니까?

Question

N 개의 동일한 프로세서에서 작업 일정에 대한 최상의 솔루션을 찾는 정확한 알고리즘을 찾고 있습니다.

이 알고리즘의 시간은 중요하지 않습니다. 가장 중요한 해결 방법은 마지막 작업이 완료 될 때 모든 프로세서의 시간입니다. P || Cmax는

을 누군가가 내가 도움을 grathefull 될 것이다 (특히 자바) 알고리즘 또는 의사가있는 경우 다음과 같이이 알고리즘을 설명하는 이론 방정식에서

이다.

난 내 자신의 정확한 알고리즘으로 쓰기하지만 ID가 permUtil 아래 코드에서 :(작동하지 않습니다 시도

는 순열에 해당하는 클래스

메소드의 인수입니다 :..
- 작업 -> 모든 작업 여기서 인덱스 ID는 작업 및 값 시간
- op -> 할당 프로세서 (작업을 할당하는 프로세서)
//이 프로세서의 인덱스는 ID이고 값은 작업 스케줄 시간이되는 글로벌 어레이 op 프로세서입니다.

public void schedule(Byte[] tasks, int op) 
{ 
    PermUtil<Byte> permA = new PermUtil<Byte>(tasks); 
    Byte[] a; 
    // permutation of all tasks 
    while ((a = permA.next()) != null) 
    { 

     // assign tasks 
     for(int i=1; i< a.length; i++) 
     { 
      // get the b set from i to end 
      Byte[] b = Arrays.copyOfRange(a, i, a.length); 
      // all permutations off b set 
      PermUtil<Byte> permB = new PermUtil<Byte>(b); 
      while ((b = permB.next()) != null) 
      { 
       // task on assign processor 
       proc[op] = sum(Arrays.copyOfRange(a, 0, i)); 
       if (op < proc.length) 
        schedule(b, ++op); 
       else 
       { 
        proc[++op] = sum(b); 
       } 
      } 
     } 
    } 
} 

Answer 1

다음은 가능한 모든 과제를 반복하는 청사진입니다. 실제 구현에서는 long을 BigInteger, 으로 대체하고 배열 초기화를 내부 루프 외부로 옮겨야합니다.

public void processOne(int nProcs, int nTasks, int[] assignment) { 
    /* ... */ 
} 

public void checkAll(int nProcs, int nTasks) { 
    long count = power(nProcs, nTasks); 
    /* Iterate over all the possible assignments */ 
    for (long j = 0; j < count; j++) { 
     int[] assignment = new int[nTasks]; 
     for (int i = 0; i < nTasks; i++) 
      assignment[i] = (int) (j/power(nProcs, i) % nProcs); 
     processOne(nProcs, nTasks, assignment); 
    } 
} 

속임수는 숫자로 인코딩하는 것입니다. 배정은 nTasks 개의 결정을 나타내므로 각 숫자는 nProcs이고 nProcs의 숫자는 nTasks 자라고 생각할 수 있습니다. 이러한 모든 숫자는 유효한 할당에 해당하며 모든 할당에는 이러한 범위의 고유 번호가 있습니다. 기본적으로 모든 정수를 반복하므로 모든 과제를 반복하는 것이 쉽습니다.

당신이해야 할 일은 processOne(int, int, int[]) 함수를 작성하는 것입니다. 이것은 다소 간단해야합니다.