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

2024. 7. 3. 22:15·Computer Science/Algorithm

최단 작업 우선 스케줄링

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

 

  • 대기열에는 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++

'Computer Science > Algorithm' 카테고리의 다른 글

[Algorithm/Greedy] 작업 스케줄링 문제  (0) 2024.07.03
[Algorithm/Greedy] 배낭 문제(knapsack problem)  (0) 2024.07.03
[Algorithm/Greedy] About 그리디 알고리즘  (0) 2024.07.03
[Algorithm/Divide&Conquer] 10. 거듭 제곱 계산법  (0) 2024.07.02
[Algorithm/Divide&Conquer] 09. 분할 정복을 적용하는데 있어서 주의할 점  (0) 2024.07.02
'Computer Science/Algorithm' 카테고리의 다른 글
  • [Algorithm/Greedy] 작업 스케줄링 문제
  • [Algorithm/Greedy] 배낭 문제(knapsack problem)
  • [Algorithm/Greedy] About 그리디 알고리즘
  • [Algorithm/Divide&Conquer] 10. 거듭 제곱 계산법
lumana
lumana
배움을 나누는 공간 https://github.com/bebeis
  • lumana
    Brute force Study
    lumana
  • 전체
    오늘
    어제
    • 분류 전체보기 (452) N
      • Software Development (27) N
        • Performance (0)
        • TroubleShooting (1)
        • Refactoring (0)
        • Test (8) N
        • Code Style, Convetion (0)
        • DDD (0)
        • Software Engineering (18)
      • Java (71) N
        • Basic (5)
        • Core (21)
        • Collection (7)
        • 멀티스레드&동시성 (13)
        • IO, Network (8)
        • Reflection, Annotation (3)
        • Modern Java(8~) (12)
        • JVM (2) N
      • Spring (53) N
        • Framework (12)
        • MVC (23)
        • Transaction (3) N
        • AOP (11) N
        • Boot (0)
        • AI (0)
      • DB Access (1)
        • Jdbc (1)
        • JdbcTemplate (0)
        • JPA (14)
        • Spring Data JPA (0)
        • QueryDSL (0)
      • Computer Science (125)
        • Data Structure (27)
        • OS (14)
        • Database (10)
        • Network (21)
        • 컴퓨터구조 (1)
        • 시스템 프로그래밍 (23)
        • Algorithm (29)
      • HTTP (8)
      • Infra (1) N
        • Docker (1) N
      • 프로그래밍언어론 (15)
      • Programming Language(Sub) (77) N
        • Kotlin (1) N
        • Python (25)
        • C++ (51)
        • JavaScript (0)
      • FE (11)
        • HTML (1)
        • CSS (9)
        • React (0)
        • Application (1)
      • Unix_Linux (0)
        • Common (0)
      • PS (13)
        • BOJ (7)
        • Tip (3)
        • 프로그래머스 (0)
        • CodeForce (0)
      • Book Review (4)
        • Clean Code (4)
      • Math (3)
        • Linear Algebra (3)
      • AI (7)
        • DL (0)
        • ML (0)
        • DA (0)
        • Concepts (7)
      • 프리코스 (4)
      • Project Review (6)
      • LegacyPosts (11)
      • 모니터 (0)
      • Diary (0)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.4
lumana
[Algorithm/Greedy] 최단 작업 우선 스케줄링(shortest-job-first scheduling)
상단으로

티스토리툴바