작업 매트릭스를 어떻게 그리나요?

Question

할당 문제가있는 작업이 있습니다. 우리는 하나의 슈퍼 컴퓨터와 n 컴퓨터를 보유하고 있으며 이것들에 대한 작업을 n 실행하고 싶습니다. 수퍼 컴퓨터는 언제든지 하나의 작업 만 계산할 수 있으며 슈퍼 컴퓨터는 별도의 컴퓨터를 가지고 있습니다. 컴퓨터는 수퍼 컴퓨터를 거쳐 작업을 얻습니다.

실행에 가장 적합한 시간을 계산하는 알고리즘을 작성해야합니다. 여기

가 입력된다 :

5 
9 6 
6 2 
2 6 
10 1 
5 6 

첫번째 줄은 작업 번호 다음 라인에서는, 첫 번째 숫자는 슈퍼에서 태스크를 실행하는 데 걸리는 시간은,이고, 두번째는 컴퓨터 인 .

매트릭스가 어떻게 표시되어야하는지 지정하는 데 문제가 있습니다. 나는 같은 컴퓨터에서 어떻게 할 수 있는지 알고 있지만 여기에서는 슈퍼 컴퓨터에 대해서도 설명해야한다.

누구나이 작업을위한 매트릭스를 그릴 수 있습니까? , tesing 서버 답변에

33이고, I는 2 가지 방법을 시도하지만 난 (S) upercomputer 및 (C) 같습위한 최소한의 시간을 찾고, 이제 32

| T1 | T2 | T3 | T4 | T5 |minimal 
    ________________________________ 
S | 9 | 6 | 2 | 10 | 5 |2 
_________________________________ 
C | 6 | 2 | 6 | 1 | 6 |1 

(34)가 2이고 1을 빼고 모든 행에서 뺍니다.

 | T1 | T2 | T3 | T4 | T5 | 
     _________________________ 
    S | 7 | 4 | 0 | 8 | 3 | 
    ____________________________ 
    C | 5 | 1 | 5 | 0 | 5 | 
__________________________________ 
minimal| 5 | 1 | 0 | 0 | 3 

다음으로, 나는 어떤 작업이라도 최소한의 시간을 찾고 빼기. 결과는 첫 번째 빼기 2 + 1, 두 번째 빼기 5 + 1 + 3,이 2 + 3 + 5 + 8 + 2 :

 | T1 | T2 | T3 | T4 | T5 | 
     _________________________ 
    S | 2 | 3 | 0 | 8 | 0 | 
    ____________________________ 
    C | 0 | 0 | 5 | 0 | 2 | 

하지만 전혀이 있습니다 나도 몰라 감각.

Answer 1

이것은 할당 문제가 아닙니다. 그것은 스케줄링 문제가 더 있습니다. 당신이 얻을 수있는 대답은 다음과 같은 논리 때문입니다.

모든 작업에서 사용할 수있는 슈퍼 컴퓨터가 하나뿐이므로 가능한 한 무료로 유지해야합니다.

따라서 수퍼 컴퓨터에서 실행 시간이 오름차순으로 작업을 예약합니다.

2 -> 5 -> 6 -> 9 -> 10 

슈퍼 컴퓨터에서 각각의 작업을 완료 한 후에는 항상 개별 컴퓨터에서 나머지 작업을 실행해야합니다. 그러나이 시리즈 후에는 컴퓨터에서 작업 할 때 마지막 작업 만 남아 있어야합니다 (1 시간 단위). 나는 가능한 한 무료 슈퍼 컴퓨터를 유지하는 것입니다 앞서 말했듯이

하나의 논리 :

Hence total time consumed = 2 + 5 + 6 + 9 + 10 + 1 = 33 

어떻게 이러한 문제를 해결합니다. 그러나 경우에이 논리를 나누기 좋아 다음과

5 
9 6 
6 2 
2 6 
10 **100** 
5 6 

을 이제 보는 바와 같이, 제 4 과제는 개별 컴퓨터에 시간의 100 개 단위를합니다. 따라서 실행의 총 시간이 110 이상이되도록 우선 순위를 지정하는 것이 좋습니다.

브 루트 포스 조합은 N! 가능한 일정 순열.

그러나 Job-shop 일정 계획에 관한 인터넷에서 수 많은 도서가 있습니다. 당신은 그것을 위해 구글과 당신에게 관련이있는 뭔가를 찾을 수 있습니다.