
[알고리즘] 동적 계획법 - Assembly Line Scheduling using Python
CS/알고리즘
2021. 5. 7. 15:43
위의 라인은 S1, 아래 라인이 S2이다. 각 라인은 1부터 n까지의 공정이 있고, 이는 Si, j로 나타낸다. Si, j의 소요 시간은 각각 ai, j이다. ei는 i번째 라인에 들어가는 데 소요되는 시간을 의미하고(ex. e1: line 1에 들어가는 데 소요되는 시간) xi는 i번째 라인에서 작업을 다 마치고 나오는 데 소요되는 시간을 의미한다. 마지막으로 ti, j는, j번째 공정까지 마친 뒤 i번째 라인에서 다른 라인으로 교체하는 데 소요되는 시간이다. f1[j]은, i번째 라인에서 진행하는 j 공정(Si, j)을 시작 지점으로 했을 때 가장 빠른 시간이다. 여기서 우리가 구해야 될 것은, f*, 즉 최종적으로 가장 빠른 시간을 저장하는 변수이다. 동적 계획법을 사용하여 접근하면 이 문제를 선형..