Algorithm] 작업 스케줄링(Task Scheduling)

Algorithm] 작업 스케줄링(Task Scheduling)

기계에서 수행하는 n개의 작업(T1, T2, T3, ... , Tn)이 있고,

각 작업에 시작 시간과 종료 시간이 존재한다고 할 때 최소한의 기계를 배치하면서

모든 작업을 수행하도록 하는 문제를 작업 스케줄링이라고 한다.

이 때 수행 시간이 중복되지 않게 모든 작업을

가장 적은 수의 기계에 배정하는 최적해를 구하는 문제라는 것에 초점을 두자.

작업 스케줄링 문제에서 우리가 다룰 수 있는 변수와

알 수 있는 정보에 대해서 조금 생각해보도록 하자.

작업의 수 n과, 각 작업들의 시작 시간과 종료 시간이 기본적으로 입력값으로 들어올 것이다.

이건 입력값을 통해서 우리가 알 수 있는 정보고

문제를 살펴봤을 때 우리가 알 수 있는 정보가 하나 더 있다.

그 어떠한 경우에도 배치된 기계가 작업의 수보다 많을 수 없다는 것이다.

이제 우리는 최적해를 구해볼 필요가 있는데

우리에게 주어진 정보를 바탕으로 최적해를 구하려면

시작시간, 종료시간, 그리고 그를 바탕으로 구할 수 있는 작업의 길이를 바탕으로

알고리즘을 구현하면 될 것 같다.

네 가지 정도의 경우가 존재한다.

1. 빠른 시작시간 작업 우선

2. 빠른 종료시간 작업 우선

3. 짧은 작업 우선

4. 긴 작업 우선

이 네 가지 우선 원칙 중에서 1번의 원칙을 제외하고는,

그리디 알고리즘을 사용하는 상황에서 항상 최적해를 보장하지 못한다.

각각의 반례에 대해서는 직접 생각해볼 필요가 있다.

근시안적으로 최적해를 찾아나가는 그리디 알고리즘이라 반례를 찾기가 더욱 쉽다.

어떻게 만들어나갈지 방법은 정했고,

이제 의사코드를 살펴보자.

입력 : n개의 작업

출력 : 기계에 배정된 작업 순서

작업 시작 전, 빠른 시작 시간으로 오름차순 정렬하여 배열(arr)에 삽입

arr[0] ~ arr[n-1], i=0

while(i<n) {

if(arr[i]를 수행할 수 있는 기계가 있으면)

arr[i]를 해당 기계에 배정

else

새로운 기계에 arr[i]를 배정

i++

}

return 기계에 배정된 결과

이런 과정으로 진행하면 이 알고리즘의 시간 복잡도는 O(nlogn)+O(mn)이 된다.

이 때 m은 배정되는 기계의 수다.

앞서 말했듯 배정되는 기계의 수가 n에 가까워질수록 수행 속도가 느려진다.

소스코드를 한 번 살펴보자.

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<pair<int, int> >    task;
vector< vector<int> > machine;
int nMachine;
 
int Operating(int start)
{
    int i;
    // 업무가 할당된 기계가 존재하는 경우
    if (nMachine > 0)
    {
        for (i = 0; i < nMachine; i++)
        {
            // 업무를 수행하고 있는 기계가 있고,
            // 그 기계가 다음 업무를 수행할 수 있는 경우 해당 기계를 배치
            if (machine[i].size() > 0 && task[machine[i].back()].second <= start)
            {
                return i;
            }
        }
 
        // 업무를 수행할만한 기계가 없으면 새 기계를 배치
        nMachine++;
        return i;
    }
    // 업무가 할당된 기계가 존재하지 않는 경우
    else
    {
        nMachine++;
        return 0;
    }
}
 
void Scheduling(int nTask)
{
    int i = 0;
    while (i < nTask)
    {
        // 기계 번호를 할당 받고,
        // 해당 기계에 업무 배정
        int machineNum=Operating(task[i].first);
        machine[machineNum].push_back(i);
        i++;
    }
}
 
int main(void)
{
    int n;
    int start, end;
 
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> start >> end;
        task.push_back(make_pair(start, end));
    }
 
    // 이중 배열
    for (int i = 0; i < n; i++)
    {
        vector<int> element(0);
        machine.push_back(element);
    }
    nMachine = 0;
    
    // 업무 시작 시간 기준으로 오름차순 정렬
    sort(task.begin(), task.end());
 
    // 스케줄링 시작
    Scheduling(task.size());
 
    for (int i = 0; i < n; i++)
    {
        if (machine[i].size() != 0)
        {
            cout << "Machine No." << i + 1 << endl;
            for (int j = 0; j < (int)machine[i].size(); j++)
            {
                cout << "(" << task[machine[i][j]].first << ", ";
                cout << task[machine[i][j]].second << ")" << " ";
            }
        }
        cout << endl;
    }
 
    return 0;
}

나는 이 문제를 풀 때 새로운 기계를 할당하고,

그 기계에 작업을 할당하는 과정을 매 순간 동적할당을 해야 한다고 판단했다.

공부하는 차원에서 연결 리스트 등을 만들어 손수 작업하는 것도 나쁘지 않지만,

STL에서 vector를 사용하면 정렬부터 모든 것들을 손쉽게 해결할 수 있고,

원하는 알고리즘에 초점을 둘 수 있다.

여기서 vector를 이중배열처럼 사용하기 위해 일련의 과정을 거쳐

이해하기 어려운 사람들이 일부 있을 것이라고 사료되는데,

이 부분에 대해서는 빠른 시일내에 보충 설명하여 링크를 걸어둘 생각이다.

이런 작업 스케줄링은 산업 전반에서 많이 쓰이고

가장 피부에 와닿는 예시는 아마 강의실/세미나룸 배정 등이 있을 것이다.