TIL - 0117

Posted on | In | 0 comments

문인철 교수님의 ‘데이터 구조 및 분석: Linear Structure and Dynamic Programming’ 수업

Process of Assembly Line Schedule in Recursion

Assembly Line Scheduling

  • 200117
  • DP 를 이용한 예제
  • 어느쪽 라인으로 보낼때 상품이 더 빨리 나오는지?

결과

200117

  • Line 1 에서 최소 시간 38초가 걸림
  • 38초 걸리게 하기 위해서 어떻게 station 을 따라가야하는지는 오른쪽 테이블을참고해야함

Recursion 방법 코드

# Process of Assembly Line Scheduling 
class AssebmlyLinesInRecursion:
    time_station = [[7,9,3,4,8,4],
                    [8,5,6,4,5,7]]
    time_belt = [[2,2,3,1,3,4,3],
                    [4,2,1,2,2,1,2]]
    count = 0
    def scheduling(self, idx_line, idx_station):
        print(f'calculate scheduling: line - {idx_line}',
                f'station - {idx_station}, count - {self.count}')
        self.count += 1
        
        # excape loop         
        if idx_station == 0:
            if idx_line == 1:
                return self.time_belt[0][0] + self.time_station[0][0]
            elif idx_line == 2:
                return self.time_belt[1][0] + self.time_station[1][0]
        
        # recursion         
        if idx_line == 1:
            cost_line1 = self.scheduling(1, idx_station-1) + self.time_station[0][idx_station]
            cost_line2 = self.scheduling(2, idx_station-1) + self.time_station[0][idx_station] + self.time_belt[1][idx_station]
            
        elif idx_line == 2:
            cost_line1 = self.scheduling(1, idx_station-1) + self.time_station[1][idx_station] + self.time_belt[0][idx_station]
            cost_line2 = self.scheduling(2, idx_station-1) + self.time_station[1][idx_station] 
        
        if cost_line1 > cost_line2:
            return cost_line2
        else: 
            return cost_line1
    
    def start_scheduling(self):
        num_station = len(self.time_station[0])
        
        # 마지막 time_belt 는 따로 더해줌
        cost_line1 = self.scheduling(1, num_station-1) + self.time_belt[0][num_station]
        cost_line2 = self.scheduling(2, num_station-1) + self.time_belt[1][num_station]
        
        if cost_line1 > cost_line2:
            return cost_line2
        
        else:
            return cost_line1

코드 결과

lines = AssebmlyLinesInRecursion()
time = lines.start_scheduling()
print(time)

calculate scheduling: line - 1 station - 5, count - 0
calculate scheduling: line - 1 station - 4, count - 1
calculate scheduling: line - 1 station - 3, count - 2
calculate scheduling: line - 1 station - 2, count - 3
calculate scheduling: line - 1 station - 1, count - 4
calculate scheduling: line - 1 station - 0, count - 5
calculate scheduling: line - 2 station - 0, count - 6
calculate scheduling: line - 2 station - 1, count - 7
calculate scheduling: line - 1 station - 0, count - 8
calculate scheduling: line - 2 station - 0, count - 9
calculate scheduling: line - 2 station - 2, count - 10
calculate scheduling: line - 1 station - 1, count - 11
calculate scheduling: line - 1 station - 0, count - 12
calculate scheduling: line - 2 station - 0, count - 13
calculate scheduling: line - 2 station - 1, count - 14
calculate scheduling: line - 1 station - 0, count - 15
calculate scheduling: line - 2 station - 0, count - 16
calculate scheduling: line - 2 station - 3, count - 17
calculate scheduling: line - 1 station - 2, count - 18
calculate scheduling: line - 1 station - 1, count - 19
calculate scheduling: line - 1 station - 0, count - 20
calculate scheduling: line - 2 station - 0, count - 21
calculate scheduling: line - 2 station - 1, count - 22
calculate scheduling: line - 1 station - 0, count - 23
calculate scheduling: line - 2 station - 0, count - 24
calculate scheduling: line - 2 station - 2, count - 25
calculate scheduling: line - 1 station - 1, count - 26
calculate scheduling: line - 1 station - 0, count - 27
calculate scheduling: line - 2 station - 0, count - 28
calculate scheduling: line - 2 station - 1, count - 29
calculate scheduling: line - 1 station - 0, count - 30
calculate scheduling: line - 2 station - 0, count - 31
calculate scheduling: line - 2 station - 4, count - 32
calculate scheduling: line - 1 station - 3, count - 33
calculate scheduling: line - 1 station - 2, count - 34
calculate scheduling: line - 1 station - 1, count - 35
calculate scheduling: line - 1 station - 0, count - 36
calculate scheduling: line - 2 station - 0, count - 37
calculate scheduling: line - 2 station - 1, count - 38
calculate scheduling: line - 1 station - 0, count - 39
calculate scheduling: line - 2 station - 0, count - 40
calculate scheduling: line - 2 station - 2, count - 41
calculate scheduling: line - 1 station - 1, count - 42
calculate scheduling: line - 1 station - 0, count - 43
calculate scheduling: line - 2 station - 0, count - 44
calculate scheduling: line - 2 station - 1, count - 45
calculate scheduling: line - 1 station - 0, count - 46
calculate scheduling: line - 2 station - 0, count - 47
calculate scheduling: line - 2 station - 3, count - 48
calculate scheduling: line - 1 station - 2, count - 49
calculate scheduling: line - 1 station - 1, count - 50
calculate scheduling: line - 1 station - 0, count - 51
calculate scheduling: line - 2 station - 0, count - 52
calculate scheduling: line - 2 station - 1, count - 53
calculate scheduling: line - 1 station - 0, count - 54
calculate scheduling: line - 2 station - 0, count - 55
calculate scheduling: line - 2 station - 2, count - 56
calculate scheduling: line - 1 station - 1, count - 57
calculate scheduling: line - 1 station - 0, count - 58
calculate scheduling: line - 2 station - 0, count - 59
calculate scheduling: line - 2 station - 1, count - 60
calculate scheduling: line - 1 station - 0, count - 61
calculate scheduling: line - 2 station - 0, count - 62
calculate scheduling: line - 2 station - 5, count - 63
calculate scheduling: line - 1 station - 4, count - 64
calculate scheduling: line - 1 station - 3, count - 65
calculate scheduling: line - 1 station - 2, count - 66
calculate scheduling: line - 1 station - 1, count - 67
calculate scheduling: line - 1 station - 0, count - 68
calculate scheduling: line - 2 station - 0, count - 69
calculate scheduling: line - 2 station - 1, count - 70
calculate scheduling: line - 1 station - 0, count - 71
calculate scheduling: line - 2 station - 0, count - 72
calculate scheduling: line - 2 station - 2, count - 73
calculate scheduling: line - 1 station - 1, count - 74
calculate scheduling: line - 1 station - 0, count - 75
calculate scheduling: line - 2 station - 0, count - 76
calculate scheduling: line - 2 station - 1, count - 77
calculate scheduling: line - 1 station - 0, count - 78
calculate scheduling: line - 2 station - 0, count - 79
calculate scheduling: line - 2 station - 3, count - 80
calculate scheduling: line - 1 station - 2, count - 81
calculate scheduling: line - 1 station - 1, count - 82
calculate scheduling: line - 1 station - 0, count - 83
calculate scheduling: line - 2 station - 0, count - 84
calculate scheduling: line - 2 station - 1, count - 85
calculate scheduling: line - 1 station - 0, count - 86
calculate scheduling: line - 2 station - 0, count - 87
calculate scheduling: line - 2 station - 2, count - 88
calculate scheduling: line - 1 station - 1, count - 89
calculate scheduling: line - 1 station - 0, count - 90
calculate scheduling: line - 2 station - 0, count - 91
calculate scheduling: line - 2 station - 1, count - 92
calculate scheduling: line - 1 station - 0, count - 93
calculate scheduling: line - 2 station - 0, count - 94
calculate scheduling: line - 2 station - 4, count - 95
calculate scheduling: line - 1 station - 3, count - 96
calculate scheduling: line - 1 station - 2, count - 97
calculate scheduling: line - 1 station - 1, count - 98
calculate scheduling: line - 1 station - 0, count - 99
calculate scheduling: line - 2 station - 0, count - 100
calculate scheduling: line - 2 station - 1, count - 101
calculate scheduling: line - 1 station - 0, count - 102
calculate scheduling: line - 2 station - 0, count - 103
calculate scheduling: line - 2 station - 2, count - 104
calculate scheduling: line - 1 station - 1, count - 105
calculate scheduling: line - 1 station - 0, count - 106
calculate scheduling: line - 2 station - 0, count - 107
calculate scheduling: line - 2 station - 1, count - 108
calculate scheduling: line - 1 station - 0, count - 109
calculate scheduling: line - 2 station - 0, count - 110
calculate scheduling: line - 2 station - 3, count - 111
calculate scheduling: line - 1 station - 2, count - 112
calculate scheduling: line - 1 station - 1, count - 113
calculate scheduling: line - 1 station - 0, count - 114
calculate scheduling: line - 2 station - 0, count - 115
calculate scheduling: line - 2 station - 1, count - 116
calculate scheduling: line - 1 station - 0, count - 117
calculate scheduling: line - 2 station - 0, count - 118
calculate scheduling: line - 2 station - 2, count - 119
calculate scheduling: line - 1 station - 1, count - 120
calculate scheduling: line - 1 station - 0, count - 121
calculate scheduling: line - 2 station - 0, count - 122
calculate scheduling: line - 2 station - 1, count - 123
calculate scheduling: line - 1 station - 0, count - 124
calculate scheduling: line - 2 station - 0, count - 125
38