최단 작업 우선 스케줄링(Shortest-Job-First Scheduling)

최단 작업 우선 스케줄링(Shortest-Job-First Scheduling)

• 그리디 알고리즘(Greedy Algorithm)으로 해결할 수 있는 문제 중 하나

 

예 : 은행 창구

• 하나의 창구에서만 업무를 보고 있음.
• 대기열에 N명의 사람이 기다리고 있음.
  • 서로 다른 용무로 방문했기 떄문에 일 처리에 필요한 시간은 사람들마다 서로 다름.
  • 대기열에 기다리고 있던 모든 사람이 매우 합리적이어서 평균 대기 시간이 최소화될 수 있도록 대기 순서를 다시 정하는 것 에 동의하였음.
• 그래서 이제 대기 순서를 어떻게 바꿔야 하는지를 결정해야 함.

• 항목
  • Pi : i번째 사람
  • Ai : Pi의 일 처리 시간
  • Wi : Pi가 기다려야 하는 시간
• 창구에서 가까운 사람이 먼저 일을 처리할 수 있으므로 첫 번째 사람 P0의 대기 시간은 A0 = 0임.
• 대기열에서 두 번째에 있는 사람은 첫 번째 사람의 일 처리 시간만큼 기다려야 하기 떄문에 A1 = 8임.
• 비슷한 방식으로 i번째 사람은 첫 번째 사람부터 i - 1번째 사람까지의 일 처리 시간의 합만큼 대기 시간이 필요함.
• 문제 해결 방법
  • 평균 대기 시간 을 최소화하는 것이 목표
  • 가능한 많은 사람의 대기 시간을 줄일 수 있는 방법을 찾아야 함.
  • 모든 사람의 대기 시간을 줄이려면, 일 처리가 가장 빨리 끝나는 사람 을 맨 앞에 세워야 함.
    • 이 방식을 반복하면 아래의 그림과 같은 형태의 순서를 재설정할 수 있음.

• 거의 2배로 성능이 향상된 것을 볼 수 있음.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
 
template<typename T>
auto compute_waiting_times(std::vector<T>& service_times) {
    std::vector<T> W(service_times.size());
    W[0] = 0;
 
    for (auto i = 1; i < service_times.size(); i++) {
        W[i] = W[i - 1] + service_times[i - 1];
    }
 
    return W;
}
 
template<typename T>
void print_vector(std::vector<T>& V) {
    for (auto& i : V) {
        std::cout.width(2);
        std::cout << i << " ";
    }
    std::cout << std::endl;
}
 
template<typename T>
void compute_and_print_waiting_times(std::vector<T>& service_times) {
    auto waiting_times = compute_waiting_times<int>(service_times);
 
    std::cout << "- 처리 시간: ";
    print_vector<T>(service_times);
 
    std::cout << "- 대기 시간: ";
    print_vector<T>(waiting_times);
 
    auto ave_waiting_times = std::accumulate(waiting_times.begin(), waiting_times.end(), 0.0) / waiting_times.size();
 
    std::cout << "- 평군 대기 시간: " << ave_waiting_times;
 
    std::cout << std::endl;
}
 
int main() {
    std::vector<int> service_times { 8, 1, 2, 4, 9, 2, 3, 5 };
 
    std::cout << "[처음 일 처리 시간 & 대기 시간]" << std::endl;
    compute_and_print_waiting_times<int>(service_times);
 
    // 일 처리 시간을 오름차순으로 정렬
    std::sort(service_times.begin(), service_times.end());
 
    std::cout << std::endl;
    std::cout << "[정렬 후 일 처리 시간 & 대기 시간]:" << std::endl;
    compute_and_print_waiting_times<int>(service_times);
 
    return 0;
}

 

결과

[처음 일 처리 시간 & 대기 시간]
- 처리 시간:  8  1  2  4  9  2  3  5 
- 대기 시간:  0  8  9 11 15 24 26 29 
- 평군 대기 시간: 15.25
 
[정렬 후 일 처리 시간 & 대기 시간]:
- 처리 시간:  1  2  2  3  4  5  8  9 
- 대기 시간:  0  1  3  5  8 12 17 25
- 평군 대기 시간: 8.875