최 우수 흐름 작업 스케줄 링
8767 단어 알고리즘-동적 계획
질문 설명:
n 개의 작업 이 설치 되 어 있 으 며, 모든 작업 i 는 m 개의 임무 로 분해 되 었 습 니 다: Ti1, Ti 2, 94777 °, Tim (1 ≤ i ≤ n, 그러므로 모두 n * m 개의 임무 가 있 습 니 다). 이 임 무 를 m 대 기계 에 배치 하여 가공 해 야 합 니 다.
현재 세 가지 제한 이 있다.
1、 각 작업 i 의 제 j 항 퀘 스 트 Tij (1 ≤ i ≤ n, 1 ≤ j ≤ m) 는 기계 Pj 에 만 배치 하여 가공 할 수 있다.
2、 작업 i 의 제 j 항 퀘 스 트 Tij (1 ≤ i ≤ n, 2 ≤ j ≤ m) 의 시작 가공 시간 은 모두 제 j - 1 항 퀘 스 트 Ti, j - 1 가공 완료 후;
3、 어떤 기계 든 지 언제든지 최대 한 가지 임 무 를 맡 을 수 있다.
최 적 화 된 흐름 작업 스케줄 링: 작업 Tij 를 설정 하여 기계 Pj 에서 가공 하 는 데 필요 한 시간 은 tij 입 니 다.만약 모든 tij (1 ≤ i ≤ n, 1 ≤ j ≤ m) 가 이미 제시 되 었 다 면, 임 무 를 배정 하 는 방법 을 찾 아 이 n 개 작업 을 완성 하 는 가공 시간 을 최소 화해 야 한다.기계 수 (또는 작업 번호) m ≥ 3 일 때 유수 작업 스케줄 문 제 는 NP - hard 문제 임 이 증명 되 었 다.
여기에 n 개의 작업 이 2 개의 기계 (P1, P2) 에 대한 스케줄 링 을 고려한다.현재 문 제 는 n 개의 작업 T 를 정 하고 각 작업 은 두 개의 작업 A, B 로 나 눌 수 있다 는 것 이다.그 중에서 A 임 무 는 P1 에서 처리 하고 B 임 무 는 P2 에서 처리한다.어떻게 이 n 작업 의 가공 시간 을 가장 짧게 합 니까?
문제 해결:
분석:
우선 최 적 화 된 흐름 스케줄 의 성질 을 고려 합 니 다.
1. 확 정 된 최 적 화 된 스케줄 링 의 배열 에서 첫 번 째 작업 을 수행 한 후에 남 은 작업 배열 은 아직도 최 적 화 된 스케줄 링 이다. 즉, 이 문 제 는 최 적 화 된 서브 구조의 성질 을 가진다.
2. 규모 가 n 인 작업 집합의 최 우선 스케줄 을 계산 할 때 이 작업 집합의 하위 집합의 최 우선 스케줄 을 여러 번 사용 해 야 한다. 즉, 이 문제 도 고도 의 중복 성 을 가진다.
So... 동적 기획 으로 이 문 제 를 풀 어 볼 까 합 니 다.
설정 N = {1, 2, 94777 °, n} 은 모든 작업 의 집합 이 고 작업 집합 S 는 N 의 부분 집합 S * 8712 ° N 입 니 다.우리 가 S 중의 첫 번 째 작업 을 가공 하기 시 작 했 을 때 기계 P2 에서 가공 한 다른 작업 은 아직 완성 되 지 않 았 을 수도 있 고 S 중의 작업 을 즉시 가공 할 수 없다.
만약 에 기계 P2 에 대해 t 개 시간 단 위 를 기 다 려 야 S 중의 작업 가공 (t 도 0 일 수 있 고 기다 릴 필요 가 없다) 에 사용 할 수 있다 고 가정 하면 g (S, t) 로 기록 할 수 있다.
현재 작업 i 를 S 의 첫 번 째 가공 작업 으로 선택 한 후, 기계 P2 에서 S - {i} 의 작업 을 가공 하기 전에 필요 한 대기 시간 은 bi + max {t - ai, 0} 입 니 다.이 는 P2 가 가공 S 중의 작업 을 시작 하기 전에 t 개 시간 단위 와 t > ai 를 기 다 려 야 작업 i 가 P1 에서 가공 (필요 시 ai) 을 마 친 후에 t - ai 개 시간 단 위 를 기 다 려 야 P2 에서 가공 할 수 있 기 때문이다.만약 t ≤ ai, 작업 i 가 P1 에서 가공 을 마 친 후 즉시 P2 에서 가공 할 수 있 으 며 대기 시간 은 0 입 니 다.그러므로 P2 는 S - {i} 의 작업 을 가공 하기 전에 필요 한 대기 시간 은 t = bi + max {t - ai, 0} 입 니 다.(bi 는 작업 i 가 P2 에서 가공 하 는 데 소요 되 는 시간).따라서 ai 를 알 고 있 는 g (S, t) 값 을 최소 화 하 는 첫 번 째 작업 으로 가정 하면 얻 을 수 있 습 니 다.
g(S,t)= ai+ g(S-{i},bi+max{t-ai,0}) (1)
이상 의 결론 을 홍보 하고 지금 우 리 는 먼저 작업 i 를 집행 한 다음 에 작업 j 를 집행 하도록 배정 합 니 다. P2 는 t 개 시간 단 위 를 기 다 려 야 S 중의 작업 가공 에 사용 할 수 있 습 니 다.g (S, t)
g(S,t)=ai+g(S-{i}, t’)=ai+aj+g(S-{i,j}, bj+max{t’-aj,0})。 (2)
max {} 연산 에 대하 여 이 성질 이 있 습 니 다: x + max {y1, y2,..., yn} = max {x + y1, x + y2,..., x + yn}.
그래서
bj+max{t’-aj,0}
= bj + max{bi+max{t-ai,0}-aj, 0}
= bj + bi - aj+ max{max{t-ai,0},aj-bi}
= bj + bi - aj + max{t-ai, 0, aj-bi}
= bj+ bi - aj - ai + max{t, ai, ai+aj-bi}。
기 tij = bj + bi - aj - ai + max {t, ai, ai + aj - bi} 이면 g (S, t) = ai + aj + g (S - {i, j}, tij).
전에 저희 스케줄 기억 나 세 요?우 리 는 먼저 작업 i 를 스케줄 링 하고 작업 j 를 스케줄 링 하기 로 약 속 했 습 니 다. 발견 하지 못 했 습 니까? 우 리 는 반나절 을 미 루 었 지만 실질 적 인 결과 가 없 었 습 니 다. 왜냐하면 지금 우 리 는 i 와 j 가 무엇 인지 전혀 모 르 기 때 문 입 니 다. 어떻게 확정 합 니까?
그래서 먼저 i 후 j 가 가장 좋다 고 했 는데 왜?j 와 i 를 맞 추 면 가장 좋 은 것 이 아 닙 니 다. 그 맞 추 면 가장 좋 은 근원 이 아 닙 니 다. 어디 에 있 습 니까?해 보 자.
j 작업 을 먼저 스케줄 링 하고 i 작업 을 스케줄 링 하면 g '(S, t) = ai + aj + g (S - {i, j}, tji) 를 얻 을 수 있 습 니 다.
g (S, t) 와 g '(S, t) 두 식 을 비교 하면 분명히 tij 와 tji 를 비교 하 는 것 이다.
tij= bj+ bi - aj - ai +max{t, ai, ai+aj-bi},
tji= bj+ bi - aj - ai + max{t, aj, ai+aj-bj},
그러므로 tij - tji = max {t, ai, ai + aj - bi} - max {t, aj, ai + aj - bj}.
따라서 우 리 는 max {t, ai, ai + aj - bi} 와 max {t, aj, ai + aj - bj} 의 크기 를 비교 하면 됩 니 다. 즉, tij ≤ tji 는 max {t, ai, ai + aj - bi} ≤ max {t, aj, ai + aj - bj} 입 니 다.
max {t, ai, ai + aj - bi} ≤ max {t, aj, ai + aj - bj}
그 어떠한 t ≥ 0 에 대해 서도 성립 되 며, 당 해 야 한다.
max {ai, ai + aj - bi} ≤ max {aj, ai + aj - bj} 성립
ai + aj + max {- aj, - bi} ≤ ai + aj + max {- ai, - bj} 성립
max {- aj, - bi} ≤ max {- ai, - bj} 이 성립 되 었 을 때
min {aj, bi} ≥ min {ai, bj} 이 성립 되 었 습 니 다.
min {ai, aj, bi, bj} 이 ai 또는 bj 일 때 tij ≤ tji 가 있 습 니 다. 이때 i 를 앞 에 놓 고 j 를 뒤에 놓 는 스케줄 링 시간 이 적 습 니 다.
반면에 min {ai, aj, bi, bj} 이 aj 또는 bi 일 경우 j 는 앞 i 가 뒤에 있 는 스케줄 링 시간 이 비교적 적다.
이 상황 을 일반 으로 보급 하 다.
min {a1, a2, 94777 °, an, b1, b2, 94777 °, bn} = ak 일 때 그 어떠한 i ≠ k 에 대해 서도 min {ai, bk} * 6161619 ° min {ak, bi} 이 성립 되 므 로 이 때 작업 k 를 맨 앞 에 배치 하여 최 적 화 된 스케줄 의 첫 번 째 작업 으로 해 야 합 니 다.
min {a1, a2, 94777 °, an, b1, b2, 94777 °, bn} = bk 일 때 모든 i ≠ k 에 대해 서도 min {ak, bi} * 6161619 ° min {ai, bk} 이 성립 되 므 로 작업 k 를 맨 뒤에 배치 하여 최 적 화 된 스케줄 의 마지막 작업 으로 해 야 합 니 다.
알고리즘 설명:
1. 2n 길이 의 배열 C 를 만 듭 니 다.
a1, a2, 94777 °, an 을 C [1] ~ C [n] 에 차례대로 넣 고,
b1, b2, 94777 °, bn 은 C [n + 1] ~ C [2n] 에 차례대로 넣는다. /* O (n), 다음은 이 2n 개 수 를 정렬 합 니 다 * /
2. 2n 길이 의 배열 D 를 초기 화 합 니 다:
D [1] ~ D [n] 에서 1, 2, 94777 °, n 을 순서대로 넣 습 니 다.
D [n + 1] ~ D [2n] 에서 순서대로 - 1, - 2, 94777 °, - n 을 넣는다. /* O (n) 는 각각 a1, a2, 94777 °, an 과 b1, b2, 94777 °, bn 의 아래 표 * / 에 대응 합 니 다.
3. 배열 C 를 정렬 합 니 다.
D [k] 는 항상 C [k] 와 의 대응 관 계 를 유지한다.(O (n log n), C [i] 와 C [j] 가 바 뀌 면 D [i] 도 D [j] 와 바뀐다.)
a1, a2, 94777 °, an 및 b1, b2, 94777 °, bn 이 어 렸 을 때 부터 큰 순 서 를 세운 후에 D [1] ~ D [2n] 도 어 렸 을 때 부터 큰 순서 로 이런 ai 와 bj 의 아래 표 시 는 바로 작업 번호 (bj 의 아래 표 시 는 ai 와 구별 된다) 를 기록 했다.
4. E [1] ~ E [n] 을 모두 "No" 로 설정 합 니 다. / *O (n), 모든 퀘 스 트 가 배정 되 지 않 았 음 을 표시 합 니 다 * /
5. 다음 변수 초기 화: i ← 1;j←n;k←1; /*O(1),*/
/*i 현재 가장 왼쪽 빈 자 리 를 가리 키 는 F [i], * /
/*현재 가장 먼저 배정 해 야 할 작업 번 호 를 놓 습 니 다. * /
/* j 현재 가장 오른쪽 빈자리 F [j], * /
/*현재 마지막 으로 배정 해 야 할 작업 번 호 를 놓 습 니 다. * /
/* k 는 1 부터 1, D [k] (또는 - D [k]) * /
/*ai 와 bj 의 어 릴 때 부터 큰 순서 로 순서대로 작업 번 호 를 드 립 니 다. * /
6. while i ≤ j do
{ /* 작업 이 아직 완료 되 지 않 았 습 니 다. i 는 어 릴 때 부터 크 고 작은 것 까지 * /
if D[k]>0 then /*D [k] > 0 즉 D [k] 에 ai 가 표시 되 어 있 습 니 다 * /
{ if E [D [k] "No" then /*작업 D [k] 가 준비 되 지 않 았 습 니 다 * /
{F [i] ← D [k]; i 증가 1; E [D [k] 를 "Yes" 로 설정 합 니 다}
}/*작업 D [k] 현재 가장 왼쪽 빈 자리 에 놓 기 * /
else /*D [k] < 0, 그러면 – D [k] 는 bj 아래 표 시 됩 니 다 * /
{ if E [– D [k] 는 "No" then / * 작업 – D [k] 는 아직 배정 되 지 않 았 습 니 다 * /
{F [j] ← – D [k]; j 마이너스 1; E [– D [k] 를 "Yes" 로 설정 합 니 다.}
} /*작업 – D [k] 현재 가장 오른쪽 빈자리 에 놓 기 * /
k 증 1; / * 후속 작업 배정 을 위해 다음 D [k] 를 검사 하려 고 합 니 다 * /
}
C 언어 구현:
#include
#include
#define MAX_LEN 128
void heap_adjust(int *array,int *index,int n,int loc)
{
int tmp,i,j,k;
tmp=array[loc];
k=index[loc];
for(i=loc;2*i0;i--)
heap_adjust(array,index,n,i);
for(i=n;i>1;i--)
{
tmp=array[i];
array[i]=array[1];
array[1]=tmp;
j=index[i];
index[i]=index[1];
index[1]=j;
heap_adjust(array,index,i,1);
}
}
int main()
{
int n,i,j,k;
int A[MAX_LEN],B[MAX_LEN],C[MAX_LEN*2],D[MAX_LEN*2],E[MAX_LEN],F[MAX_LEN];
while(1==scanf("%d",&n)){
if(n > 0 && n < MAX_LEN){
for(i=1;i<=n;i++)
scanf("%d%d",A+i,B+i);
break;
}
printf("invalid n
");
}
//initial tabs
for(i=1;i<=2*n;i++){
if(i<=n){
C[i]=A[i];
D[i]=i;
E[i]=0;
}
else{
C[i]=B[i-n];
D[i]=-(i-n);
}
}
//sort it!
heap_sort(C,D,2*n);
//dp find
for(k=1,i=1,j=n;i<=j;k++){
if(D[k] > 0){
if(E[D[k]] == 0){
F[i++]=D[k];
E[D[k]]=1;
}
}
else{
if(E[-D[k]] == 0){
F[j--]=-D[k];
E[-D[k]]=1;
}
}
}
printf("scheduled tasks:");
for(i=1;i<=n;i++)
printf("%-3d",F[i]);
printf("
");
return 0;
}
알고리즘 구현 결과:
that's all~
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
최 우수 흐름 작업 스케줄 링현재 작업 i 를 S 의 첫 번 째 가공 작업 으로 선택 한 후, 기계 P2 에서 S - {i} 의 작업 을 가공 하기 전에 필요 한 대기 시간 은 bi + max {t - ai, 0} 입 니 다.이 는 P2 가 가...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.