[Data Structure] LPT 알고리즘 (히프)

머신 스케줄링

- 동일한 기계 m개, 처리해야 하는 작업 n개가 존재

•   모든 기계를 가동해서 가장 최소의 시간 안에 작업을 모두 끝내는 것 = 머신 스케줄링

- 각 작업마다 완료까지 걸리는 시간이 다름

1. 종료 시간이 최소인 기계를 선택 
2. 해당 기계에 작업시간이 최대인 작업을 할당한다

 

▶ LPT 알고리즘  

- ex) 여러 서버에 작업을 분배 할 경우, 가장 효율이 좋은 최적의 해(근사의 해)를 찾는 알고리즘

 

- 항상 종료시간이 최소인 기계를 선택 → 최소 히프를 통해서 구현

• -----------------------------------------------------------------------------------------------------------

1. 기계들을 최소 히프에 전부 insert 
2. 최소 히프에서 기계 delete 
3. 해당 기계에 작업 시간 최대인 작업 할당 
4. 작업 할당 후, 해당 기계의 종료 시간을 작업 시간만큼 증가시키고 다시 최소 히프에 insert

• -----------------------------------------------------------------------------------------------------------

- 작업이 끝날 때 까지 2, 3, 4 반복

 

---

※ Example) 머신스케쥴링

- 기계 3대 존재 (M1, M2, M3)

- 작업 7개 존재

 

(기계, 작업 시간)

작업	J1	J2	J3	J4	J5	J6	J7
작업 시간	8	7	6	5	3	2	1
색깔

1. 모든 기계(M1, M2, M3)를 최소 히프에 insert
2. 최소 히프에서 delete 시킨 기계(M1)에 작업 시간에 최대인 작업(J1 - 8시간) 할당
3. 기계 M1은 (M1, 8)이 되고 M1을 다시 최소 히프에 insert

 

1. 최소 히프에서 delete 시킨 기계(M2)에 작업 시간에 최대인 작업(J2 - 7시간) 할당
2. 기계 M2은 (M2, 7)이 되고 M2을 다시 최소 히프에 insert

1. 최소 히프에서 delete 시킨 기계(M3)에 작업 시간에 최대인 작업(J3 - 6시간) 할당
2. 기계 M3은 (M3, 6)이 되고 M3을 다시 최소 히프에 insert

1. 최소 히프에서 delete 시킨 기계(M3)에 작업 시간에 최대인 작업(J4 - 5시간) 할당
2. 기계 M3은 (M3, 11)이 되고 M3을 다시 최소 히프에 insert

1. 최소 히프에서 delete 시킨 기계(M2)에 작업 시간에 최대인 작업(J5 - 3시간) 할당
2. 기계 M2은 (M2, 10)이 되고 M2을 다시 최소 히프에 insert

1. 최소 히프에서 delete 시킨 기계(M1)에 작업 시간에 최대인 작업(J6 - 2시간) 할당
2. 기계 M1은 (M1, 10)이 되고 M1을 다시 최소 히프에 insert

1. 최소 히프에서 delete 시킨 기계(M2)에 작업 시간에 최대인 작업(J7 - 1시간) 할당 → 마지막 작업
2. 기계 M2은 (M2, 11)이 되고 M2을 다시 최소 히프에 insert

• 모든 작업이 끝나고 최소 히프트리의 모습

 

▶ 기계별 작업 현황

작업	J1	J2	J3	J4	J5	J6	J7
작업 시간	8	7	6	5	3	2	1
색깔

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

---

Full Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// LPT 알고리즘을 이용한 머신 스케줄링 (최소 히프 사용)
// 기계 3대, 작업 10개
#define MAX_HEAP_SIZE 300
#define MACHINES 3
#define JOBS 10

typedef struct{
	char name[100]; // 기계 이름
	int usetime; // 기계 사용시간 저장
}machine;

machine m = { 0, 0};

typedef struct{
	char name[100]; // 작업 이름
	int working; // 작업 걸리는 시간
}job;

typedef struct {
	machine heap[MAX_HEAP_SIZE];
	int heap_size;
}heapnode;

typedef struct { // 작업시간 별 정렬 전용 구조체
	job heap[MAX_HEAP_SIZE];
	int heap_size;
}heapnode_job;

heapnode* create() {
	return (heapnode*)malloc(sizeof(heapnode));
}

void init_heap(heapnode* h) {
	h->heap_size = 0;
}

int is_empty(heapnode* h) {
	return h->heap_size == 0;
}

int is_full(heapnode* h) {
	return h->heap_size == MAX_HEAP_SIZE - 1;
}

void insert_min_heap(heapnode* h, machine item) {
	if (is_full(h)) {
		fprintf(stderr, "Error : Heap is full\n\n");
		return;
	}
	else {
		int index = ++h->heap_size;
		while (index != 1 && (item.usetime < h->heap[index / 2].usetime)) {
			h->heap[index] = h->heap[index / 2];
			index /= 2;
		}
		h->heap[index] = item;
	}
}

machine delete_min_heap(heapnode* h) {
	if (is_empty(h)) {
		fprintf(stderr, "Error : Heap is empty\n\n");
		return;
	}
	else {
		machine root = h->heap[1];
		machine last = h->heap[h->heap_size--];
		int index = 1;
		int child = 2;
		while (child <= h->heap_size) {
			if (child < h->heap_size && (h->heap[child].usetime > h->heap[child + 1].usetime))
				child++;
			if (last.usetime < h->heap[child].usetime) break;
			h->heap[index] = h->heap[child];
			index = child;
			child *= 2;
		}
		h->heap[index] = last;
		return root;
	}
}

void insert_max_heap(heapnode_job* h, job job) {
	// 히프 정렬 (작업 시간 별 정렬) 용 함수
	if (is_full(h)) {
		fprintf(stderr, "Error : Heap is full\n\n");
		return;
	}
	else {
		int index;
		index = ++(h->heap_size);
		while (index != 1 && (job.working > h->heap[index / 2].working)) {
			h->heap[index] = h->heap[index / 2];
			index /= 2;
		}
		h->heap[index] = job;
	}
}

job delete_max_heap(heapnode_job* h) {
	// 히프 정렬 (작업 시간 별 정렬) 용 함수
	if (is_empty(h)) {
		fprintf(stderr, "Error : Heap is empty\n\n");
		return;
	}
	else {
		job root = h->heap[1];
		job last = h->heap[h->heap_size--];
		int index = 1;
		int child = 2;
		while (child <= h->heap_size) {
			if (child < h->heap_size && (h->heap[child].working < h->heap[child + 1].working))
				child++;
			if (last.working >= h->heap[child].working) break;
			h->heap[index] = h->heap[child];
			index = child;
			child *= 2;
		}
		h->heap[index] = last;
		return root;
	}
}

void job_sort_desc(job arr[]) {
	heapnode_job* h;
	h = create();
	init_heap(h);
	for (int i = 0; i < JOBS; i++) {
		insert_max_heap(h, arr[i]);
	}

	for (int i = 0; i < JOBS; i++) {
		arr[i] = delete_max_heap(h);
	}
	free(h); // 히프 동적 할당 해제
}

void machine_possess(machine machine[]) {
	// 기계 현황 print
	for (int i = 0; i < MACHINES; i++) {
		printf("Name : \"%s\" -- Usage Time : %d\n", machine[i].name, machine[i].usetime);
	}
}

void job_possess(job job[]) {
	// 작업 현황 print
	for (int i = 0; i < JOBS; i++) {
		printf("Name : \"%s\" -- Working Time : %d\n", job[i].name, job[i].working);
	}
}

int main(void) {
	heapnode* h;
	h = create();
	init_heap(h);

	machine machine[MACHINES]; // 기계 3대
	job job[JOBS]; // 작업 10개
	
	printf("-------------------------------------------------------\n");
	printf(">> 기계 정보 작성\n");
	for (int i = 0; i < MACHINES; i++) { // 기계 정보 작성
		printf("Machine Name : ");
		scanf("%s", machine[i].name);
		machine[i].usetime = 0;
		printf("%s Create\n", machine[i].name);
	}

	printf("-------------------------------------------------------\n");
	printf(">> 기계 보유 현황\n");
	machine_possess(machine);

	printf("-------------------------------------------------------\n");
	printf(">> 작업 정보 작성\n");
	for (int i = 0; i < JOBS; i++) { // 작업 정보 작성
		printf("Job Name : ");
		scanf("%s", job[i].name);
		printf("\"%s\" Working Time : ", job[i].name);
		scanf("%d", &job[i].working);
	}

	printf("-------------------------------------------------------\n");
	printf(">> 작업 현황\n");
	job_possess(job);

	printf("-------------------------------------------------------\n");
	printf(">> 작업 현황 정렬(작업 시간 내림차순)\n");
	job_sort_desc(job);
	job_possess(job);

	for (int i = 0; i < MACHINES; i++) {
		insert_min_heap(h, machine[i]);
	}
	printf("-------------------------------------------------------\n");
	printf(">> 작업 시작\n");
	for (int i = 0; i < JOBS; i++) {
		m = delete_min_heap(h); // 최소 히프에서 작업을 위한 machine 꺼내기
		printf("%-7s : \"%s\" -> Time %d ~ %d\n"
			, job[i].name, m.name, m.usetime, m.usetime + job[i].working - 1);
		m.usetime += job[i].working; // 각 machine usetime에 작업 시간 추가
		insert_min_heap(h, m); // 작업 종료 후, 꺼낸 machine 다시 insert
	}

	printf("-------------------------------------------------------\n");
	printf(">> 작업 종료 후 기계 별 사용시간 (오름차순)\n");
	for (int i = 0; i < MACHINES; i++) {
		m = delete_min_heap(h); // delete하게 되면 기계 작동시간 오름차순으로 꺼내짐
		printf("Name : \"%s\" -- Usage Time : %d\n", m.name, m.usetime);
	}

	return 0;
}