Journal Search Engine

ISSN : 2005-0461(Print)
ISSN : 2287-7975(Online)

Journal of Society of Korea Industrial and Systems Engineering Vol.43 No.4 pp.23-32
DOI : https://doi.org/10.11627/jkise.2020.43.4.023

Batch Scheduling Algorithm with Approximation of Job Completion Times and Case Studies

Song-Eun Kim^*

, Seong-Hyeon Park^*

, Su-Min Kim^*

, Kyungsu Park^**†

, Min Hyung Hwang^***

, Jongeun Seong^****

^*Department of Industrial & Management Systems Engineering, Dong-A University
^**Department of Business Administration, Pusan National University
^***DongHwa Entec Co., Ltd.
^****KAR Co., Ltd.

^†Corresponding Author : ks.park@pusan.ac.kr

Received 29/07/2020 Finally Revised 08/09/2020 Accepted 10/09/2020

Abstract

Many small and medium-sized manufacturing companies process various product types to respond different customer orders in a single production line. To improve their productivity, they often apply batch processing while considering various product types, constraints on batch sizes and setups, and due date of each order. This study introduces a batch scheduling heuristic for a production line with multiple product types and different due dates of each order. As the process times vary due to the different batch sizes and product types, a recursive equation is developed based on a flow line model to obtain the upper bound on the completion times with less computational complexity than full computation. The batch scheduling algorithm combines and schedules the orders with same product types into a batch to improve productivity, but within the constraints to match the due dates of the orders. The algorithm incorporates simple and intuitive principles for the purpose of being applied to small and medium companies. To test the algorithm, two case studies are introduced; a high pressure coolant (HPC) manufacturing line and a press process at a plate-type heat exchanger manufacturer. From the case studies, the developed algorithm provides significant improvements in setup frequency and thus convenience of workers and productivity, without violating due dates of each order.

Key Words : Batch Scheduling , Flow Line Models , Upper Bound on Completion Time , Batch Size

작업완료시각 추정을 활용한 배치 스케줄링 및 사례 연구

김 송은^*, 박 성현^*, 김 수민^*, 박 경수^**†, 황 민형^***, 성 종은^****

^*동아대학교 산업경영공학과
^**부산대학교 경영학과
^***동화엔텍
^****케이에이알

초록

키워드 :

This article has been cited by 0 article in crossref

Cited-By

Funding:

1. 서 론

한국뿐 아니라 많은 국가들이 제조업의 약화에 큰 위 협을 느끼고 이를 대비하기 위해 노력하고 있다[7, 9]. 중 소기업중앙회(KBIZ)에 따르면, 2020년 1월의 SBNI(경기 전망지수)와 최근 3년간 SBNI 평균치를 비교해본 결과 제조업에서 대부분의 전망이 악화되었을 뿐만 아니라 SBNI가 최저치를 갱신하는 등 많은 제조기업들이 경영 상의 어려움을 겪고 있음을 알 수 있다. 특히 인력 확보 및 관리의 어려움, 기술 경쟁력 약화 및 이로 인한 생산 성 저하 등의 이유로 제조 경쟁력을 점차 잃어가고 있다 [11]. 이러한 현실에서 중소 제조기업이 생산성 향상 및 경쟁력 강화를 위해서는 효율적이고 체계적인 생산 시스 템을 구축하는 것이 중요하다. 특히, 중소기업에서는 수 주 및 생산 정보의 잦은 변동으로 인해, 납기를 고려하면 서도 효율적이고 실용적인 스케줄링이 필수적이다.

따라서, 본 논문에서는 다품종의 제품들이 하나의 제 조라인에서 생산되는 유연생산시스템을 위해 플로우 라 인(flow line) 모델을 제시하고, 이를 활용한 배치(batch) 사이즈 선정 및 스케줄링 알고리즘을 제시한다. 실제 중 소기업의 제조 특성을 반영하여 플로우 라인은 배치 사 이즈 및 제품의 종류에 따라 다른 공정 소요시간을 가지 며, 이론적 연구를 통해 각 제품 배치가 모든 공정을 완 료하는 시각에 대한 상한값(upper bound)을 도출하였다. 또한, 도출된 배치 스케줄링 알고리즘을 실제 중소기업 의 생산 데이터에 적용하여 성능평가를 수행하였다.

실제 중소기업의 두 가지 적용사례는 다음과 같다. 먼 저, 고압 절삭유 공급 장치(High Pressure Coolant, 이하 HPC)를 생산하는 K사의 생산 공정에 적용된 스케줄링 알고리즘을 소개한다. 고압 절삭유 공급 장치, 즉 HPC는 공작기계가 절삭 가공 시 냉각 및 윤활을 위해 사용되는 절삭유를 고압으로 분사해주는 장치이다. K사에의 적용 을 위해, 우선 K사의 HPC 생산 공정 개요 및 작업 순서 를 파악하고, 회귀분석을 통해 공정별로 배치 사이즈에 따른 소요시간을 모델링하였다. 이를 기반으로 구축된 플로우 라인 모델을 통해 효율적인 배치 사이즈를 선정 할 수 있도록 했다. 또 다른 사례로, 판형 열교환기 제작 업체인 H사의 공정 스케줄링을 소개하였다. H사의 전체 공정을 분석하여 병목(bottleneck) 공정인 프레스(press) 공정에 대해 스케줄링 알고리즘을 적용하였다. 특히, 프 레스 공정은 두 개의 기계를 사용하고 21가지 제품을 취 급하며, 제품 종류에 따른 기계 선정 제약도 존재하였다. 또한 잦은 수주 및 납기 변동에도 불구하고 체계적인 절 차나 시스템 없이 관리자의 임의로 스케줄링이 행해짐으 로써 생산성 저하 및 작업자의 불만이 야기되고 있었다. 따라서, 효율적인 배치 스케줄링을 통해 금형 교체 횟수 및 셋업 시간을 감소시키고, 생산성 향상 및 작업자의 편 의성 증대가 요구되었다.

본 연구의 의의는 다음과 같다. 첫째, 제품의 종류와 배치 사이즈에 따라 공정 시간이 변화하는 플로우 라인 모델에서 각 배치별 공정 완료 시각의 상한값을 추정하 는 재귀적 모형을 도출하였다. 이를 통해 모든 공정에서 각 배치들의 진행사항을 추적할 필요없이, 직전 배치의 전체 공정 완료 시각만을 이용하여 다음 배치들의 전체 공정 완료 시각의 추정이 가능하다. 둘째, 다수의 생산라 인 또는 다수의 기계로 이루어진 공정을 위해, 납기 준수 를 최우선으로 고려하면서 생산성 향상을 목적으로 하는 배치 사이즈의 결정 및 스케줄링 알고리즘을 제시하였 다. 실제 중소기업에의 적용을 위해 가능한 간단하고 직 관적인 원리를 활용하였다. 셋째, 실제 중소기업 2곳의 데이터를 바탕으로 알고리즘을 적용 및 테스트하였다.

본 논문의 제 2장에서는 관련된 기존 연구들의 이론 및 배경을 소개하고 본 연구와의 차별점을 제시한다. 제 3장에서는 플로우 라인 모델을 제시하고 전체 작업 완료 시각에 대한 추정식 도출한다. 제 4장에서는 공정의 특 성을 반영한 배치 사이즈 및 스케줄링 알고리즘을 소개 한다. 제 5장에서는 4장에서 도출된 알고리즘을 K사의 고압 절삭유 공급 장치 공정과 H사의 프레스 공정에 적 용하고, 스케줄링 알고리즘의 효과에 대해서 탐구한다. 마지막으로, 제 6장에서는 본 연구의 의의와 향후 연구 방향을 제시하였다.

2. 기존 연구 및 문헌 조사

플로우 라인(flow line) 모델은 직렬로 배열된 기계들을 차례로 방문하여 각 공정을 받는 것을 나타내는 수리 모 형이다. 1950년대, 플로우 라인 모델에 관련된 결과가 발 표된 후 제조 공정을 분석하기 위해 오늘날까지 사용되어 왔다[3]. 특히, 임의의 도착 분포를 가지는 플로우 라인에 대한 통찰력을 제공했던 1960년대 연구인 Avi-Itzhak[1]과 Friedman[4]에서는 기초 플로우 라인 모델을 강화하고 적 용하기 위한 많은 작업이 이루어졌다. 이후로도 플로우 라인은 오랫동안 제조 시스템 모델로 연구되어 왔으며 다 양한 프린터, 자동차 등의 대량 제조 공정에 적용이 되어 왔다[2]. 또한 최근에는 반도체 제조공정에서 많은 연구가 되어 왔다. 반도체 공정의 병목 구간에 모형을 적용, 유전 알고리즘을 바탕으로 한 스케줄링 이론이 발표되었고[23], 이를 이용해 처리량이 병목 현상의 서비스 시간에 의해 결정된다는 것을 보여주기도 하였다[1]. 반도체 스캐너 장 비를 플로우 라인으로 모델링하고 시뮬레이션을 활용해 그 적합성을 검증하고 활용하거나[12], 반도체 클러스터 장비의 분석[10] 등에도 활용되었다. 또한, 플로우 라인은 정확한 성능 추정치를 제공할 수 있어 시뮬레이션을 위한 모델로도 사용된다[14]. 이러한 플로우 라인의 활용성 증 대를 위해 모델의 변환 과정이나 다양한 관련 이론들은 [16, 17]에서도 연구 되었다.

제조업에서 배치(batch)는 주로 ‘묶음’ 또는 ‘1회의 공정 을 통해 얻는 생산량’을 의미한다. 따라서 배치생산(batch production) 방식은 일괄생산, 묶음생산으로 불리기도 하 며, 주문생산이나 대량생산과 구분되기도 한다. 하나의 배 치의 크기는 로트(lot)의 크기와 동일할 수도 있으며, 로트 의 크기보다 큰 경우도 있다. 배치(batch) 생산 시스템은 표준화된 제품을 대량생산 한다는 점에서 연속 생산 시스 템과 유사하나, 주로 더 많은 종류의 제품을 생산할 경우 에 사용된다. 또한 하나의 제품을 일정량(배치 크기)을 생 산하고 다른 제품으로 변경하여 생산한다는 점에서 큰 차 이를 보이며, 이때 제품 또는 배치마다 생산량과 순서를 변경시킨다는 점에서 큰 차이를 보인다. 이러한 배치생산 방식에서는 주로 배치 사이즈의 결정(batch sizing)과 배치 의 디스패칭 또는 순서 결정에 대한 이슈가 발생하며, 이 를 위해 매우 많은 연구가 진행되어 왔다. 대표적인 예로, 최소 배치 사이즈(MBS, Minimum Batch Size) 기법은 단순 하고 적용하기 쉬워 널리 활용되고 있다. 또한, 이를 확장 하여 다양한 종류의 로트를 가지는 경우에 배치의 크기를 결정하는 MBSX 기법 또한 널리 연구되었다[19]. Glassey and Weng[5]에서 제안된 Dynamic Batching Heuristic(DBH) 은 가장 먼저 도착하는 로트의 도착 시간 정보를 배치 스 케줄링에 활용하였다. 즉, look-ahead number를 적용해 앞 으로 도착할 제품의 도착 시간을 예측한 후 그 값을 통해 얻은 로트의 도착 시간 데이터를 활용해 적정 배치 사이즈 를 결정하였다. Weng and Leachman[22]의 Minimum Cost Rate(MCR) 알고리즘은 모든 로트당 대기시간을 고려하여 배치 사이즈를 결정하는 것에 그 특징이 있다. Van De Rzee et al.[21]에 의해 제안된 DJAH 기법은 단일 로트, 단일 기계 상태뿐만 아니라 여러 로트와 여러 기계의 상태 까지 고려하였다. 이외에도 여러 로트를 통합하여 처리하 는 배치 공정(BP, Batch Process) 방식에 대한 연구들도 진 행되었다. 예를 들어, 효율을 극대화하고 작업의 납기지연 을 최소화하기 위해 도착한 작업에 대해서 단위 기간의 실시간적 일정계획을 수립하는 알고리즘이 Joe and Gu[8] 에서 연구되었다. 최근에도 이러한 배치 사이즈 결정 및 스케줄링을 위한 연구는 계속되고 있다[15, 18].

3. 플로우 라인 모델

본 장에서는 플로우 라인 모델을 통해 각 배치별 공정 완료시각을 추정하는 예측식을 소개한다. Kock et al.[12], Park and Morrison[13]에서는 배치 사이즈에 상관없이 단 위당 공정 시간이 일정한 단일 종류의 제품이 복수의 서 버를 가지는 공정들로 이루어진 플로우 라인에 대해 다루 었다. 특히, 이러한 시스템 하에서 각기 다른 도착시각을 가지는 제품들에 대해 각 공정에서의 진행사항을 추적하 지 않고, 이미 전체 공정이 완료된 제품들의 완료시각만 을 사용하여 다음 제품들의 전체 공정 완료시각을 추론 하였다. 본 연구에서는 Kock et al.[12], Park and Morrison [13]에서 도출된 상한값 추정식을 확장하여 배치 사이즈 또는 제품 종류에 따라 각 공정 소요시간이 변화하는 제 조 라인에 적용한다. 참고로 단일 제품은 배치 사이즈가 1인 하나의 배치로 취급가능하다.

<Figure 1>에 표현된 것과 같이, 플로우 라인 모델은 다수의 공정이 직렬로 연결되어 있으며 주문에 따라 여러 종류의 제품이 단일제품 또는 배치의 형태로 모든 공정을 진행한 후 시스템을 벗어난다. 시스템은 총 M개의 공정 으로 이루어져 있으며, i번째 공정을 m_i라고 정의한다. 각 공정은 동시에 여러 배치를 소유할 수 없다. 예를 들 어, 배치 k가 m₁에서 공정을 완료했으나 m₂에서 배치 k - 1이 공정을 진행 중이면, 배치 k는 공정 m₂로 넘어가 지 못하고 공정 m₁에 그대로 남아있게 된다. 배치 k - 1 이 공정 m₂를 완료하고 m₃로 넘어가야 배치 k도 공정 m₂로 진행이 가능하다. 또한, 각 공정 사이에는 유한한 용량의 대기 공간(buffer)이 존재할 수 있으며, 이 또한 하 나의 공정으로 표현된다. 즉, n개의 저장 용량을 가지는 대기 공간은 공정소요시간이 0인 n개의 공정으로 대체 가능하다. 각 공정에 소요되는 시간은 제품의 종류와 각 배치의 크기에 의해 결정된다. 즉, 배치 k의 제품 종류와 배치의 크기를 각각 t_k와 N_k로 정의하면, 배치 k에 대해 공정 m_i를 완료하는데 소요되는 공정 시간은 τ_i (k, t_k, N_k) 로 표현한다. 또한, 본 연구에서는 이미 수주가 완료된 제 품에 대한 스케줄링을 다루므로, 모든 부품 또는 제품들 은 이미 시스템에 도착하여 공정 m₁ 앞에서 대기 중인 것으로 가정한다. 모든 공정이 끝난 m_M 이후에는 무한의 대기 공간이 있다고 가정한다.

이러한 시스템에서 각 제품 배치들이 각 공정을 시작 하는 시각은 간단한 식을 통해 계산이 가능하다. 즉, X_i (k, t_k, N_k)를 k번째 배치를 공정 시작 시각이라고 정의 하면, 아래와 같이 표현 가능하다.

X_{i} (k, t_{k}, N_{k}) = max {\begin{matrix} X_{i - 1} (k, t_{k}, N_{k}) + τ_{i - 1} (k, t_{k}, N_{k}), \\ X_{i + 1} (k - 1, t_{k - 1}, N_{k - 1}) \end{matrix}}

(1)

max 함수 안의 첫 번째 식은 k번째 배치의 제품이 공정 m_i_-1를 완료하고 공정 m_i에 들어갈 준비가 되었음을 의 미한다. 하지만 공정 m_i 또한 k - 1번째 배치를 완료하고 새로운 제품을 처리할 준비가 되어 있어야 하므로 max 함 수 안의 두 번째 식이 존재한다.

Park and Morrison[14]의 Theorem 1에서는 이러한 기본 식을 활용하여 각기 다른 도착 시간을 가지는 단일 종류 의 제품에 대해 직전 제품들의 전체 공정 완료시각만을 사용하여 다음 제품들의 전체 공정 완료시각의 상한값을 추정하였다. k번째 제품의 전체 공정 완료시각을 C_k, 도 착시각을 a_k, 공정 i 소요시간을 τ_i라, 공정 i를 위한 서버 수를 p_i라고 정의하면, 해당 식은 아래와 같다.

C_{k} \leq max_{i} {a_{k} + \sum_{j = 1}^{M} τ_{j}, C_{k - p_{i}} + τ_{i}}

(2)

위 식의 의미를 살펴보면, max 함수 안의 첫 번째 식 은 배치가 시스템 안에서 단 한 번의 대기(delay) 없이 공정을 완료했음을 의미한다. 두 번째 식은 배치 k가 공 정 m_i에서 배치 p_i로 인해 대기(delay)를 경험했으며 이 후 공정에서는 대기 없이 공정을 진행했음을 의미한다. 본 연구에서는 모든 제품이 이미 시스템에 도착했으므 로, 위 식의 첫번째 식은 무시할 수 있다. 또한, 각 공정 은 하나의 서버만을 가진다고 가정하였으며 각 배치마다 공정 소요시간이 다르므로 이를 반영하여야 한다.

이를 확장하여, 본 연구 시스템을 위한 개략적인 아이 디어는 <Figure 2>를 통해 설명 가능하다. <Figure 2>는 배치 k가 공정 m_i에서 배치 k - 1로 인해 마지막 대기를 경험했으며 이후 공정에서는 대기 없이 공정을 진행했음 을 의미한다. 또한, 상한값을 추정하기 위해, 각 배치 k - 1 또한 m_i 이후 대기 없이 공정을 완료한 경우를 고 려한다. <Figure 2>에 표시되어 있듯이, 배치 k가 공정 m_i에서 직전 배치와 마지막 대기를 경험하였을 때, 직전 배치와의 전체 작업완료 시각 차이는 아래와 같다.

\sum_{j = 1}^{M} τ_{j} (k, t_{k}, N_{k}) - \sum_{j = i + 1}^{M} τ_{j} (k - 1, t_{k - 1}, N_{k - 1})

(3)

식 (3)을 활용한 작업완료시각의 상한값 추정식은 식 (4) 와 같다. 정확한 수학적 증명은 Park and Morrison[14]의 Lemma 1과 Theorem 1의 증명 방식과 동일하므로 생략한다.

\begin{array}{l} C_{k} \leq C_{k - i} + \\ max_{i = 1, \dots, M} {\begin{matrix} \sum_{j = i}^{M} τ_{j} (k, t_{k}, N_{k}) - \sum_{j = i + 1}^{M} τ_{j} (k - 1, t_{k - 1}, N_{k - 1}), \\ τ_{M} (k, t_{k}, N_{k}) \end{matrix}} \end{array}

(4)

이러한 추정식을 활용하면 각 공정에서 각 제품이 언 제 공정을 시작하고 완료하는지 일일이 추적할 필요가 없 으며, 계산의 복잡성도 크게 줄일 수 있다. 또한, 실제 제 조 현장에서는 제품의 납기일 준수를 위하여 이러한 제품 완료 시각에 대한 상한값의 추정이 더욱 중요하다.

4. 배치 사이즈 및 순서 결정 알고리즘

본 연구에서는 납기 만족을 최우선으로 하면서 생산 성을 향상하는 것을 그 목적으로 한다. 이를 위해, 로트 순서를 재배열하여 배치 사이즈를 최대화하며, 이를 통 해 셋업 감소와 작업자의 편의성 증대, 생산성 향상, 안 전성 향상 등을 꾀할 수 있다.

하나의 생산라인은 다수의 공정으로 이루어져 있으나, 많은 실제 생산라인이 작업장의 레이아웃 및 크기, WIP (work-in-progress) 저장 공간 부족, 자동화 여부 등으로 인해 최초 공정에서 배치의 크기와 순서가 결정되면 후속 공정에서는 변경이 불가능하다. 따라서 본 스케줄링 알고 리즘에서는 최초의 배치 사이즈 및 순서를 결정한다. 또 한, 각 배치의 전체 공정 완료 시각을 계산하고 납기 만족 여부를 판별하기 위해서, 3장에서 도출된 배치 공정 완료 시각의 상한값을 추정하는 식을 이용한다. 이러한 추정식 을 사용함으로써 연속되는 공정을 하나의 공정으로 취급 가능한 장점을 가진다. 따라서 본 연구에서는 다수의 공 정으로 이루어진 다수의 생산라인(또는 기계)에 적용가능 한 알고리즘 도출을 목적으로 하지만, 본 장에서는 다수 의 생산라인(또는 기계)이 하나의 공정을 담당한다고 가 정하고 설명한다. 참고로, 5장의 K사는 다수의 공정으로 이루어진 하나의 생산라인에 대해 본 알고리즘을 적용하 며, H사는 하나의 공정을 다수의 기계가 담당하는 경우에 대해 다룬다.

본 알고리즘을 위한 가정은 다음과 같다. 생산라인은 여러 종류의 제품을 생산하며, 동일한 제품만 하나의 배 치로 생산 가능하다. 또한, 제품별 또는 배치 사이즈별로 서로 다른 공정 시간을 가진다. 또한, 제품 종류는 기계 (또는 생산라인)의 개수보다 많다고 가정한다. 수주 받은 각 주문은 1개 이상의 동일한 종류의 제품으로 이루어져 있으며, 각 주문을 하나의 로트로 취급한다. 하나의 로트 는 분할될 수 없으며, 하나의 배치 안에서 생산되어야 한 다. 또한, 수주 받은 주문들은 생산능력(capacity) 하에서 처리 가능하다.

알고리즘을 위해 필요한 변수에 대한 정의는 아래 <Table 1>과 같다.

알고리즘의 대략적인 순서는 아래와 같다.

1. 수주 받은 주문들을 납기일 기준으로 오름차순으로 정렬 하고 순서대로 로트 번호를 부여한다(k = 1, 2, 3, ⋯, K).
2. 로트 번호 순으로 모든 기계에 하나씩만 로트를 할당하 되, 한번 할당된 로트 타입은 할당하지 않는다. 즉, 각 기계(또는 생산 라인)별로 서로 다른 타입의 한 개의 로 트만을 가진다. 이때, 기계 m에 할당된 로트를 L_c(m) 이라고 정의한다.
3. 첫 번째 기계에 대해 할당을 시작한다. 즉, m = 1이라 고 정의한다.
4. 할당된 L_c(m)과 다른 다른 타입 로트 중 최소 번호 로 트를 가지는 로트를 L_c (m) 다음 순번 로트로 할당하고 L_N (m)이라고 정의한다( $t_{L_{C} (m)} \neq t_{L_{N} (m)}$ ) .
5. 할당된 L_c(m)과 동일한 타입의 로트 중 최소 번호 로트 를 가지는 로트를 L_N (m) 직전 순번으로 할당한다. 만 약, L_N (m)이 납기를 만족시키면 ( $C_{L_{N} (m)} \leq D_{L_{N} (m)}$ ) 4단 계를 반복한다. 만약 납기를 만족시키지 못하면 ( $C_{L_{N} (m)} > D_{L_{N} (m)}$ ) , 직전에 할당된 로트를 취소하고 다음 단계로 넘어간다. L_c (m)과 동일한 타입의 로트들이 모두 할당 이 완료되어도 다음 단계로 넘어간다. 참고로, 단일 공 정이 아닌 다수의 공정으로 이루어진 생산라인에 대해 본 알고리즘을 적용하는 경우, $C_{L_{N} (m)}$ 계산을 위해 3장 의 플로우 라인 추정식인 식 (4)를 사용한다.
6. L_N (m)을 새로운 L_c(m)으로 설정한다.
7. 다음 기계들에 대해서도 4~6단계를 반복한다(m = m + 1). 마지막 기계(m = M )에 대한 할당을 완료하였다면, 다시 처음의 기계(m = 1)에 대해 4~6단계를 반복한다. 이 러한 과정은 모든 제품의 할당이 끝날 때까지 반복된다.

본 배치 알고리즘을 위한 개략적인 순서도는 <Figure 3>과 같다. 생산라인 또는 기계별로 담당할 수 있는 제 품의 종류에 제약이 있다면 단계 2와 단계 4에서 고려될 수 있으며, 배치 최대 크기에 제약이 있다면 단계5에서 고려될 수 있다.

이러한 알고리즘을 통해, 다음 납기일(즉, 로트 L_N (m) 의 납기일)을 준수하면서 현재 고려 중인 배치(즉, 로트 L_c(m)으로 시작하는 배치)의 크기를 증가시킴으로써 셋 업의 감소, 생산성 향상, 작업자의 편의성 증대 등의 효 과를 기대할 수 있다. 본 알고리즘은 최적화된 스케줄을 제공하지 않으므로 주문의 납기일을 만족시키지 못할 가 능성도 존재하나, 실제로는 이미 영업 단계에서 생산 현 장의 생산능력(capacity)을 고려하여 수주 및 납기일이 결정되므로 실제 중소기업의 상황에서는 이러한 알고리 즘은 매우 안정적일 수 있다.

5. 사례연구

5.1 K사의 고압 절삭유 공급장치 생산라인

본 장에서는 K사의 고압 절삭유 공급장치(이하 HPC) 생산라인과 주문 현황 자료를 바탕으로 개발된 배치 알 고리즘을 적용하였다. HPC 제조공정은 각 배치들이 여 러 공정 과정을 거치는 흐름 방식이며, 모든 공정이 수작 업으로 이루어진다. 또한, 제품은 두 가지 타입(type)으로 나누어진다. 하나의 배치는 하나의 타입만으로 구성되며, 작업장 크기 제약으로 인해 하나의 배치는 최대 10대의 제품으로 구성될 수 있다. 자세한 시스템에 대한 설명은 Seong[20]에서 참조할 수 있다.

<Figure 4>는 두개의 HPC 타입(타입 1과 타입 2)에 대 한 작업 공정 순서를 나타낸다. 각 작업은 수작업의 특성 상 한 번에 생산되는 수량, 즉 배치의 크기가 늘어날수록 대당 작업시간은 감소한다. 전기 조립 작업들은 타입 2 의 경우에만 필요로 한다.

가장 첫 번째 작업으로는 기계 1차 조립(OP10)과 전기 1차 조립(OP20)이 병렬적으로 진행된다. 기계 1차 조립 은 타입 1과 타입 2에 대해 모두 필요하나, 전기 1차 조 립은 타입 2에 한해서만 필요하다. 또한 배치 사이즈에 따라 작업시간은 다르나, 배치 사이즈가 10인 경우를 기 준으로 기계 1차 조립은 약 50분/개, 전기 1차 조립은 약 90분/개의 시간이 소요된다. 하지만 최근 6개월의 수주 량을 분석한 결과, 타입 1의 수주량이 1.6배 이상 많고, 작업자들과의 인터뷰 결과, 전기 1차 조립은 작업의 편 의성 때문에 작업자들이 작업 간 여유시간에 미리 완료 해 두는 경우가 많았다. 따라서 본 연구에서는 전기 1차 조립 작업을 배제하고 기계 1차 조립의 작업만을 첫 번 째 작업으로 고려한다.

기계 2차 조립(OP30)과 기계 3차 조립(OP40)은 두 가 지 타입 모두에 대해 수행되어야 한다. 전기 2차 조립 (OP50)의 경우 타입 2에서만 진행하므로 타입 1의 공정 소요시간을 0으로 정의하였다. 성능 테스트 작업(OP60) 은 배치 형태의 작업이 이루어지지 못하고 배치 사이즈 가 1로 제한되며 소요시간 또한 매우 높아, 대부분의 경 우 병목(bottleneck) 공정의 역할을 하였다. 마무리/출하 작업(OP70)은 소요시간이 매우 적어, 직전 공정인 성능 테스트 작업이 이루어지는 동안 작업이 완료되므로 본 연구의 범위에서 제외되었다.

성능 테스트 공정을 제외한 본 시스템의 작업 시간은 작업자의 숙련도 상승 및 준비 시간 감소로 인해 배치 사 이즈의 증가에 따라 단위당 작업 시간이 감소하는 경향이 있다. 이를 분석하기 위해 각 공정별로 배치 사이즈가 1에 서 최대 10인 경우들의 작업 시간 자료를 바탕으로 배치별 작업시간 추정식을 추정하였다. 그 결과 각 공정별 배치 사이즈에 따른 작업 시간 및 추정식은 <Figure 5>와 같다.

배치사이즈에 따른 작업 소요 시간은 선형 회귀를 적 용하여, 배치 사이즈가 N인 작업 i를 수행하는데 걸리는 시간은 아래 식으로 나타낼 수 있다. 아래와 같다.

τ_{i} = α_{i} + β_{i} \times N

이때, 작업 i를 위한 α_i , β_i 값은 아래 <Table 2>와 같다.

작업 소요 시간 추정식과 <Table 2>를 통해, 배치 사 이즈가 2대 이하인 경우에는 전기 1차 조립이 병목 공정 이 되지만, 3대 이상이면 성능 테스트가 병목 공정으로 변하는 것을 확인할 수 있다.

<Table 3>은 K사의 1월 주문의 일부를 발췌하여 단순히 납기일 기준으로 정렬한 것이다. 예상 납기 여유(estimated slack time to due date)는 납기일에서 예상 작업 완료 시 각(estimated completion time)을 뺀 값이다. 이때, 예상 작 업 완료 시각은 플로우 라인을 활용한 추정식인 식 (4)를 활용한다.

현재 K사에서는 주로 주문서를 바탕으로 주문 순서를 재배열하지 않은 채로 연속되는 주문(로트)에 대해서만 배치를 형성하여 작업을 진행하였다. 즉, 기존의 방법을 <Table 3>의 예제에 적용하면 로트 2와 3, 로트 5와 6, 로 트 7~10을 각각 하나의 배치로 형성하여 작업을 진행하 였다. 하지만 작업 완료 시간을 고려하여 주문의 순서를 조정하며 배치를 형성한다면, 더욱 생산성 향상이 가능하 다. 아래 <Table 4>는 <Table 3>의 예제에 개발된 배치 알고리즘을 적용한 예시이다.

이와 같이, 제안된 배치 알고리즘을 적용하면 단순히 연속되는 주문으로만 배치를 형성하는 것이 아니라 납기 준수가 가능한 내에서 후속 주문들을 먼저 생성함으로써 배치의 크기를 늘리고, 아울러 생산성을 향상시킬 수 있 다. 위 예제에서는 로트 6~10을 앞당김으로써, 평균 배치 크기를 늘리고 생산시간 또한 절감할 수 있다.

K사의 2019년 1월~3월 데이터(총 188건의 주문)를 바탕 으로 제안된 배치 알고리즘을 적용한 결과는 아래 <Table 5>와 <Table 6>에 나타나 있다. 기존 방법은 앞서 설명한 바와 같이 납기일 기준으로 주문을 정렬한 후 연속된 주 문들만으로 배치를 형성하는 방법을 의미한다.

기존의 방식과 비교하여 평균 6.9%의 생산 시간(makespan) 절감 효과와 46.0%의 배치 사이즈 증대 효과가 있 음을 확인할 수 있다. 이는 생산 효율 증가, 납기 준수율, 실질 생산능력 증가로 이어질 수 있다.

5.2 H사의 판형 열 교환기를 위한 프레스 공정

본 장에서는 H사의 판형 열 교환기 생산 라인과 관련 자료를 바탕으로 배치 알고리즘을 적용하였다. H사에서 수행하는 제작 공정은 크게 비닐 코팅 작업, 프레스 성형 (Forming) 작업, 피어싱(Piercing) 작업, 마킹(Marking) 작 업, Gasket 본딩(Bonding) 작업으로 구성된다. 먼저 시스템 개선이 시급한 작업을 파악하기 위해 각 작업에 대한 공정 시간 분석을 실시하였다. H사에서는 21가지의 Plate 종류 를 취급하며, 이들을 공정 및 취급의 유사성에 대해 크게 7개의 타입(A, B, C, …, G)으로 나누어 제작 공정 시간을 분석한 결과는 <Figure 6>과 같다. 자세한 Plate 타입 및 시스템에 대한 설명은 Hwang[6]에서 참조할 수 있다.

대부분의 Plate 타입에 대해 프레스 공정이 가장 많은 시간이 소요되며, 전체 공정의 62.5%가 프레스 공정에 소요됨을 알 수 있다. 또한, 2대로 제한된 프레스 장비로 인해 프레스 공정의 효율성 증대가 시급하므로 본 연구 에서는 프레스 공정에 초점을 맞추어 연구를 진행하였 다. H사의 작업자들 또한 표준화된 방법이나 규칙 없이 생산관리자의 경험에 의존하여 일정 계획 수립되고 있 어, 개선의 필요성을 인식하고 있었다. 중소기업에서 프 레스 공정의 생산성을 향상시키기 위해 주로 프레스 생 산 속도(SPH, stroke per hour)를 향상시키거나 비가동 시 간을 줄인다. 하지만, 본 연구에서는 배치 알고리즘을 통 해 셋업의 횟수를 줄임으로써 생산성을 향상시키려 하였 다. 프레스 공정을 위한 금형 셋업은 상당한 시간이 소요 될 뿐만 아니라 작업자들의 편의성 및 안전과도 밀접한 관계에 있기 때문이다.

본 연구에서는 H사의 2019년 7월에서 9월까지의 180 개의 주문 데이터를 활용하여 프레스 공정 분석을 진행하 였다. H사는 10,000톤급 프레스 설비와 15,000톤급 프레스 설비를 사용하며(M = 2), 제품의 타입은 21가지(T = 21) 이다. 배치 알고리즘을 적용함에 있어 두 가지 제약조건 을 반영하였다. 먼저, 금형 홀더를 공유하는 일부 타입 (DH151, DH201 타입)은 동시에 작업을 공유할 수 없다. 둘째, 일부 타입(DH352 타입)은 15,000톤급 설비에서만 작업이 가능하다. 이러한 제약 조건들은 배치 알고리즘에 서 각 기계에 로트가 할당될 때 고려되었다.

<Table 7>은 알고리즘 적용 전후의 총 셋업 횟수, 제 품 종류당 평균 셋업 횟수, 평균 배치 사이즈의 개선율을 요약한 표이다.

H사는 2019년 7월에서 9월에 거쳐 총 33회의 셋업, 평 균 1.57회의 타입별 셋업, 평균 5.45개의 배치 사이즈를 가지고 있었다. 하지만 본 연구에서 도출된 배치 알고리 즘을 적용한 결과, 동일한 주문들에 대해 총 셋업 횟수는 27회로 18.2% 정도가 감소된 것을 확인할 수 있다. 이로 인한 총 작업시간의 감소는 계량화하지 못했지만, 한 번 의 셋업에 소요되는 시간이 수십 분에서 수시간임을 감 안할 때 총 작업시간에도 유의미한 감소가 있을 것으로 예상된다. 또한 작업자의 편의성과 안전성 또한 크게 향 상될 수 있다. 평균 배치 사이즈는 6.95개로 기존보다 27.5%가 증가하였으며, 이로 인한 납기 미준수 또한 발 생하지 않았다.

6. 결 론

본 논문에서는 다품종 제품들을 배치 생산 방식으로 생 산하는 유연생산시스템에 대한 연구를 진행하였다. 먼저, 플로우 라인 모델을 활용하여 직전 배치의 최종 작업 완료 시각만을 활용하여 다음 배치의 작업 완료 시각의 상한값 을 추정하는 식을 개발하였다. 또한, 이를 활용하여 다수의 생산라인 또는 다수의 기계로 이루어진 공정에서 납기를 준수하면서 배치 사이징 및 스케줄링 알고리즘을 개발하였 다. 이러한 알고리즘은 간단하고 직관적인 방법을 활용하 여 주문 또는 로트의 순서를 재배열하며 배치 사이즈를 증대시킴으로써 생산성을 향상시키려 하였다. 이러한 배치 사이즈의 증대는 생산성 향상뿐만 아니라, 셋업의 감소 등 을 통해 작업자의 편의성과 안전성도 증대시킬 수 있다.

도출한 알고리즘은 두 개의 실제 중소 생산 라인 시스템 과 데이터에 적용되었다. K사의 고압 절삭유 공급장치 (HPC)에 배치 알고리즘을 적용한 결과, 납기일을 준수하면 서도 기존 방식보다 배치 사이즈를 평균 46% 증가시킴으로 써 총 생산시간(makespan)을 평균 7% 감소시켰다. 이를 통 해 수주량을 증대시킴으로써 매출 증가의 효과를 기대할 수 있다. 또는 4명의 작업자가 이 공정을 담당하므로 연간 최대 약 582시간(4명×8시간/일×260일/년×0.07)의 노동시간 감소 또는 작업자의 업무 영역 확장을 통한 생산성 향상을 기대할 수 있다. H사의 프레스 공정 사례에서는 개발된 배치 알고리즘을 통해 평균 배치 사이즈를 27.5% 증가시키고 총 셋업 횟수를 18.2% 감소시킬 수 있었다. 프레스 공정은 특히 금형 교체 및 셋업에 많은 노력과 시간이 소요되므로 생산성과 작업자의 편의성을 향상시킬 수 있을 뿐만 아니라 작업자의 안전에도 긍정적인 영향을 가져올 수 있다.

하지만, 본 연구는 최적 스케줄링 방법론이 아니며, 비 교적 짧은 기간의 과거 실제 데이터를 바탕으로 테스트 한 결과이며 실제로 적용되어 운영해보지 못했음에 한계 점을 가진다. 향후에 다양하고 더 많은 중소기업에 적용 된다면 도출된 알고리즘의 효용성에 더욱 정확하게 평가 될 수 있을 것이라 기대한다.

Acknowledgement

This work was supported by the National Research Foundation of Korea(NRF) grant funded by the Korea government( MSIT) (No. 2018R1C1B5046069) and Pusan National University Research Grant, 2020.

Figure

<Figure 1>.

Flow Line Models

<Figure 2>.

Possible Completion Time Gap Between Batch k and k−1

<Figure 3>.

Batch Sizing and Scheduling Heuristics

<Figure 4>.

Processes for HPC

<Figure 5>.

Process Times with Respect to Batch Size

<Figure 6>.

Process Times Analysis

Table

<Table 1>.

Indexes and Parameters

<Table 2>.

Parameters for Process Time Equations

<Table 3>.

Original Lot Schedule Example

<Table 4>.

Lot Schedule Example after Applying Batch Sizing

<Table 5>.

Makespan Results for Batch Algorithm

<Table 6>.

Batch Size Results for Batch Algorithm

<Table 7>.

Performance Results for Batch Algorithm

Reference

Avi-Itzhak, B., A sequence of service stations with arbitrary input and regular service times, Management Science, 1965, Vol. 11, No. 5, pp. 565-571.
Burman, M., Gershwin, S.B., and Suyematsu, C., Hewlett- Packard uses operations research to improve the design of a printer production line, Interfaces, 1998, Vol. 28, No. 1, pp. 24-36.
Dallery, Y. and Stanley, B.G., Manufacturing flow line systems : a review of models and analytical results, Queueing Systems, 1992, Vol. 12, No. 1-2, pp. 3-94.
Friedman, H.D., Reduction methods for tandem queuing systems, Operations Research, 1965, Vol. 13, No. 1, pp. 121-131.
Glassey, C.R. and Weng, W.W., Dynamic batching heuristic for simultaneous processing, IEEE Transactions on Semiconductor Manufacturing, 1991, Vol. 4, No. 2, pp. 77-82.
Hwang, M.H., A case study on improving scheduling of pressing process for plate heat exchanger, [MS Thesis], [Busan, Korea] : Dong-A University, 2020.
Jang, B.Y., Moon, Y.H., and Hang, S.W., Manufacturing- based service R&D strategy : Manufacturing servitization service R&D, Science and Technology Policy Institute(STEPI) Report(2014-20), 2014.
Joe, J.J. and Gu, P.H., Comparing Lot Sizing Decision Method of Layout Processes with Simulation Analysis, KIIE, 2012, pp. 2701-2708.
Kim et al., The Fourth Industrial Revolution and the Return of Manufacturing, Cloud 9, 2017.
Kim, W.S. and Morrison, J.R., The throughput rate of serial production lines with deterministic process times and random setups : Markovian models and applications to semiconductor manufacturing, Computers and Operations Research, 2015, Vol. 53, pp. 288-300.
Kim, Y.S., Strategies for industrial competitiveness through manufacturing service, KERI Insight, 2016.
Kock et al., Lumped parameter modelling of the litho cell, Production Planning and Control, 2011, Vol. 22, No. 1, pp. 41-49.
Park, K. and Morrison, J., Performance bounds for hybrid flow lines : Fundamental behavior, practical features and application to linear cluster tools, 2012 IEEE International Conference on Automation Science and Engineering, IEEE, 2012, pp. 371-376.
Park, K. and Morrison, J., Performance Evaluation of Deterministic Flow Lines : Redundant Modules and Application to Semiconductor Manufacturing Equipment, 2010 IEEE International Conference on Automation Science and Engineering, 2010, pp. 45-50.
Lee, J.-Y. and Shin, M.S., A case study on application of dispatching rule-based advanced planning and scheduling( APS) system, Journal of Society of Korea Industrial and Systems Engineering, 2015, Vol. 38, No. 3, pp. 78-86.
Li, J. and Meerkov, S.M., Production systems engineering, Springer Science and Business Media, 2008.
Morrison, J.R., Multiclass Flow Line Models of semiconductor Manufacturing Equipment for Fab-Level Simulation, IEEE Transactions on Automation Science and Engineering, 2010, Vol. 8, No. 1, pp. 81-94.
Na, K.H., Kim, M.J., and Lee, J.H., Real-time batch size determination in the production line, Journal of Society of Korea Industrial and Systems Engineering, 2019, Vol. 42, No. 1, pp. 55-63.
Neuts, M.F., A general class of bulk queues with Poisson input., Annals of Mathematical Statistics, 1967, Vol. 38, pp. 759-770.
Seong, J.E., A case study on batch size scheduling for HPC assembly lines, [MS Thesis], [Busan, Korea] : Dong-A University, 2020.
Van De Rzee, D.J., Van Harten, A., and Schuur, P.C., Dynamic job assignment heuristics for multi-server batch operations-A Cost-Based Approach, International Journal of Production Research, 1997, Vol. 35, No. 11, pp. 3063-3094.
Weng, W.W. and Leachman, R.C., An improved methodology for real-time production decisions at batch-process work stations, IEEE Transactions on Semiconductor Manufacturing, 1993, Vol. 6, No. 3, pp. 219-225.
Wu, M.-C. and Chie-Wun, C., Scheduling semiconductor in-line steppers in new product/process introduction scenarios, International Journal of Production Research, 2010, Vol. 48, No. 6, pp. 1835-1852.