히프 응용-LPT 알고리즘

LPT(Longest Processing Time first): 가장 긴 작업을 우선적으로 할당하는 방법

- 서로 다른 소요 시간을 가지는 작업들을 가장 짧은 시간 내에 마무리해야 할 때 LPT를 이용해 근사의 해를 찾을 수 있다.

 

m개의 기계와 n개의 작업이 있고, 각 작업에 걸리는 기계의 사용 시간이 다르다고 가정하자. 모든 기계를 가동하여 최소의 시간 내에 작업들을 모두 끝내는 문제를 머신 스케줄링(machine scheduling)이라 한다. 

이때 LPT를 활용해 문제를 해결할 수 있다.

 

아래와 같이 기계 사용 시간에 따라 정렬된 7개의 작업이 있고 동일한 기계가 3대 있을 때,

J1	J2	J3	J4	J5	J6	J7
8	7	6	5	3	2	1

 

LPT 알고리즘은 각 작업들을 가장 먼저 사용 가능하게 되는(=이전 작업이 가장 빨리 끝나는) 기계에 할당한다. LPT 알고리즘을 사용하면 위 작업들은 아래와 같이 할당된다.

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
M1
M2
M3

 

이때 최대 히프가 아닌 최소 히프를 사용하고, 최소 히프는 모든 기계의 종료 시간을 저장하고 있다.

 

처음에는 어떤 기계도 사용되지 않았으므로 모든 기계의 종료 시간이 0이다. 히프에서 최소의 종료 시간을 가지는 기계를 삭제해 작업을 할당하고, 선택된 기계의 종료 시간을 업데이트해 히프에 다시 저장한다.

 

맨 처음에 M1이 선택되었다 가정하면, 선택된 M1은 히프에서 삭제되고 작업 J1(소요 시간=8)이 M1에 할당된다.

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
M1	J1
M2
M3

 

다음 작업은 소요 시간이 7인 J2이다. M2와 M3이 비어 있으므로 M2에 할당한다.

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
M1	J1
M2	J2
M3

 

그 다음 소요 시간이 6인 J3을 M3에 할당한다.

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
M1	J1
M2	J2
M3	J3

 

다음 작업은 소요 시간이 5인 J4이고, M1~M3 중 가장 먼저 현재 작업을 마무리하고 사용 가능하게 되는 기계가 M3이므로 M3에 J4를 할당한다.

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
M1	J1
M2	J2
M3	J3						J4

 

모든 작업을 완료할 때까지 위와 같이 할당한다.

 

결과>>

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
M1	J1								J6
M2	J2							J5			J7
M3	J3						J4

---

LPT 알고리즘의 구현

 

항상 종료 시간이 최소인 기계를 선택해야 하므로 기계의 종료 시간이 중요하다. 기계의 종료 시간을 최소 히프에 넣고, 최소 히프에서 기계를 꺼내 그 기계에 작업을 할당하면 된다. 작업을 할당한 후 기계의 종료 시간을 작업 시간만큼 증가시켜 다시 최소 히프에 삽입한다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_ELEMENT 200

typedef struct {
	int id;
	int avail;
} element;
typedef struct {
	element heap[MAX_ELEMENT];
	int heap_size;
} HeapType;

//생성
HeapType* create() {
	return (HeapType*)malloc(sizeof(HeapType));
}
//초기화
void init(HeapType* h) {
	h->heap_size = 0;
}
//삽입
void insert_min_heap(HeapType* h, element item) {
	int i;
	i = ++(h->heap_size);

	while ((i != 1) && (item.avail < h->heap[i / 2].avail)) {
		h->heap[i] = h->heap[i / 2];
		i /= 2;
	}
	h->heap[i] = item;
}
//삭제
element delete_min_heap(HeapType* h) {
	int parent, child;
	element item, temp;

	item = h->heap[1];
	temp = h->heap[(h->heap_size)--];
	parent = 1;
	child = 2;
	while (child <= h->heap_size) {
		if ((child < h->heap_size) && (h->heap[child].avail) > h->heap[child + 1].avail) {
			child++;
		}
		if (temp.avail < h->heap[child].avail) {
			break;
		}
		h->heap[parent] = h->heap[child];
		parent = child;
		child *= 2;
	}
	h->heap[parent] = temp;
	return item;
}

#define JOBS 7
#define MACHINES 3

int main(void) {
	int jobs[JOBS] = { 8,7,6,5,3,2,1 };
	element m = { 0,0 };
	HeapType* h;
	h = create();
	init(h);

	for (int i = 0; i < MACHINES; i++){
		m.id = i + 1;
		m.avail = 0;
		insert_min_heap(h, m);
	}

	for (int i = 0; i < JOBS; i++) {
		m = delete_min_heap(h);
		printf("JOB %d을 시간=%d부터 시간=%d까지 기계 %d에 할당한다. \n", i, m.avail, m.avail + jobs[i] - 1, m.id);
		m.avail += jobs[i];
		insert_min_heap(h, m);
	}
	return 0;
}

>>