최 우수 흐름 작업 스케줄 링

최 우선 흐름 스케줄 링 문제
질문 설명:
       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~