알고리즘 분석 | 간격 스케줄링(Interval Scheduling) | Task Scheduling

이전 포스팅

이전 그리디 알고리즘 내용을 보고 오시면 이해가 쉽습니다.

2023.03.27 - [알고리즘 분석 및 데이터 구조] - 알고리즘 분석 | Greedy 알고리즘 쉽게 이해하기 | Fractional Knapsack Problem(분수 배낭 문제)

알고리즘 분석 | Greedy 알고리즘 쉽게 이해하기 | Fractional Knapsack Problem(분수 배낭 문제)

---

간격 스케줄링 문제

간격 스케줄링 문제는 여러 작업(또는 회의실 사용 시간 요청 등)이 주어졌을 때, 이러한 작업들을 처리할 수 있는 단일 기계(또는 회의가 열릴 수 있는 단일 회의실 등)가 있다고 가정합니다.이 문제의 목표는 기계에서 스케줄할 수 있는 작업 수를 최대화하기 위해 작업들의 부분집합을 선택하는 것입니다.

간단한 예를 들면, 회의실이 하나 있는 회사에서 여러 팀이 회의실을 사용하려고 요청했다고 가정해봅시다. 회의실은 한 번에 하나의 회의만 수용할 수 있으므로, 가능한 많은 회의를 진행하기 위해 스케줄을 최적화해야 합니다

이 문제를 해결하기 위한 한 가지 대표적인방법은 그리디 알고리즘을 사용하는 것입니다. 그리디 알고리즘은 각 단계에서 최선의 선택을 하며 전체적인 최적해에 도달하는 것을 목표로 합니다. 간격 스케줄링 문제에 대한 그리디 알고리즘은 다음과 같이 작동합니다:

1.  작업들을 종료 시간에 따라 오름차순으로 정렬합니다. 이렇게 하면 가장 먼저 종료되는 작업부터 고려할 수 있습니다.
2.  가장 먼저 종료되는 작업을 선택하고 스케줄에 추가합니다.
3.  선택한 작업과 겹치는 다른 작업들을 제거합니다. 겹치는 작업은 동시에 진행할 수 없기 때문에 선택에서 제외됩니다.
4. 남은 작업들 중에서 다시 가장 먼저 종료되는 작업을 선택하고 스케줄에 추가합니다.
5. 위 과정을 반복하여 남은 작업들 중 겹치지 않는 작업을 찾아 스케줄에 추가합니다.
6. 더 이상 선택할 수 있는 작업이 없을 때까지 이 과정을 계속 반복합니다.

이러한 그리디 알고리즘을 사용하면 각 단계에서 최선의 선택을 하여 전체적으로 최대한 많은 작업을 스케줄에 추가할 수 있습니다. 이 알고리즘은 그리디 알고리즘이지만, 간격 스케줄링 문제의 경우 최적해를 찾을 수 있음이 증명되어 있습니다.

구현

public class IntervalScheduling {
    public static void intervalScheduling(int[] startTime, int[] endTime){
        int n = startTime.length;

        //Task 클라스 객체에 추가
        Task[] tasks = new Task[n];
        for(int i = 0; i<n; i++){
            tasks[i] = new Task(startTime[i], endTime[i]);
        }
        //오름차순으로 정렬
        Arrays.sort(tasks, new Comparator<Task>() {
            @Override
            public int compare(Task t1, Task t2) {
                return t1.endTime - t2.endTime;
            }
        });
        
       // 선택된 task를 저장할 리스트 생성
        List<Task> selectedTasks = new ArrayList<Task>();
        selectedTasks.add(tasks[0]);
        
	// 선택된 task와 충돌하지 않는 task 선택
        for(int i = 0; i<n; i++){
            Task currentTask = tasks[i];
            Task lastSelectedTask = selectedTasks.get(selectedTasks.size() - 1);
            if(currentTask.startTime >= lastSelectedTask.endTime){
                selectedTasks.add(currentTask);
            }
        }
        
    // 선택된 task 출력
        System.out.println("Selected tasks : ");
        for(Task task : selectedTasks){
            System.out.println(task);
        }
    }
    
    //Task class 정의
    static class Task{
        int startTime, endTime;

        public Task(int startTime, int endTime){
            this.startTime = startTime;
            this.endTime = endTime;
        }
        
        public String toString(){
            return "(" + startTime + "," + endTime + ")";
        }
    }
    
    //main 함수 실행
    public static void main(String[] args){
        int[] startTime = {0,0,6,0,9,7};
        int[] endTime = {5,3,10,10,10,12};
        intervalScheduling(startTime, endTime);
    }
}

---

 

Task Scheduling

Task Scheduling은 "Task Scheduling with Minimum Number of Machines" 문제라고도 하는데, Interval Scheduling 문제와 매우 유사합니다. 그러나 Interval Scheduling은 한 기계에서 실행 가능한 task만 선택할 수 있지만, 이 문제에서는 가능한 적은 수의 기계를 사용하여 모든 task를 실행해야합니다.

해결책으로는 Greedy 알고리즘을 사용할 수 있습니다:

1. 먼저, 모든 task를 종료 시간(end time)에 따라 오름차순으로 정렬합니다.
2. 이제 새로운 기계를 만들고, 첫 번째 task를 첫 번째 기계에 배치합니다.
3. 그 다음 task를 선택하고, 첫 번째 기계와 충돌하지 않으면 해당 task를 첫 번째 기계에 배치합니다. 그렇지 않으면, 새로운 기계를 만들고 해당 task를 새로운 기계에 배치합니다.
4. 모든 task를 선택할 때까지 위의 단계를 반복합니다.

이 알고리즘은 최적의 해를 제공하지는 않지만, 어느 정도 근사치를 제공합니다. 또한, 이 알고리즘의 시간 복잡도는 \(O(nlogn)\)입니다.

 

---