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

작업 스케줄링 문제

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

 

 

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++