[Algorithm/Greedy] 작업 스케줄링 문제

2024. 7. 3. 23:20·Computer Science/Algorithm

작업 스케줄링 문제

앞으로 해야 할 작업 목록을 가지고 있다고 해보자. 어떤 작업을 어떤 순서로 시행해야 할까?

 

 

Case 1) 특정 시점에 오직 하나의 작업만 수행할 수 있을 때

솔루션) 종료 시간 기준

  1. 각각의 작업은 고유한 ID, 시작 시간, 종료 시간을 갖는다. 이러한 작업을 표현할 구조체를 생성하자. 이 구조체는 인스턴스로 각 작업을 표현한다.
  2. N개의 작업을 포함하는 list를 생성한다. 각 작업은 1부터 N까지 고유한 ID를 가지며, 시작 시간과 종료 시간은 임의의 정수로 설정한다
  3. 스케줄링 함수를 작성한다
    1. 종료 시간을 기준으로 전체 작업 리스트를 정렬한다.
    2. 현재 리스트에서 그리디 방식으로 가장 빠른 종료 시간을 갖는 작업을 선택하자
    3. 현재 선택된 작업과 시간이 겹치는 작업은 모두 제거한다. 즉, 현재 작업 종료 시간보다 먼저 시작하는 작업은 제거한다
    4. 리스트에 작업이 남아있다면 2번 단계로 이동하고, 남아있지 않다면 선택된 작업들로 구성된 벡터를 반환한다.

 

Case 1) 작업 스케줄링 문제 구현(C++)

구조체 초기화

#include <list>
#include <algorithm>
#include <iostream>
#include <random>

// 모든 작업은 ID와 <시작 시간, 종료 시간> 쌍으로 표현됨
struct Task
{
	unsigned ID;
	unsigned start_time;
	unsigned end_time;
};

auto initialize_tasks(int num_tasks, int max_end_time)
{
	std::random_device rd;
	std::mt19937 rand(rd());
	std::uniform_int_distribution<std::mt19937::result_type> uniform_dist(1, max_end_time);

	std::list<Task> tasks;

	for (unsigned i = 0; i < num_tasks; i++)
	{
		auto start_time = uniform_dist(rand);
		auto end_time = uniform_dist(rand);
		
		if (start_time == end_time) end_time++;
		if (start_time > end_time) std::swap(start_time, end_time);

		tasks.push_back({i + 1, start_time, end_time});
	}

	return tasks;
}

 

작업 스케줄링 함수 구현

auto job_scheduling(std::list<Task> tasks) {
    // 작업 종료 시간을 기준으로 정렬
    tasks.sort([](const auto& lhs, const auto& rhs) {
        return lhs.end_time < rhs.end_time;
    });
    
    for (auto curr_task = tasks.begin(); curr_task != tasks.end(); curr_task++) {
        auto next_task = std::next(curr_task, 1);
        while (next_task != tasks.end() && next_task->start_time < curr_task->end_time ) {
            next_task = tasks.erase(next_task);
        }
    }
    return tasks;
}

 

테스트 코드 작성

void print(std::list<Task>& tasks, int max_end_time)
{
	for (auto t : tasks) {
		std::cout << "[" << t.ID << "] " << t.start_time << " -> " << t.end_time << "\t|";

		int i = 0;
		for (; i < t.start_time; i++) std::cout << " ";
		for (; i < t.end_time; i++) std::cout << "*";
		for (; i < max_end_time; i++) std::cout << " ";
		std::cout << "|" << std::endl;
	}
}

int main()
{
	int num_tasks = 10;
	int max_end_time = 20;

	auto tasks = initialize_tasks(num_tasks, max_end_time);
	std::cout << "[전체 작업]" << std::endl;
	print(tasks, max_end_time);

	auto scheduled_tasks = job_scheduling(tasks);
	std::cout << "\n[스케쥴 조정한 작업]" << std::endl;
	print(scheduled_tasks, max_end_time);
}

 

결과

[전체 작업]
[1] 20 -> 21    |                    *|
[2] 1 -> 17     | ****************   |
[3] 5 -> 8      |     ***            |
[4] 8 -> 9      |        *           |
[5] 12 -> 13    |            *       |
[6] 6 -> 9      |      ***           |
[7] 3 -> 14     |   ***********      |
[8] 1 -> 14     | *************      |
[9] 5 -> 6      |     *              |
[10] 5 -> 14    |     *********      |

[스케쥴 조정한 작업]
[9] 5 -> 6      |     *              |
[4] 8 -> 9      |        *           |
[5] 12 -> 13    |            *       |
[1] 20 -> 21    |                    *|

 

관련 백준 문제

https://www.acmicpc.net/problem/1931

 

Case 2) 특정 시점에 n개의 작업을 시행할 수 있을 때

<!-- 추후 작성 예정-->

 

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

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

[Algorithm/Greedy] 그래프 컬러링  (0) 2024.07.04
[Algorithm/Greedy] 최소 신장 트리(Minimum Spanning Tree, MST) 문제 (크루스칼)  (0) 2024.07.04
[Algorithm/Greedy] 배낭 문제(knapsack problem)  (0) 2024.07.03
[Algorithm/Greedy] 최단 작업 우선 스케줄링(shortest-job-first scheduling)  (0) 2024.07.03
[Algorithm/Greedy] About 그리디 알고리즘  (0) 2024.07.03
'Computer Science/Algorithm' 카테고리의 다른 글
  • [Algorithm/Greedy] 그래프 컬러링
  • [Algorithm/Greedy] 최소 신장 트리(Minimum Spanning Tree, MST) 문제 (크루스칼)
  • [Algorithm/Greedy] 배낭 문제(knapsack problem)
  • [Algorithm/Greedy] 최단 작업 우선 스케줄링(shortest-job-first scheduling)
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) N
        • 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] 작업 스케줄링 문제
상단으로

티스토리툴바