[Algorithm/Greedy] 최단 작업 우선 스케줄링(shortest-job-first scheduling)

최단 작업 우선 스케줄링

사람들이 은행 창구에 줄을 서서 순서를 기다리는 상황을 생각해보자.

 

• 대기열에는 N명의 사람이 기다리고 있다.
• 각 사람마다 일 처리에 필요한 시간은 다르다
• 대기열에 기다리고 있던 모든 사람이 매우 합리적이어서 평균 대기 시간이 최소화될 수 있도록 대기 순서를 다시 정하는 것에 동의한다고 가정한다.
  • 따라서 평균 대기 시간을 최소화하는 것이 목표이다.
  • 가능한 많은 사람의 대기 시간을 줄일 수 있는 방법을 찾아보자.
    • 일 처리가 가장 빨리 끝나는 사람을 맨 앞에 세워야 한다

 

최단 작업 우선 스케줄링 구현

최단 작업 우선 스케줄링을 구현하는 것은 매우 단순하다. 일 처리 소요 시간 순으로 오름차순으로 정렬하면 된다.

정렬 전 대기 시간과 정렬 후 대기 시간을 비교해보는 코드를 작성해보자

 

#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(int argc, char* argv[])
{
	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);
}

 

 

Ref) 코딩 테스트를 위한 자료 구조와 알고리즘 with C++