Advanced
A Heuristic Algorithm for Block Storage Planning in Shipbuilding
A Heuristic Algorithm for Block Storage Planning in Shipbuilding
Journal of the Society of Naval Architects of Korea. 2014. Jun, 51(3): 239-245
Copyright © 2014, The Society of Naval Architects of Korea
This is an Open-Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License(http://creativecommons.org/licenses/by-nc/3.0) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : March 04, 2014
  • Accepted : April 04, 2014
  • Published : June 20, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Article
Author
Metrics
Cited by
TagCloud
About the Authors
정열, 손
흥원, 서
hwsuh@dsme.co.kr
병현, 하

Abstract
This paper deal with the block storage planning problem of storing and retrieving assembly blocks in a temporary storage yard with limited capacity, which is one of the critical managerial problems in shipbuilding. The block storage planning problem is required to minimize the number of relocations of blocks while the constraints for storage and retrieval time windows are satisfied. We first show NP-hardness of the block storage planning problem. Next we propose a heuristic algorithm to generate good quality solutions for larger instances in very short computational time. The proposed heuristic algorithm was validated by comparing the results with the mathematical model presented in the previous study.
Keywords
1. 서 론
과거 조선 산업은 선박의 크기와 중량의 제약 조건 때문에 고정위치 배치의 형태로 생산이 이루어졌다. 최근에는 Fig. 1 과 같이, 작업 가능한 크기의 조립 블록으로 분할하여, 중간 크기의 대형블록으로 조립하고, 최종적으로 거대한 선박을 건조하는 블록 분할 공법이 도입되었다. 이를 통해 선박의 크기와 중량의 제약 조건을 극복하게 되었고, 잡 숍(job shop)과 플로우 숍(flow shop)방식을 도입하여 생산성을 향상시키고 있다.
PPT Slide
Lager Image
Shipbuilding process flow
현재 조선 산업에서는 전통적인 선박뿐 아니라 다양한 해양구조물의 건조를 위하여 생산설비를 공유하며 다양한 블록들이 동시에 생산된다. 블록 분할 공법에 의하여 나누어진 블록은 선박의 종류와 선박 내의 위치에 따라 다양한 작업량과 난이도를 가지며, 이로 인해 생산 공정에서 선후 블록들 간의 생산시간의 편차가 발생한다. 또한 입고 지연, 생산 공정 차질, 기상 변화, 중간 품질 검사 등으로 일정이 빈번하게 변경된다. 이러한 이유로 공정 간 생산 동기화의 어려움을 극복하기 위하여 재공(work in process) 블록을 보유하게 된다.
재공 블록을 적치하기 위하여 과거에는 각 공정별 전용 적치장이 분산 운영되어 왔다. 하지만 최근 선박 건조량의 증가와 공정간 생산능력의 불균형으로 재공 블록 수가 증가하고 적치장 용량의 불균형이 커졌다. 이를 해소하기 위해 현재 대부분의 조선소에서는 적치장을 통합하여 운영하고 있다. 그에 따라 적치장 규모가 증가하게 되고, 다양한 형상과 중량, 일정을 가진 블록이 적치되어 결과적으로 운영의 복잡도가 높아지게 되었다.
적치장에서 출고 블록을 꺼내기 위해서는 이동 동선에 놓여 있는 간섭 블록을 옮기는 재취급 작업이 함께 수행된다. 높아진 운영 복잡도로 인해 간섭 블록의 수가 많아지고 재취급 작업도 함께 증가하게 되었다. 이는 적치장 운영 계획의 효율성을 저해하는 주요한 원인이 된다.
본 연구는 선박 건조 공정들 사이에서 블록의 적시공급과 이송 장비의 효율적인 운영을 위한 적치장 운영 계획을 다룬다. 이는 적치장 내 간섭 블록의 재취급 최소화를 목적으로 하며, 주어진 기간 제약을 만족하는 입출고 기간과 적치 위치를 결정한다. 조선소 내의 블록 물류는 적치장 운영 계획과 함께 이송장비 할당 계획을 바탕으로 실행된다.
지금까지 조선 산업에서의 블록 생산과 물류에 관한 많은 연구들이 수행되어 왔다 ( Park, et al., 1995 ). 유전자 알고리즘을 사용하여 조립 블록의 생산 계획 수립에 관한 연구가 있었으며 ( Koh, 1996 ), 통합 생산 계획을 체계화하기 위한 방법론 연구가 수행되었다 ( Lee, et al., 1997 ). 특히 공장 내에서 공간제약과 일정을 고려하여 공간 효율성을 극대화, 생산 시간을 최소화하기 위하여 블록위치를 결정하는 공간 일정 계획에 관한 많은 연구가 수행되어 왔다 ( Lee, et al., 1996 ; Park, et al., 1996 ; Koh, et al., 1999 ; Cho, et al., 2001 ). 하지만 공장 내에서는 크레인을 사용하여 블록을 취급하므로 입출고되는 방향에 대한 제약이 없으며, 블록의 설치와 작업의 효율성을 위하여 한 번 놓여진 블록은 작업이 완료되기 전까지 이동하지 않는다는 점에서 적치장 운영 계획 문제와 차별성을 가진다.
조선 산업의 블록운영에 영향을 미치는 요소들을 분석한 연구 ( Park & Seo, 2006 )을 시작으로 적치장에서 블록의 취급 방법과 적치 위치에 대한 연구가 진행되었다. 컨테이너와 같이 블록의 크기를 정형화하여 고정된 직사각형의 적치장을 직사각형 구역으로 구분하고, 블록을 하나의 구역에 배치하는 블록 입출고 계획 문제가 다루어졌다 ( Park & Seo, 2009 ; Park & Seo, 2010 ). 적치장 내 블록의 다양한 크기와 이동 방향의 자유도를 부여하여 재취급 횟수를 줄이는 연구가 진행되으나 ( Lee, et al., 2011 ), 높은 자유도로 인하여 터부 탐색(tabu search)을 사용한 근사해법이 제시되었다. 본 연구의 선행 연구로는 조선소의 블록 물류시스템을 설계하는 연구 ( Son & Cho, 2007 )에서 물류시스템을 구성하는 세부 문제를 정의하였다. 그 가운데 적치장 운영 문제를 네트워크 흐름을 기반으로 수리 계획 모형을 제시하고, 문제의 특성을 고려한 모형으로 변경하여 최적해의 도출시간을 줄이는 연구가 수행되었다 ( Ha, et al., 2013 ).
본 연구에서는 적치장 운영 방식을 모형화하여 최적화 문제를 도출해내고, 이 문제가 NP-hard임을 보인다. 그리고 문제의 복잡도를 감안하여 짧은 시간에 근사해를 도출하는 휴리스틱을 제안한다. 휴리스틱은 입출고 시간을 결정하는 단계와 입출고 위치를 결정하는 단계로 이루어진다. 수치실험을 통하여 이전 연구 ( Ha, et al., 2013 )의 정수 계획 모형과 성능을 비교한다.
본 연구의 구성은 다음과 같다. 2절은 적치장에서 블록을 적치하는 방법을 고찰하고 이를 최적화 문제로 모형화한다. 3절에서는 적치장 운영 계획 문제를 상세히 정의하고, 이 문제의 복잡도를 보인다. 4절에서 짧은 시간에 근사해를 도출하는 휴리스틱 알고리즘을 제안하고, 예제를 통하여 그 과정을 설명한다. 5절에서는 수치실험을 통하여 최적해를 도출하는 정수 계획 모형과 성능을 비교하고, 6절에서 결론을 제시한다.
2. 적치장 운영
선박을 건조하는 과정은 1절에 제시된 Fig. 1 과 같이 제품설계, 선각공정, 의장공정, 도장공정, 탑재공정, 안벽의장 공정을 거친다. 조립 블록이 이들 생산 공정 사이를 이동하면서 다양한 물류 문제가 발생한다. 각 공정은 Fig. 2 와 같이 동일한 기능을 수행하는 다수의 공장으로 분산되어 위치한다.
PPT Slide
Lager Image
Storage and retrieval process in temporary storage areas
선박과 해양 구조물은 그 종류에 따라 Fig. 1 의 공정들 사이의 작업량이 많은 차이를 보인다. 이들 작업량 차이로 인하여 공정 및 공장에서 블록의 생산시간 차이가 발생하게 된다. 선후행 공정의 생산 시간 차이로 인하여 이로 인하여 각 공장의 재공 블록수의 차이가 발생하여 공장별 전용 적치공간의 과부족 문제가 발생하게 되었다. 현재 조선소에서는 공장별 적치장 과부족 문제를 해소하기 위하여 분산되어 있는 다수의 전용 적치장을 Fig. 2 와 같이 통합 운영하여 공장별 적치공간의 과부족을 해결하였다.
생산 공정들 사이에서 블록을 공급하는 과정은 세부적으로 이송 대상 블록까지의 공차 이동, 적치장 내의 간섭 블록 제거를 위한 재취급 이동, 블록을 공장까지 공급하는 블록 이동 작업으로 이루어진다. 공차 이동과 재취급 이동시간이 과도하면, 물류비용의 증가와 입출고 작업 지연으로 이어져 공정의 생산 지연이 발생한다. 다양한 가변성과 불확실성이 존재하는 현장에서 재공품인 블록을 생산 공정에 적시 공급하는 것은 선박 건조 공정의 생산성에 많은 영향을 미친다. 따라서 효율적인 블록의 관리는 생산성 향상을 위한 중요한 문제이다.
공정간 작업부하의 불균형으로 후행 공정이 즉시 작업가능 상태가 아닐 경우에는 중간 재공 블록으로 구분되어 적치장에 일정 기간 적치되어야 하며, 이를 입고 요청이라 하며, 입고되는 블록을 입고 블록이라 부른다. 후행 공정에서 작업할 블록을 요청하면 선행 공정에서 공급하거나 적치장에서 공급하게 되며, 이때 적치장에서 공급하는 경우 출고 요청을 처리하게 된다. 출고되는 블록을 출고 블록이라 부른다.
입고 블록은 대상 공정에서의 블록 투입순서에 따라 이전 블록의 작업 시작시간과 완료시간 사이에 공급되어야 생산지연이 발생하지 않는다. 또한 임의의 공정에서 완료된 블록은 생산순서에 따라 이전 블록이 완료되기 전까지 출고되어야 생산지연을 막을 수 있다. 따라서 입출고 요청은 반드시 지켜야 하는 고유의 시간 제약을 가지고 있다. 입고 블록의 시간제약을 입고 가능 기간, 출고 블록의 시간제약을 출고 가능 기간이라 부른다.
전체 계획 기간은 단위 기간(period)으로 구분된다. 블록은 단위 기간 동안 입고, 출고, 재취급 되거나 적치된 위치에 그대로 있게 된다. 단위 기간 1부터 주어진 계획 기간까지 계획을 수립하며, 한 단위 기간 동안 적치장은 다음과 같은 작업 순서로 운영 된다:
  • i) 출고될 블록들과 함께 간섭 블록들을 적치장에서 꺼낸다.
  • ii) 입고될 블록들과 함께 꺼냈던 간섭 블록들을 적치장으로 넣는다.
적치장 내의 블록은 생산 계획에 따라 후행 공정에 입고되기 전까지 적치되어 잔여 적치기간을 고려하여 적치하는 것이 효율적이지만 빈번한 일정변경으로 미리 옮겨놓은 블록의 출고시점이 달라지면 추가적인 재취급이 발생될 수 있다. 따라서 본 연구는 입출고 블록에 의하여 발생되는 간섭 블록 이외는 블록을 먼저 재취급하지 않음을 가정한다.
크기와 모양이 다양한 블록은 안전과 이동 준비시간 절감을 위하여 전용 운반대(트레슬, 세일링 지그)에 올려져 블록운반 전용 중장비인 트랜스포터로 운반된다. 전용 운반대는 이동 상태에서 블록의 안정적인 지지를 위하여 충분한 폭과 길이를 유지하고 있어야 한다. 따라서 입출고를 위하여 블록의 이동통로와 회전 반경만큼의 여유 공간이 필요하며, 이는 블록 하나이상을 적치할 수 있는 행 또는 열만큼의 공간을 필요로 하기 때문에 적치공간이 부족한 조선소에서는 가능한 많은 블록을 적치하기 위하여 한 방향의 출입구로 블록을 적치하여 적치공간을 확보한다. 따라서 본 연구에서는 한 방향으로만 출입하는 것을 가정하였다.
과거에는 적치공간의 효율성을 위하여 Fig. 3(a) 와 같이 적치 하였으나, 현재는 (b)와 같이 행을 기준으로 적치하는 것이 일반적이다. 이는, 예를 들어 (a)에서 적치되어 있는 블록 A와 같이, 행의 경계에 걸쳐있는 경우 두 행 모두에 작업 간섭을 일으키기 때문이다. 반출 과정에서 FIg. 3(b) 와 같이 트랜스포터의 이동 동선에 위치하여 제거해야 하는 블록을 간섭 블록이라 부른다. 트랜스포터는 자체 유압장치로 블록을 상하차할 수 있기 때문에 Fig. 3(c) 와 같이 길이 또는 폭을 고려하여 다수의 블록을 행에 맞추어 배치한다.
PPT Slide
Lager Image
The desciption of block storage problem, (a) storage area configuration, (b) block retrieves process, (c) bounding rectangle
적치장의 적치 능력은 Fig. 3(c) 와 같이 행의 길이만을 고려하여 안전공간을 포함한 블록 길이의 합으로 표현된다. 블록 길이의 산출을 위하여 다각형의 블록형상을 경계 사각형(bounding rectangle)으로 표현하여 길이 값을 사용한다. 적치장의 블록 적치방식은 공간효율성 향상을 위하여 블록의 폭을 기준으로 효율적인 행의 폭을 선정하여 블록의 폭과 차이가 적은 행에 블록을 적치한다.
3. 문제정의 및 복잡도
본 절에서는 먼저 2절의 분석을 바탕으로 적치장 운영을 위한 최적화 문제를 정의한 후 문제의 복잡도를 논한다.
- 3.1 문제정의
적치장은 세로 방향의 행으로 나누어져 운영되며, 블록의 입출고는 적치장의 오른쪽 측면(각 행의 오른쪽 끝)을 통해 이루어진다. 각 블록은 하나의 행에 다른 블록들과 함께 들어온 순서대로 저장된다. 한 행에 최대로 저장할 수 있는 블록의 개수는 제한되어 있으며, 모든 행에 동일한 개수의 블록을 놓을 수 있음을 가정한다. 행의 안쪽에 있는 블록을 출고 또는 재취급하기 위해서는 바깥쪽으로 간섭 블록이 없어야 한다. 초기 블록들은 시작 시점에 적치장의 안쪽부터 빈틈없이 저장되어 있다고 가정한다. 모든 입출고 요청 블록은 입출고 가능 기간을 가지고 있다. 계획 기간 중 입고되어 출고도 되는 블록의 경우 입출고 가능 기간은 겹치지 않는다.
문제 정의를 위하여 다음과 같은 표기를 사용한다:
  • n: 적치장의 행의 개수
  • m: 한 행에 일렬로 적치할 수 있는 최대 블록의 개수
  • (i, j) : 행 i에서 왼쪽부터 j 번째 위치
  • T: 계획 기간의 길이
  • B0: 초기 블록들의 집합
  • 초기 블록b∈B0의 최초 적치 위치
  • Bin: 입고 예정 블록들의 집합
  • Bout: 출고 예정 블록들의 집합
  • Ib: 입고 블록b의 가능 입고 기간들의 집합
  • Ob: 출고 블록b의 가능 출고 기간들의 집합
블록의 입출고 시점과 입고 및 간섭 블록의 적치 위치는 다음의 의사결정 변수로 표현된다:
  • xb: 블록b의 입고 시점
  • yb: 블록b의 출고 시점
  • : t 시점에 입고 및 간섭 블록b적치되는 행
  • : t 시점에 입고 및 간섭 블록b가 적치되는 열
- 3.2 복잡도
본 연구에서는 적치장 운영 계획 문제가 NP-hard임을 보이기 위하여 상호 배제 일정 계획(mutual exclusion scheduling; MES) 문제를 고려한다.
정점(vertex)의 집합 V 와 모서리(edge)의 집합 E 로 이루어진 무지향 그래프(undirected graph) G = ( V ,E )가 주어졌을 때, V 의 부분집합 U 에 대하여( U V ), 만일 U 에 속한 모든 정점의 쌍 ( i, j )가 모서리가 아니라면, 즉 ( i, j )∉ E 라면, U G 에 대하여 독립(independent)이라 한다. MES 문제는 다음과 같이 정의된다:
무지향 그래프 G = ( V ,E )와 양의 정수 q r 이 주어졌을 때, 크기가 q 이하이면서 G 에 대하여 독립인 r 개의 집합 U i ( i = 1, … , r ,| U i | ≤ q )로 분할(partition)할 수 있는가?
순열(permutation)그래프에서 정의 MES문제는 q 가 6보다 크거나 같을 때 NP-complete임이 알려져 있다 ( Jansen, 2003 ).
여기서 순열 그래프의 정의는 다음과 같다:
1부터 s 까지의 순열 p = ( p 1 , … , , ps )가 주어졌을 때, 순열 그래프는 정점의 집합 V = { v 1 , … , vs }와 정점의 쌍 i, j ( > i )에 대하여 순열 p 에서 j i 보다 앞에 있는 ( vi, vj )를 모서리로 하는 그래프이다.
정리 1. 적치장 운영 계획 문제는 NP-hard이다.
Proof. 이 문제가 NP에 속하는 것은 자명하다. 순열 p = ( p 1 , … , , ps )의 순열 그래프 G = ( V, E )와 양의 정수 q r 구성된 MES 문제가 주어졌을 때, 다음과 같이 정의되는 적치장 운영 계획 문제를 고려하자:
  • n=r+ 1
  • m= 2s+ 1
  • T= 2s+ 1
  • B0=r+ 1
  • fork= 1, …,s
PPT Slide
Lager Image
우리는 이와 같이 정의된 문제에서 최소 재취급 횟수가 s 인 것과 V 를 크기가 q 이하이면서 독립인 r 개의 집합으로 분할할 수 있는 것이 동치임을 보인다(필요충분조건). 블록 1부터 (2 s + 1)을 출고하기 위해서 최소한 s 번의 재취급이 필요하다. 그리고 블록 1부터 블록 s 는 순열 p 의 역순으로 행 2에서 행 ( r + 1)로 옮겨져야 한다. s 번의 재취급으로 이루어진 해를 얻기 위해서는 s 개의 블록들을 추가적인 재취급이 발생하지 않도록 행 2에서 행 ( r + 1)까지로 옮겨야 한다. 그렇게 옮겨진 블록들 가운데 추가적인 재취급을 발생시키는 두 개의 블록을 고려하자. 이 두 블록은 순열 그래프 G 에서 모서리로 연결된 두개의 정점에 대응한다. 따라서 추가적인 재취급 없이 블록을 옮기는 것은 V 를 크기가 q 이하이면서 독립인 r 개의 집합으로 분할하는 문제와 동일하다.
4. 휴리스틱
본 연구에서 제안하는 휴리스틱에서는 먼저 개별 블록의 입출고 시점을 확정하고, 다음으로 입고 및 간섭 블록이 적치되는 위치를 결정하는 2 단계의 접근 방법을 취한다.
단계 1에서는 개별 블록의 입출고 시점을 확정하기 위해 입출고가 가장 많이 발생하는 시점을 결정하고, 그 시점이 속한 블록의 입고 시점( xb )과 출고 시점( yb )을 결정한다. 이는 서로 다른 시점에 출고되는 블록들을 하나의 공통 시점에 출고하면 간섭 블록이 여러 번 재취급 되는 상황을 피할 수 있기 때문이다. 또한 입고 블록 또한 출고 시점이 빠른 블록을 바깥쪽에 위치시켜 재취급을 줄일 수 있는 가능성이 커진다.
단계 2에서는 단계 1에서 결정된 개별 블록의 입출고 시점을 바탕으로 출고 시점을 고려하여 순차적으로 입고 블록과 간섭 블록이 놓일 위치를 결정한다. 이때 계산의 복잡도를 줄이기 위해 나중의 추가적인 입고 블록을 고려하지 않고 그 시점에 적치된 블록들만을 고려하여 간섭 블록을 최소화하는 위치를 정한다.
구체적으로, 어떤 시점에서 출고 블록과 간섭 블록을 함께 제외한 적치 상황을 고려하자. 행 i 에서 가장 빨리 나가는 블록의 출고 시점을 𝜃 i 라 하자. 만일 출고되는 블록이 없으면 𝜃 i 는 큰 수 M 으로 한다. 만일 행 i 에 출고 시점이 𝜃 i 보다 늦거나 출고가 되지 않는 블록을 들여오게 되면 간섭을 일으키게 된다. 이와 같은 간섭 블록의 개수를 최소화하는 입고 블록과 간섭 블록의 적치 위치는, 입고 및 간섭 블록 b 와 블록을 놓을 수 있는 위치 k 에 대하여 주어지는 비용 행렬 [ cbk ]를 가지는 배정 문제(assignment problem)로 형식화할 수 있다. 여기서 비용 cbk 는 다음과 같이 정의된다:
PPT Slide
Lager Image
여기서 r ( k )는 위치 k 의 행을 의미하며, 출고 예정이 아닌 블록 b 에 대해서는 yb = M 으로 둔다.
휴리스틱의 절차를 정리하면 다음과 같다:
단계 1
  • Step 1.B=Bin∪Bout으로 놓는다.
  • Step 2.B에 속한 블록들이 가장 많이 입출고될 수 있는 기간t* 를 구한다.
  • Step 3.B에 속하며,t* 에 입출고될 수 있는 블록b에 대해서xb와yb를t* 로 확정한다.
  • Step 4. 입출고 시점이 확정된 블록들을B에서 제거한다. 만약B가 공집합이면 단계를 마치고, 그렇지 않으면 Step 2로 간다.
단계 2
  • Step 5. 초기 적치 형태를 구성한다.
  • Step 6. 기간t= 1,…,T에 대하여 Step 7부터 Step 9까지 수행한다.
  • Step 7. 적치장에서yb=t인 블록들과 이때의 간섭 블록을 반출한다.
  • Step 8. 입고 및 간섭 블록b와 이들을 위치시킬 수 있는 위치k에 대하여 비용 행렬 [cbk]를 구성하고, 최소의 비용을 가지도록 배정한다.
Step 9. 행 1,…, n 에 대하여, 각 행에 배정된 입고 및 간섭 블록 b 가 입고되는 행 ub 와 열 vb 를 결정한다. 이때 각 행에서 출고 시점이 늦은 블록부터 안쪽에서 빈틈없이 위치시킨다.
참고로, Step 8에서 비용 행렬 [ cbk ]를 가지는 배정문제를 해결하기 위하여 본 연구에서는 헝가리언 방법(Hungarian method)을 사용하여 최적해를 도출하였다.
제시된 휴리스틱의 설명을 위하여 Fig. 4 에서 제시된 다섯 행으로 구성된 적치장의 운영 문제를 고려한다. 24시간 동안 블록의 입출고를 위하여 단위 기간을 2시간으로 계획 기간의 길이 T=12로 구성되어 있다. 한 행에는 최대 다섯 개의 블록을 적치할 수 있다( n = 5, m = 5 ). 계획 초기에는( t = 0 ) Fig. 4(a) 와 같이 적치되어 있다; 예를 들어 b 08 의 저장 위치는 (2,3)이며, 이는
PPT Slide
Lager Image
임을 의미한다.
PPT Slide
Lager Image
An example of block storage problem, (a) initial blocks configuration, (b) block storage and retrieval request time constraints
초기 적치 블록 가운데 출고 요청이 발생하지만 특별한 경우 계획 기간 동안 입고된 블록이 다시 출고되는 경우를 고려하였다.
시간 제약 조건을 가진 블록의 입출고 요청은 Fig. 4(b) 와 같다. 예를 들어 b 08 의 출고 가능 기간은
PPT Slide
Lager Image
이며, b 25 의 입고 가능 기간은
PPT Slide
Lager Image
이다. 블록 b 29 와 b 30 은 입고된 후 출고되는 블록이다.
단계 1의 첫 번째 반복 과정은 다음과 같다.
PPT Slide
Lager Image
단계 1은 두 번 더 반복하고 완료되며, 각각 반복의 결과는 Fig. 5 의 (c), (d)와 같다. 즉, 각각 반복에서의 t * 는 4와 10이다.
PPT Slide
Lager Image
Storage and retrieval period determination in Phase 1, (a) blocks that can be stored or retrieved at period 7, (b) first iteration results, (c) second iteration results, (d) third iteration results
단계 2에서 기간 4일 때 Step 8과 9에서 고려되는 배정 문제는 Fig. 6 에 나타나 있다. Step 7에서 출고 및 간섭 블록을 모두 출고시킨 후의 적치장 상황은 Fig. 6(a) 와 같다. 예를 들어 b 03 이 반출되므로 바깥쪽에 놓여 있던 간섭 블록 b 04 와 b 05 가 모두 출고되었다. 비어있는 위치는 점선으로 표시되어 있으며, 각각의 위치 번호는 괄호를 사용하여 표시하였다.
PPT Slide
Lager Image
Assignment problem at period 4 in Phase 2, (a) storage configuration after retrieving blocks, (b) cost matrix
Step 8에서 만들어지는 비용 행렬 [ cbk ]는 Fig. 6(b) 와 같다. 예를 들어, 입고 블록 b 30 을 행 2의 빈위치 (4)에 입고시키면 행 2에서 가장 빨리 나가는 블록 b 06 의 출고 시점 7보다(𝜃 2 = 7) b 30 의 출고 시점
PPT Slide
Lager Image
이 크기 때문에, 재취급이 발생하게 되어 비용
PPT Slide
Lager Image
이 된다. 반면 행 1의 빈 슬롯에 입고시키면 (𝜃 1 = 10)과 b 30 의 출고 시점이 같기 때문에 재취급이 발생하지 않아 비용은 0이 된다.
Step 9에서 Fig. 6(b) 의 비용 행렬을 사용한 최적 배정을 바탕으로 입고 행을 구하고 적치 위치를 선정하여, Fig. 7(a) 와 같이 기간 4가 끝난 후의 적치 결과를 얻을 수 있다. 추가적으로 단계 1에서 확정된 입출고 기간 7과 10에 대해 각각 Step 7부터 9까지 수행하면 Fig. 7 (b) 와 (c)의 결과를 얻을 수 있다.
PPT Slide
Lager Image
Storage configuration at the end of each period, (a) period 4, (b) period 7, (c) period 10
본 연구에서 제안한 휴리스틱을 사용하면 간섭 블록의 재취급 횟수가 11 회인 적치장 운영 계획을 도출할 수 있다. 참고로 이전 연구 ( Ha, et al., 2013 )의 수리 계획 모형을 바탕으로 도출한 최적 계획은 10 회의 최소 재취급 횟수를 가진다. 따라서 제시된 휴리스틱이 도출한 해가 최적에 가까운 근사해임을 알 수 있다. 이전 연구와 동일한 실험 환경에서 최적해를 도출하는데 약 14.5 초가 소요되었으며 휴리스틱의 실행에는 아주 짧은 시간만이 소요되었다.
5. 수치실험
본 연구에서는 이전 연구 [2] 에서 사용된 적치장 문제를 대상으로 휴리스틱을 검증하였다. 적치장은 13 행, 7 열로 이루어져 있다. 예제는 30%에서 90%까지의 초기 적치율에 대하여 각각 10 개의 문제로 구성되어 있다. 여기서 초기 적치율은 적치 능력(91 개) 대비 계획 시작 시점부터 적치되어 있는 블록 개수의 비율을 의미한다.
제안된 휴리스틱은 범용 언어인 Python 2.7을 사용하여 구현 하였으며, 실험은 Intel Core i7-3610QM 2.3GHz와 16GB RAM을 가지는 하드웨어와 Windows 7(64bit)에서 수행되었다.
표 1은 수리 계획 모형으로 도출한 최적해와 휴리스틱으로 찾은 근사해의 비교 결과를 보여준다. 각각의 초기 적치율과 문제 번호(Instance No.)에 해당하는 칸에는 최적 재취급 개수 𝓏 * 와 근사해의 재취급 개수
PPT Slide
Lager Image
를 나타내었다. 예를 들어, 50%의 초기 적치율을 가지는 첫 번째 문제의 경우 최적해는 𝓏 * = 15 회의 최소 재취급 횟수를 가지나, 휴리스틱으로 도출한 근사해는
PPT Slide
Lager Image
=16 회의 재취급이 필요하다는 것을 알 수 있다. 한계시간 3,600 초 내에 최적해를 찾지 못한 경우는 ``-''로 표시하였다.
근사해와 최적해의 차이는 GAP 의 평균(AVG)과 최소(MIN), 최대(MAX)로 나타내었다. 각각의 문제에 대하여
PPT Slide
Lager Image
로 계산된다. 단, 최적 𝓏 * 가 0 인 경우는 𝓏 *
PPT Slide
Lager Image
에 각각 1을 더하여 계산하였으며, 한계시간 내에 최적해를 구하지 못한 경우는 계산에서 제외하였다. 또한 최적해를 구하는데 소요되는 계산시간은 한계시간 내에 최적해를 구하지 못한 경우를 제외하여 평균 계산 시간(Avg. CPU time for 𝓏 * )으로 나타내었다.
초기 적치율 30%인 예제에서는 GAP 의 평균이 큰 차이를 보인다. 하지만 절대적인 재취급 횟수의 차이는 크지 않음을 알 수 있다. 초기 적치율이 40% 이상 증가하면 GAP 의 차이가 줄어들어 평균 10% 미만의 차이를 보였다. 참고로 최적해를 도출한 경우도 많이 있음을 알 수 있다. 수리모형은 80%까지의 초기 적치율을 가지는 문제에 대하여 모두 한정된 시간 내에 해를 구할 수 있었다.
초기 적치율이 증가하면서, 평균 계산 시간도 증가하는 것을 볼 수 있다. 특히 90%의 문제에 대하여 한정된 시간 내에 해를 구하지 못하는 문제의 수가 2 개 존재하는 것을 볼 수 있다. 현장에서 주어진 시간 내에 계획을 수립하지 못하면 적치장의 블록 입출고에 차질이 발생할 수 있다. 반면 휴리스틱에서는 모든 문제에 대하여 0.1 초 이내에 해를 도출한 것을 볼 수 있다. 이는 입고 지연, 생산 공정 차질, 기상 변화, 중간 품질 검사 등으로 일정이 빈번하게 변하는 현장에서 기민하게 계획을 재수립하기 위한 방법으로 사용할 수 있는 의미 있는 결과이다.
6. 결 론
본 연구는 주어진 기간 제약 조건에서 블록의 입출고 시점과 적치 위치를 결정하는 적치장 운영 계획 문제를 다루었다. 이는 블록의 중량 제약 조건을 고려하여 이송지연 최소화와 장비간 부하평준화를 위한 이송장비 할당 계획을 함께 수립하기 위한 첫번째 과정이다.
본 연구는 현장에서 동적으로 변화하는 상황을 감안하여 신속하게 근사해를 도출하는 휴리스틱을 제안하였다. 구체적으로, 적치장 운영 방법을 모형화하고 문제의 복잡도를 보였으며, 두 단계로 이루어진 휴리스틱을 제안하였다. 수치실험을 통하여 정수 계획 모형과 휴리스틱의 성능을 비교하였다. 제안된 휴리스틱의 신속성은 공정상태가 빈번하게 변하는 현장에서 기민하게 대응하기 위한 수단으로 중요한 의미를 지니며, 블록의 입출고 및 재취급을 실행하기 위한 이송장비 운영 계획의 신속한 재수립을 위해서도 필수적일 것이다.
휴리스틱으로 도출한 운영 계획은, 단계 1에서의 입출고 기간 선정 방법에 의해, 임의의 기간에 블록 이송 작업이 집중될 수 있다. 많은 적치장을 보유하고 있는 대규모 조선소의 경우 충분한 수의 장비를 운용하고 있으므로, 적절한 운영 전략과 함께 휴리스틱이 사용된다면 보다 나은 운영 결과를 가져다 줄 수 있을 것으로 판단된다. 운영 조건에 따라 임의의 기간에 이송할 수 있는 블록의 수가 제한 될 수 있으며 이를 위하여 집중된 입출고 시점을 적절히 분산해야 하며, 이 과정에서 증가하는 재취급을 최소화 할 수 있어야 할 것이다.
본 연구를 바탕으로 한 향후 과제로는 적용분야 확대를 위하여 블록의 입출고 방향이 다양한 환경에 대응하는 연구가 필요하다. 또한 적치장 운영 계획을 실행하기 위한 이송장비 운영 계획의 연구도 동시에 이루어져야 한다. 생산 환경에 따라 운영 가능한 이송장비의 제한되어, 단위기간의 입출고 및 재취급 블록의 개수가 제한되는 상황을 고려하는 연구도 필요할 것이다.
Acknowledgements
이 논문은 2014년도 정부(미래창조과학부)의 재원으로 한국연구재단의 지원을 받아 수행된 연구임(No. 2012K1A2B1A03000562)
BIO
손 정 열
서 흥 원
하 병 현
References
Cho K.K. , Chung K.H. , Park C. , Park J.C. , Kim H. S. 2001 A Spatial Scheduling System for Block painting process in shipbuilding CIRP Annals 50 (1) 339 - 342
Ha B.H. , Son J.R. , Cho K.K. , Choi B.C. 2013 A Mathematical Programming Approach for Block Storage Problem in Shipbuilding Process The Korean Operations and Management Science Society 30 (3) 99 - 111    DOI : 10.7737/KMSR.2013.30.3.099
Jansen K. 2003 The Mutual Exclusion Scheduling Problem for Permutation and Comparability Graphs Information and Computation 180 (2) 71 - 81
Koh S.G. 1996 A production schedule with genetic algorithm in block assembly shop Korean Management Science Review 13 (1) 1 - 12
Koh S.G. , Park J.C. , Chon Y.S. , Joo C.M. 1999 Development of a Block Assembly Scheduling System for Shipbuilding Company IE interfaces 12 (4) 586 - 594
Lee K.J. , Lee J.K. , Choi S.Y. 1996 A Spatial Scheduling System and its Application to Shipbuilding DAS-CURVE Expert Systems With Applications 10 (3/4) 311 - 324
Lee J.K. , Lee K.J. , Park H.K. , Hong J.S. , Lee J. S. 1997 Developing Scheduling Systems for Daewoo Shipbuilding DAS Project European Journal of Operational Research 97 (2) 380 - 395
Lee S.H. , Kim J.O. , Moon I.K. 2011 Deployment Planning of Blocks from Storage Yards using a Tabu Search Algorithm Journal of the Korean Institute of Industrial Engineers 37 (3) 198 - 208
Park C.K , Seo J.Y 2006 A Case Study on Assembly Block Operations Management at Shipyard Korean Management Science Review 23 (2) 175 - 185
Park C.K. , Seo J.Y. 2009 Mathematical Modeling and Solving Procedure of the Planar Storage Location Assignment Problem Computers & Industrial Engineering 57 (3) 1062 - 1071
Park C.K. , Seo J.Y. 2010 Comparing Heuristic Algorithms of the Planar Storage Location Assignment Problem Transportation Research Part E 46 (1) 171 - 185
Park K.C. , Lee K.S. , Park S.S. , Kim S.H. 1996 Modeling and Solving the Spatial Block Scheduling Problem in a Shipbuilding Company Computers & Industrial Engineering 30 (3) 357 - 364
Park M.H. , Lee W.S. , Ock Y.S. , Lee T.E. 1995 A Review of Korean Shipbuilding Industry and Industrial Engineering Research IE interfaces 8 (2) 5 - 20
Son J.R. , Cho K.K. 2007 Design for block logistics system of storage location assignment in shipbuilding Proceedings The 12th Annual International Conference on Industrial Engineering Theory, Applications and Practice Cancun, Mexico 4-7 November 2007 488 - 494