알고리즘 #5_ 동적 프로그래밍: Assembly Line Scheduling

안녕하세요.

이번 포스팅에서는 동적 프로그래밍(Dynamic Programming)의 예제인 Assembly Line Scheduling과 Matrix-chain Multiplication에 대해서 알아보도록 하겠습니다. 동적 프로그래밍과 막대자르기(Rod-Cutting)예제에 대한 내용은 지난포스트를 확인해주시길 바랍니다.

---

1. Assembly Line Scheduling

먼저 Assembly Line Scheduling 예제에 대한 설명을 하겠습니다.

위와 같은 사진을 참고하여 어느 특정 공장에 두 개의 라인이 있습니다.

그림에서는 위의 라인이 S1, 아래의 라인이 S2입니다.

그리고 각각의 라인에서 진행되는 1부터 n까지의 공정이 있습니다.

이때 같은 열에 있는 공정은 같은 공정이지만 라인에 따른 시간차이가 있습니다.

또한, 위 또는 아래의 라인에서 다른 라인으로 넘어 가는데 소요되는 시간 t가 존재합니다.

이때, 같은 라인에서 넘어가는 시간은 0이라고 가정합니다.

즉, S1,1에서 S2,2로 넘어가는 시간은 t1,2 입니다. 또한 S1,1에서 S1,2로 넘어가는 시간은 0입니다.

각각의 기호에 대한 개념을 정리하면 아래와 같습니다.

 : i라인에서의 j번쨰 공정(j-th station on line i)

 : 에서 공정에 소요되는 시간(assembly time required at station )

 : i 라인으로 들어가는데 소요되는 시간(time to enter line i)

 : i 라인에서 나오는데 소요되는 시간(time to exit line i)

 : j 번째 공정을 하고 i 라인에서 다른 라인으로 교체되는 시간(time to transfer from line i after station j)

예들 들어 보겠습니다.

먼저, 위의 라인으로 들어가는 시간 e1은 0.5초, 아래의 라인으로 들어가는 시간 e2는 1초로 가정합니다.

그리고 위의 라인에서 진행되는 첫번째 공정은 S1,1로 표현하며 여기서 진행되는 공정 a1,1는 1초가 걸린다고 가정하겠습니다.

그리고 아래의 라인에서 진행되는 첫번째 공정은 S2,1로 표현하며 여기서 진행되는 공정 a2,1는 2초가 걸린다고 가정하겠습니다.

같은 방식으로 a1,2는 4초, a2,2는 3초가 걸린다고 가정하겠습니다. 또한 t1,2는 0.5초이며 t2,2는 3초라고 가정하겠습니다.

정리해보면 아래와 같습니다.

e1 = 0.5s

e2 = 1s

a1,1 = 1s

a2,1 = 2s

a1,2 = 4s

a2,2 = 3s

t1,2 = 0.5s

t2,2 = 3s

위와 같은 조건이 있을때 두번째 공정까지 진행하는 최단시간과 그 과정은 어떻게 될까요?

이러한 문제를 해결하는 것이, Assembly Line Scheduling 입니다.

위의 예제를 하나씩 확인해보겠습니다.

먼저 첫번째 공정을 마무리하는 시점을 생각해보면 S1,1 는 e1+a1,1 = 1.5s 이며 S2,1는 e2+a2,1 = 3s 입니다.

그리고 두번째 공정에 대해서 생각해보겠습니다.

만약 S1,2에서 공정을 진행한다고 가정하면, e1+a1,1+a1,2 = 5.5s 또는 e2+a2,1+t2,2+a1,2 = 10s 입니다.

그리고 S2,2에서 공정을 진행한다고 가정하면, e1+a1,1+t1,2+a2,2 = 5s 또는 e2+a2,1+a2,2 = 6s 입니다.

가장 최단시간이 걸리는 것은 5초의 과정을 가진 e1 + a1,1 + t1,2 + a2,2 입니다.

2. Brute-force

Assembly Line Scheduling에 대한 알고리즘을 고민해봅시다.

최적의 답을 찾기 위해서 전체의 경우의 수를 고려해보면 어떨까요?

n개의 공정이 존재할 때, 2개의 라인이 존재하므로 총 개의 경우의 수를 고려해야 합니다.

쉽게 말해서, S1,4의 공정을 수행하는데 오는 경로는 S1,3과 S2,3이 있는 것을 통해 특정 위치의 공정을 위한 경로를 확인하면 2개씩 존재하고, 공정의 개수는 총 n개이므로 총 개를 확인해야 하는 것 입니다.

즉, 이러한 모든 경우의 수를 탐색하는 Brute-force Approach로는 다음과 같은 시간복잡도를 가집니다.

In Brute-force Approach, 

이러한 Brute-force 방식은 상당히 많은 소요시간을 가지는 것을 지난 막대자르기 예제에서 확인 할 수 있었습니다.

뒤에서 수도코드를 확인하면서 설명드리겠지만,

동적 프로그래밍을 통해 해당 Assembly Line Scheduling 문제를 선형시간에 탐색할 수 있습니다.

따라서 동적 프로그래밍으로 알고리즘을 구현해보도록 합니다.

3. 동적 프로그래밍에 의한 Assembly Line Scheduling 해결

지난 포스팅에서 이야기 했던 것 처럼, 동적 프로그래밍의 기본 핵심은 테이블을 사용하는 것 입니다.

따라서 우리는 모든 경우에 수에 대해 탐색하는 것이 아니라, 탐색한 경우에 대해서는 테이블에 저장하여 필요할 때 값을 참조하도록 합니다.

위의 사진에 나와있듯이, 사용하는 테이블 의 의미는, i라인에서 진행하는 j 공정(=Si,j)을 시작지점으로 했을 때 가장 빠른 시간입니다.

즉 우리는 다룬 위의 예제에서는 2개의 라인을 이용하므로 f1과 f2가 테이블로 존재할 것입니다.

그리고 f*는 최종적으로 가장 빠른 시간을 저장하는 변수 입니다.

이때 f*는 다음과 같은 식으로 결정 됩니다.

그리고 각각의 테이블을 구성하는 방법은 다음과 같습니다.

또한 이후 수도코드에서 보게될 L테이블이 있습니다.

이는 최종적으로 Assembly Line Scheduling의 과정을 보여주기 위한 테이블입니다.

즉, l1[3]에 입력되는 값은, S1,3에 오는데 어떠한 라인에서 오는 것이 최적인지를 구분한 라인의 번호입니다.

이를 통해 최종적으로 구성되는 수도코드는 아래와 같습니다.

위의 수도코드를 확인해보면,

f1[1]과 f2[1]에 enter하는데 필요한 소요시간과 1번 공정을 하는데 소요되는 시간을 더해서 입력합니다.

이후, 2번 공정부터 n번째 공정까지 f1과 f2의 테이블에 적절한 값을 입력할 수 있도록 if문을 통한 처리를 진행합니다.

내부에서는 추가적인 반복문 없이 진행됩니다.

그리고 최종적으로 n번째 공정까지 마무리가 되면 라인에서 빠져나오는 시간을 고려하여 가장 소요시간이 적은 값을 f*에 저장합니다.

이를 통해서 해당 수도코드의 시간 복잡도는 선형시간을 가진다는 것을 알 수 있습니다.

 

또한 최종 과정을 보기위한 출력함수는 아래와 같습니다.

위의 수도코드들을 통해 아래 사진을 보고 그 과정을 하나씩 확인해보시면 이해가 빠를 것 입니다.

---

이렇게 해서 동적 프로그래밍, 동적 계획법의 두번째 예제인 Assembly Line Scheduling에 대해서 알아보았습니다.

다음 포스팅에서는 동적 프로그래밍의 세번째 예제인 Matrix-chain Multiplication에 대해서 알아보도록 하겠습니다.