[Algorithm] 작업 스케줄링

💡작업스케줄링

• 수행해야할 다수의 Job을 주어진 목적에따라 어떻게 수행할지를 결정하는 문제
• 주어진 목적에따라 작업스케줄링을 다양하게 정의할 수 있다. 
• 이러한 문제들은 대부분 NP-hard문제이나, 일부 목적에 대해서 또는 문제를 단순화 시킬 경우 polynomial time에 해결할 수 있다.

 

💡작업스케줄링 문제

• 작업의 수행시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계에 배정하는 문제이다.
• n개의 각작업은 시작시간과 종료시간이 있다.
• 주어진 문제요소
  1. 작업의 수
  2. 각 작업의 시작과 종료시간 : 이는 정해져 있으므로 작업의 길이도 주어진 것이 된다.
• 시각시간, 종료시간, 작업의 길이에 대해 그리디 알고리즘을 생각해 볼 수 있는데
  1. 빠른 시작시간 작업 우선 배정
  2. 빠른 종료시간 작업 우선 배정
  3. 짧은 작업 우선 배정
  4. 긴 잡업 우선 배정
• 이중 1번째 알고리즘만이 최적해를 찾을 수 있다.

 

💡의사코드

• 입력 : n개의 작업 t1~tn
• 출력 : 각 기계에 배정된 작업 순서

• 1. 시작 시간의 오름차순으로 정렬한 작업 리스트 L
  2. while(L!=∅){
  3. 	L에서 가장 이른 시작시간의 작업 ti를 가져온다.
  4. 	if(ti를 수행할 기계가 있다면)
  5. 		ti를 수행할 수 있는 기계에 배정한다.
  6. 	else
  7. 		새로운 기계에 ti를 배정한다.
  8. 	ti를 L에서 제거한다.
  }
  9. return 각 기계에 배정된 작업 순서

 

 

💡C++ 코드

#include <iostream>
#include <vector> // 벡터 리스트시 사용
#include <utility> // 입력값 -> 벡터리스트 한쌍으로
#include <algorithm>

using namespace std;

#define X first
#define Y second

// 입출력 속도 개선
#define IOFAST ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

vector<pair<int,int> > task;
vector< vector<int> > machine;
int nMachine = 0;

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(){
    IOFAST;
    int N;  // 작업의 수
    
    cin >> N;
    cin.ignore();

    for(int i=0;i<N;i++){
        int a,b;
        cin >> a >> b ;
        task.push_back(make_pair(a,b));
    }

    for (int i = 0; i < N; i++)
    {
        vector<int> element(0);
        machine.push_back(element);
    }

    sort(task.begin(), task.end());
    
    Scheduling(task.size());

    cout<<nMachine;
}

 

⏰시간복잡도

• Line1 : O(nlogn)
• while-루프에서는 작업을 L에서 가져다가 수행가능한 기계를 찾아서 배정하는 시간 : O(m) (m은 사용된 기계의 횟수)
• while루프가 수행된 총 횟수가 n번이므로, line2~9까지는 O(m)xn = O(nm)
• 따라서, O(nlogn) + O(mn)

---

➰응용

• 비즈니스 프로세싱
• 공장 생산 공정
• 강의실/세미나 룸 배정
• 컴퓨터 태스크 스케줄링

---

Reference

서울과학기술대학교 컴퓨터공학과 알고리즘 수업