조선 조립블록 지번할당 알고리즘 개발

조선 조립블록 지번할당 알고리즘 개발
박창규 ⋅ 서준용
울산대학교 경영대학
김지온 ⋅ 이상협 ⋅ 백태현 ⋅ 민상규
현대중공업 산업기술연구소 자동화연구실

초록
조선 현장의 블록 적치장에서 어떻게 하면 조립블록을 효율적으로 관리할 수 있을까 하는 것은 중요한 경영상의 난제이다.
본 연구는 세계 최대의 선박건조업체이며, 한국상선건조산업 분야에서 리더로서의 역할을 수행하고 있는 현대중공업에서 수행한 프로젝트를 바탕으로 조선 조립블록의 지번할당문제를 정의하고 조립블록 지번할당을 위한 알고리즘을 개발한다.
그리고 여러 상황에서 모의실험을 실시하여 본 연구에서 개발한 조립블록 지번할당 알고리즘의 유용성을 검증한다.

 

1. 서론
본 연구에서는 비생산적인 조립블록 운반회수를 감소시키는 체계적인 알고리즘을 개발하기 위해 조선 현장에서의 조립블록 지번할당문제를 정의한다.
먼저, <그림 1>은 크기가 m*n (세로*가로, m≤n)인 블록 적치장에 대한 개략적인 도식을 보여준다.
블록 적치장을 운영하는 과정에서 조립블록이동이 발생하는 경우는 크게 세가지로 생각할 수 있다.
하나는 새로이 도착한 조립블록을 블록 적치장에 저장하는 경우이고,다른 하나는 만기된 조립블록을 블록적치장으로부터 반출하는 경우이다.

그리고 나머지 하나는 만기된 조립블록을 반출할 이동경로 상에 있는 방해블록들을 다른 빈 지번으로 옮기는 경우이다.
조립블록은 중후 장대하기 때문에 어떠한 블록운반작업에도 비용이 많이 든다. 심지어 조립블록을 바로 다음 지번으로 이동하거나, 제 자리에서 방향을 조금 수정하는, 사소한 작업처럼 보이는 경우에도 비용이 많이 든다.
따라서 블록 적치장을 운영하는 관리자의 입장에서는  블록위치를 신중히 결정하여 블록이동회수를 최소화하는 것이 대단히 중요하다.
조선 현장에서의 조립블록 지번할당문제는 방해블록 이동회수가 최소가 되도록 도착하는 조립블록들을 블록 적치장의 빈 지번들에 배정하고, 방해블록들을 다른 빈 지번들에 재배정하고, 그리고 만기된 조립블록들을 블록 적치장으로부터 반출하는 것이다.

2. 조립블록 지번할당 알고리즘
블록 적치장 운영 생산성을 향상하기 위해 개발한 조립블록 지번할당 알고리즘은 다음과 같은 2개의 하위-알고리즘들로 구성되어 있다: 방해블록선정과 지번결정. 방해블록선정 하위-알고리즘은 조립블록을 반출하기 위해 어떤 블록들을 블록 적치장의 다른 빈
지번들로 옮겨야 하는지를 결정한다. 그리고 지번결정 하위-알고리즘은 새로이 도착한 블록들과 방해블록들에게 빈 지번들을 배정한다. 각 하위-알고리즘을 예제를 이용하여 설명하기로 한다.

2.1 방해블록선정 하위-알고리즘
블록 적치장에서 만기된 조립블록을 반출할 때 방해블록들이 존재할 수 있다. 방해블록선정 하위-알고리즘은 만기된 조립블록의 반출 이동거리를 최소로 하고, 또한 발생할 방해블록들의 개수를 최소로 하는 반출경로를 선정함으로써 다른 빈 지번들로 이동해야 할 방해블록들을 결정한다

<그림 2>는 방해블록선정 하위-알고리즘과 지번결정 하위-알고리즘의 모든 단계를 요약하여 보여준다. 우선, <그림 2.a>는 만기된 조립블록들을 반출하기 위해 다른 빈 지번들로 이동해야 할 방해블록들을 어떻게 결정 하는지를 보여주고 있다.
지번 안에 있는 숫자는 언제 조립블록이 반출되어야 하는지를 나타낸다. 현재 단위 시각이 5 라고 가정하면, 음영 처리된 지번에 있는 2 개의 조립블록들이 반출되어야 한다.
첫 번째 열에 있는 만기된 조립블록은 반출하는데 전혀 방해물이 없다. 화살표는 조립블록의 이동방향을 나타낸다. 하지만 세 번째 열에 있는 만기된 조립블록은 반출하는데 방해블록들이 있다 (즉, 점선으로 된 원으로 표시된 블록들).
<그림 2.a>에서4 방향 모두를 살펴보면, 화살표로 표시된 방향으로 만기된 조립블록을 반출하여야  이동거리와 방해블록개수를 최소로 줄일 수 있다.
따라서 화살표로 표시된 방향에 있는 조립블록이 다른 빈 지번으로 이동해야 할 방해블록으로 선정된다.

2.2 지번결정 하위-알고리즘
지번결정 하위-알고리즘은 두 가지 경우에 사용된다. 한 가지는 블록 적치장에 새로운 조립블록이 도착한 경우이고, 다른 한 가지는 블록 적치장으로부터 만기된 조립블록을 반출시키는 경로에 방해블록이 존재하는 경우이다.
새로이 도착한 조립블록이나 방해블록에게 빈 지번을 할당하기 위해 지번결정 하위-알고리즘은 다음과 같은 단계를 따른다.

단계 1: 접근 가능한 후보위치 탐색

후보위치를 찾기 위해 본 단계는 동서남북 4 방향에서 모든 접근 가능한 후보위치를 탐색한다. 먼저, 넓이 = 2 에서 n-1 까지의 구간에 대해, 북쪽에서 남쪽 방향으로 그리고 남쪽에서 북쪽 방향으로 번갈아 가며 접근가능한 후보위치를 탐색한다.
다음으로, 깊이= 1 에서 m 까지의 구간에 대해, 서쪽에서 동쪽 방향으로 그리고 동쪽에서 서쪽 방향으로 번갈아 가며 접근 가능한 후보위치를 탐색한다.
접근 가능한 후보위치는 탐색방향에서 처음 만나는 이미 조립블록으로 채워져 있는 지번 바로 앞에 위치한 빈 지번이다. <그림 2.b>는 원으로 표시된 방해블록을 다른 빈 지번으로 이동시키기 위한 본 단계를 보여준다. 음영 처리된 빈 지번들이 접근 가능한 후보위치들이다.

단계 2: 방해 후보위치 제거

본 단계는 단계 1 에서 탐색된 접근 가능한 후보위치들 중에서 고려 중인 조립블록이 저장되면 인접 지번에 저장 중인 다른 조립블록이 이동하는데 방해를 유발하는 후보위치를 제거한다.
<그림 2.c>는 방해 후보위치를 X 로 표시하였다. 만약 원으로 표시된 방해블록이 X 로 표시된 지번으로 이동된다면, 바로 오른쪽 지번에 저장 중인 조립블록은 이동통로가 막혀 버린다.
즉, 이동통로가 막힌 조립블록은 단위 시각 6 에 블록 적치장으로부터 나가야 하는데 방해블록은 단위 시각 7 에 반출되는 것으로 되어 있다.

단계 3: 최선의 후보위치 선정

마지막 단계는 이동거리를 최소로 하는 최선의 후보위치를 선정하는 것이다. <그림 2.d>는 원으로 표시된 방해블록을 이동시킬 최선의 후보위치는 바로 오른쪽 지번임을 보여준다.
화살표는 블록들의 이동방향을 나타낸다.

 

3. 모의실험
본 연구에서 개발한 조립블록 지번할당 알고리즘의 유용성을 검토하기 위해 다양한 상황을 설정하여 컴퓨터 모의실험을 수행하였다.
조선 현장의 블록 적치장 운영상에는 필수블록운반과 방해블록운반과 같이 두 가지 유형의 블록이동이 발생한다.
필수블록운반은 블록 적치장에 조립블록을 저장하고 반출하는 생산적 활동인 반면, 방해블록운반은 필수블록운반이 수행되도록 이동경로를 제공하기 위해 방해블록들을 다른 빈 지번들로 이동시키는 비생산적 활동이다.
블록 적치장 운영 생산성을 향상시키기 위해서는 방해블록운반회수를 최대한 줄여야 한다. 본 연구는 성과척도로 O/N 비율을 다음과 같이 정의하여 사용한다.

O/N 비율 = 방해블록운반회수 /
              필수블록운반회수

여기서 O/N 비율의 값이 적으면 적을수록 블록 적치장 운영 생산성이 높다는 것을 의미한다. 본 연구는 다양한 크기의 블록 적치장에 대해 컴퓨터 모의실험을 수행하였다.
그러나 본 장에서는 현대중공업에서 대표적 크기인 5*10, 5*15, 5*20과 같이 3개의 블록 적치장에 대한 모의실험 결과만을 보여준다.
다른 크기의 블록 적치장에 대해 수행한 모의실험에서도 비슷한 결과를 보였다.
모의실험에서 블록 적치장의 최대 부하율 60, 70, 80, 90, 그리고 100%와 같이 다양하게 고려되었다. 모든 모의실험은 100 단위 기간동안 수행되었고,
O/N 비율은 대략 50 단위 시각부터 안정된 상태를 나타냈다.

조립블록 지번할당 알고리즘의 유용성을 검토하기 위해 3종류의 실험상황을 설정하여 모의실험을 실시하였다.
실험상황 1에서는 주어진 모의실험 기간동안 각 단위 기간에 대해 시뮬레이터가 우선적으로 만기된 모든 조립블록들을 블록 적치장으로부터 반출하였다.
그러고 난 후, 새로이 도착한 조립블록들을 무작위 순서로 블록 적치장에 저장하였다.
여기서 방해블록 및 새로이 도착한 조립블록에 대한 지번은 무작위로 할당하였다. 실험상황 2는 실험상황 1과 비슷하나, 실험상황 2에서는 방해블록 및 새로이 도착한 조립블록들에 대한 지번를 할당하기 위해 본 연구에서 개발한 조립블록 지번할당 알고리즘을 이용하였다. 실험상황 3은 블록 적치장에 블록들을 저장하는 순서를 조립블록들이 블록 적치장에 머무를 기간의 내림차순을 따르게 했다는 것을 제외하고는 실험상황 2와 같다.

즉, 실험상황 3은 블록 적치장에 오래 머무를 조립블록을 우선적으로 블록 적치장에 저장하였다.
<그림 3>은 3종류의 실험상황에 대한 모의실험 결과를 보여준다. 일반적으로 블록 적치장에 조립블록의 부하가 증가함에 따라 O/N 비율이 증가함을 보이는데 이는 자연스런 결과라고 사료된다.
그리고 블록 적치장의 크기와 최대 부하율을 고려한 모든 경우에 대해 실험상황 2가 실험상황 1보다 더 좋은 성과를 보여주고 있다.

이것은 본 연구에서 개발한 조립블록 지번할당 알고리즘을 이용한 블록 적치장 운영이 무작위 배정방법을 이용한 블록 적치장 운영보다 방해블록운반회수를 덜 발생시킨다는 것을 의미한다.
추가적으로 살펴보면, 실험상황 3이 실험상황 2보다 더 좋은 성과를 보여주고 있다. 이것은 블록운반 순서를 결정하는 규칙도 블록 적치장 운영 생산성에 영향을 주는 것으로 해석할 수 있다.

4. 결론
블록 적치장 운영 생산성의 향상에 기여하기 위해 본 연구는 조립블록 지번할당문제를 명확히 정의하고 조립블록 지번할당 알고리즘을 개발하였다.
그리고 개발한 알고리즘의 유용성을 컴퓨터 모의실험을 통해 검증하였다.

출처 : 테크노경영연구정보센터 원문보기

---