[Algorithm] Scheduling

Scheduling은 Greedy Algorithm의 대표적인 활용 알고리즘이다
해당 알고리즘의 목표를 통해서 Greedy의 설계방법을 알수있다.
 
1. 스케줄짜기(Scheduling)

기다리는 시간을 최소화하는 것이 목표인 알고리즘이다.
여기서는 시스템 내부 시간 (The time in the system)을 기준으로 측정을 하는데
시스템 내부 시간은 기다리고 수행하는 시간을 합친시간이다.
 
즉, Scheduling의 목표는  최적의 순서를 찾아 시스템 내부 시간 을 줄이는것이다.
예시를 통해서 간단하게 알아보겠다.
 
예시 효율적인 과제하기
과제를 효율적으로 하고자한다.
한번 과제를 시작하면 중간에 다른 과제를 할 수 없다고 한다면
어떤 순서로 해야 효율적일까?
 

과제이름	걸리는시간
취창업 실무	3시간
컴퓨터 알고리즘	5시간
인공지능 캡스톤	2시간

 
시스템 내부시간을 줄이기위해서 일단 계산을 해보면 
짧은 과제부터 하는것이 제일 효율적인 것을 알 수 있다.
인>취>컴 -> 2 + (2+3) + (2+3+5) = 17
인>컴>취 -> 2 + (2+5) + (2+5+3) = 19
취>인>컴 -> 3 + (3+2) + (3+2+5) = 18
취>컴>인 -> 3 + (3+5) + (3+5+2) = 21
컴>인>취 -> 5+ (5+2) + (5+2+3) = 22
컴>취>인 -> 5 + (5+3) + (5+3+2) = 23
 
 짧은 과제로 하는 것을 기준으로 삼아서 코드를 짜면 다음과 같다 링크

# 과제 종류와 걸리는 시간
assignments = {
    '취창업 실무 과제': 3,
    '컴퓨터 알고리즘 과제': 5,
    '인공지능 캡스톤 과제': 2
}

# 걸리는 시간이 짧은 순서로 정렬
sorted_assignments = sorted(assignments.items(), key=lambda x: x[1])

# 가장 효율적인 순서와 소요 시간 계산
play_time = 0
system_time=0
optimal_order = []
for assignment, time in sorted_assignments:
    optimal_order.append(assignment)
    system_time+= play_time
    play_time += time
    
    
total_time = system_time+play_time
    
print("가장 효율적인 순서:", optimal_order)
print("소요 시간:", total_time, "시간")

이렇게 간단하게 Greedy Algorithm으로 해결이 가능하지만
진짜 적절한지 검증이 필요하다.
 
코드를 살짝 때서 가져오면 이렇게 구분하면된다.

for assignment, time in sorted_assignments:  #선택절차
    optimal_order.append(assignment)         #적절성 점검
    system_time+= play_time
    play_time += time
                                            
total_time = system_time+play_time
    
print("가장 효율적인 순서:", optimal_order) #해답점검
print("소요 시간:", total_time, "시간")

sort된 것을 가져오고(선택절차) 적절하게 넣었는지 확인한다(적절성검사)
그리고 마지막으로 프린트되는 값들을 점검하여 올바른지 확인한다 (해답점검)
 
시간복잡도
이렇게 간단하게 짠 알고리즘에도 시간복잡도가 존재한다
바로  정렬을 하였기 때문에 O(nlogn)의 복잡도가 존재한다.
 
 
2. 마감시간이 있는 스케줄 짜기(scheduling with deadlines)
만약 마감시간이 존재하는 경우의 예시를 들어보자.
만약 과제 제출 기한이 있다고 가정하고
현재 시간 : 12시, 과제하는 데 걸리는 시간 : 1시간이다.
 

과제 이름	마감시간	보상
취창업 실무	2시	B (3.0)
컴퓨터 알고리즘	1시	A+ (4.5)
인공지능 캡스톤	2시	B+ (3.5)
빅데이터 활용	1시	A (4.0)

 
마감 시간 이내에 과제를 제출한다면 보상(학점)을 받을 수있을때
 어떤 순서로 해야 제일 보상이 높을까?
 
 모든 경우의 수를 보았을때
컴>인 -> (4.5+3.5) -> 4.0
컴>취 -> (4.5+3.0) -> 3.75
빅>취 -> (4.0+3.0) -> 3.5
빅>인 -> (4.0+3.5) -> 3.75
인>취 -> (3.5+3.0) -> 3.25
취>인 -> (3.0+3.5) -> 3.25
해당 알고리즘은 모든 경우의 수를 따진후에 최선의 선택을 하면되는 알고리즘을 만들면 된다.
우선 적절한 순서만 모아서 집합을 시킨후에 최고의 값을 선택하고 끝낸다
 
해당 코드는 아래와 같다 링크

# 과제 종류, 걸리는 시간, 마감 시간, 학점
assignments = [
    ('취창업 실무 과제', 1, 14, 3.0),
    ('컴퓨터 알고리즘 과제', 1, 13, 4.5),
    ('인공지능 캡스톤 과제', 1, 14, 3.5),
    ('빅데이터 활용 과제', 1, 13, 4.0)
]

# 현재 시간
current_time = 12

# 모든 가능한 조합 생성
total_list = []
for assignment1 in assignments:
    for assignment2 in assignments:
        if current_time + assignment1[1] <= assignment1[2] and current_time + assignment1[1] + assignment2[1] <= assignment2[2]: #적합한 집합만 추가
            total_list.append((assignment1[0], assignment2[0], (assignment1[3] + assignment2[3])/2))

# 학점 총 보상이 가장 높은 조합 찾기
max_reward = max(combination[2] for combination in total_list)
optimal_combination = [combination for combination in total_list if combination[2] == max_reward]


print("가장 효율적인 과목 순서:", optimal_combination)
print("학점 총 보상:", max_reward)

 
적절한 조합만 추가를하고 총 보상이 가장 높은 조합을 찾기만 하면된다.
시간복잡도는 for문을 두개사용하였기 때문에
O(n²)이다

 

관련된 포스팅

[Algorithm] Greedy

[Algorithm] 최소 신장 트리(MST), Kruskal & Prim algorithm

[Algorithm] 다익스트라 알고리즘(Dijkstra Algorithm)

[Algorithm] 허프만 코드

[Algorithm] Greedy Code 모음