머신 스케쥴링

머신 스케쥴링이란 모든 기계를 가동시켜 가장 최소의 시간 안에 작업들을 모두 끝내기 위한 것을 말한다. 이 문제는 알고리즘 분야에서 상당히 유서 깊은 문제로 많은 응용 분야를 가지고 있는데, 예를 들어 서버가 여러 개 있어 서버에 작업을 분배할 때도 사용할 수 있다.

분배를 위한 최적의 해를 찾는 것은 어렵지만 근사의 해를 찾는 방법은 있다. 그 중 한가지가 LPT 알고리즘이다.

LPT(Logest Processing Time fist)

LPT 알고리즘은 가장 긴 작업을 우선적으로 기계에 할당하는 것이다. 예를 들어 다음과 같은 순서대로 7개의 작업이 예정되어 있고 동일한 기계가 3대가 있다고 하자. 각 작업들은 기계 사용 시간에 따라서 다음과 같이 미리 정렬되어 있다고 가정한다.

그리고 작업들을 가장 작업이 적은 머신에 할당하는 것이다.

나머지 작업들도 위와 같은 방식으로 할당해 주면 된다.

LPT 알고리즘은 우선순위 큐를 사용하여 구현 가능한데, 최소 힙을 사용하여 구현하면 된다.

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);

	// 루트 노드가 아니고, item이 부모 노드보다 작으면 계속 반복(최소 힙이기 때문)
	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() {
	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;
}

출처
C언어로 쉽게 풀어쓴 자료구조 - 천인구