Journal Search Engine
Search Advanced Search Adode Reader(link)
Download PDF Export Citaion korean bibliography PMC previewer
ISSN : 2005-0461(Print)
ISSN : 2287-7975(Online)
Journal of Society of Korea Industrial and Systems Engineering Vol.35 No.3 pp.77-86
DOI :

제지 재제조 시스템에서의 자원제약을 고려한 로트 크기 결정 및 일정 계획에 대한 사례연구

김혁철*, 도형호*, 유재민*, 김준규*, 이동호**†
*한양대학교 산업공학과,
**한양대학교 산업공학과/기술경영전문대학원

A Case Study on Capacitated Lot-sizing and Scheduling in a Paper Remanufacturing System

Dong-Ho Lee**†, Hyeok-Chol Kim*, Hyoung-Ho Doh*, Jae-Min Yu*, Jun-Gyu Kim*
**Department of Industrial Engineering, Graduate School of Technology and Innovation Management, Hanyang University
*Department of Industrial Engineering, Hanyang University
Corresponding Author leman@hanyang.ac.kr
논문접수일:2012년 06월 11일 게재확정일:2012년 09월 07일

Abstract

We consider the capacitated lot-sizing and scheduling problem for a paper remanufacturing system that produces several types of corrugated cardboards. The problem is to determine the lot sizes as well as the sequence of lots for the objective of minimizing the sum of setup and inventory holding costs while satisfying the demand and the machine capacity over a given planning horizon. In particular, the paper remanufacturing system has sequence-dependent setup costs that depend on the type of product just completed and on the product to be processed. Also, the setup state at one period can be carried over to the next period. An integer programming model is presented to describe the problem. Due to the complexity of the problem, we modify the existing two-stage heuristics in which an initial solution is obtained and then it is improved using a multi-pass interchange method. To show the performances of the heuristics, computational experiments were done using the real data, and a significant amount of improvement is reported.

SOGOBO_2012_v35n3_77.pdf1.05MB

1. 서 론

 기업 간의 경쟁이 심화되고 소비자의 기대수준이 높아지면서 제품의 수명주기는 짧아지는 등 다양한 불확실성에 직면하고 있다. 제조 산업은 타 산업에 비해 더 치열한 경쟁이 발생하며 제품 인도기간이 서비스 품질에 큰 영향을 차지하여 고객과 공급자간의 새로운 관계가 필요해 짐에 따라 보다 합리적이고 신속한 의사결정을 지원하는 정보 시스템 기반의 스피드 경영이 더욱 중요하게 되었다. 특히, 장치산업의 경우 자본집약적이며 자금의 회전기간이 길고 운전자금이 많이 소요되어 타 산업에 비해 수익성이 낮다고 할 수 있다. 그 이유로 수요증가와 설비증가가 불일치하여 수요초과, 공급초과 현상이 반복되는 특성이 있다. 그 중 본 연구에서 대상으로 하는 제지산업은 주 원재료인 펄프의 해외 의존도는 2010년 기준으로 87%로 매우 높아 원재료의 안정적인 공급이 경쟁력의 결정요인이라고 할 수 있다. 또한, 일반적인 경기 동향에 따라 종이 수요가 크게 좌우되며 공급과잉 시 현금유동성이 취약하다. 그리고 제지업의 경우 GDP 수준에 비례하여 성장하는 특성이 있고 부피가 매우 크므로 재고유지 비용이 높고 수송비가 과다하여 내수 중심인 특징이 있다. 따라서 각 기업 내에서는 주문에 대하여 납기 만족을 달성하면서 경쟁사보다 빠른 인도기간으로 납품함과 동시에 생산 비용을 최소화 할 수 있는 효율적인 생산 시스템의 개발이 절실하다.

 본 논문에서는 고지를 수거한 후 재처리를 통하여 포장용 골판지를 생산하는 D 제지회사 재제조 시스템(remanu-facturing system)의 운영 효율화 방안을 제시하는 것을 주목적으로 한다. 재제조란 수명이 다한 제품을 적절한 재생공정들을 통해 성능과 품질이 신제품과 동일하거나 더 우수한 제품을 만드는 것을 의미하며 부가가치를 창출하는 제품복구라는 의미에서 가장 상위 수준의 재사용 형태로 볼 수 있다. 일반적으로 재제조가 주요한 연구분야로 최근 각광을 받기 시작한 이유로 경제적인 측면에서는 재제조를 통하여 얻는 이익이 비용을 초과하여 새로운 사업 분야가 될 수 있다는 점과 환경적인 측면에서는 원자재 및 에너지 소비를 줄일 수 있다는 점을 들 수 있다. 

먼저, 라이너지, 골심지, 이면지로 구성되는 골판지의 구조를 간단히 살펴보면 <그림 1>과 같으며 본 연구에서 대상으로 하는 D 제지의 경우에 용도, 생산재료 및 생산방법에 의해 크게 총 4가지 종류의 제품을 생산한다. 

<그림1> 골판지의 구조

D 제지의 생산시스템은 크게 화학, 석유정제 및 전력 등과 같은 연속생산공정에 해당하는 장치산업으로 볼 수 있으며 고지를 수거하여 재처리한 골판지를 생산한다는 점에서는 재제조 시스템으로 분류할 수 있다. 연속생산공정의 특성상 제품은 표준화되어 있으며 제품의 흐름이 아래의 <그림 2>와 같이 정해진 작업순서에 따라 한 작업장에서 다음 작업장으로 직선적으로 일관되게 흘러간다. 또한, 각 제품에 필요한 공정들은 서로 밀접하게 연결되어 있으며 병목공정이 없이 전체적으로 공정균형이 잘 잡혀 있어 크게 단일설비로 간주할 수 있다. 그리고 공정의 유지보수와 관련된 작업을 제외하고 일일 3교대로 24시간 연속적으로 설비를 가동하고 있다. 또한, 생산제품의 변경 시 작업순서에 종속인 작업준비가 발생한다. 그리고 각 제품의 수요는 매우 동적이며 다수제품의 수요가 동시에 발생한다. 

본 논문에서는 앞에서 설명한 D 제지 재제조 시스템의 운영합리화를 위한 다양한 주제 중 생산 및 일정계획 문제를 다루고 있다. 흔히 적시생산 방식은 효율적인 시스템이라고 알고 있으나 대부분의 많은 제조회사에서는 현실적으로 높은 작업준비 비용과 작업준비 시간이 발생하여 생산성이 크게 떨어질 수 있으며 이 경우 전체적인 작업준비관련 비효율을 줄이기 위하여 여러 기간의 수요를 만족하는 로트 단위 생산을 해야 한다. 본 연구 대상인 D 제지의 경우도 작업순서 종속 작업준비 비용과 작업준비 시간이 발생하고 있으며 적절한 생산 및 일정계획을 통하여 작업준비 비용 및 재고비용의 합을 최소화하고자 한다. 구체적으로는 다양한 생산 및 일정계획 문제들 중 D 제지회사의 상황에 가장 적합하다고 판단된 로트 크기 결정 및 일정계획 문제(lot-sizing and scheduling problem)를 다루었다. 

<그림2> 골판지 제조 공정 : D 제지의 경우

본 연구에서 다루는 로트 크기 결정 및 일정계획 문제에 대한 기존연구는 크게 계획시평(planning horizon)에서 기간(period)의 크기와 특성에 따라 몇 가지 유형으로 나누어 볼 수 있다. 먼저, capacitated lot-sizing and scheduling problem(CLSP)은 계획시평 내 한 기간의 길이가 다른 유형 보다 상대적으로 길어 한 기간 내에 다수의 제품을 생산할 수 있는 형태이며 discrete lot-sizing and scheduling problem(DLSP)은 한 기간에 작업준비, 유휴 혹은 한 제품만을 생산할 수 있는 경우이며 proportional lot-sizing and scheduling problem(PLSP)은 DLSP와 마찬가지로 한 기간에 작업준비, 유휴 혹은 생산 중 하나의 활동만 가능하나 두 가지 제품의 생산이 가능한 경우를 다루고 있다. 이상의 기본적인 분류 이외에 작업준비 비용 및 시간의 작업순서 종속여부에 따라 추가적으로 문제를 분류할 수 있다. 위와 같은 분류기준을 포함한 로트크기 결정 및 일정계획 문제 관련 기존연구는 Drexl and Kimms[2]를 참고하기 바란다.

 본 연구에서 다루고 있는 로트크기 결정 및 일정계획 문제와 유사한 문제를 다루는 사례연구들을 정리하면 다음과 같다. 먼저, Haase and Kimms[5]는 스캐너, 프린터, 라이노타이프 등의 기술 집약적 기계를 만드는 회사에서의 로트크기 결정 및 일정계획 문제를 다루었으며 작업순서에 종속인 작업준비 비용과 작업준비 시간을 고려하고 있다. 이 논문에서는 새로운 혼합정수계획 모형을 제안하였으며 해법으로는 분지한계법에 기반을 둔 최적 알고리듬을 제안하였다. Gupta and Magnusson[3]은 사포생산 공장의 로트 크기 결정 및 일정계획 문제를 다루었으며 기존의 CLSP에 작업준비 비용이 작업순서에 종속적이고 작업준비 시간이 있으며 각 기간말의 작업준비 상태의 보존이 가능한 상황을 고려하였으며 혼합정수계획 모형 및 발견적 기법을 제안하였다. 이상의 사례연구와 달리 제지 회사에서의 로트 크기 결정 및 일정계획 문제를 다룬 논문으로 Bouchriha et al.[1]이 있으며 이 논문에서는 캐나다의 한 제지회사를 대상으로 대상 로트 크기 결정 및 일정계획 문제를 기본적으로는 공통의 주기를 갖는 CLSP에 작업순서에 종속인 작업준비 비용을 고려한 문제로 보고 관련 정수계획 모형을 제안하고 LINGO를 이용하여 문제를 해결하였다. 이 논문의 경우 제지회사를 대상으로 하며 동적인 수요를 고려한다는 측면에서는 본 연구와 유사점이 있으나 일정한 주기성을 갖는다는 측면에서 본 연구와 차이가 있다.

다음으로 본 연구에서 대상으로 하는 단일설비에서의 작업순서 종속 작업준비 비용을 고려하는 CLSP에 대한 이론연구로 Hasse[4]는 이 문제에 대한 정수계획 모형을 개발하고 간단한 역방향 기반의 발견적 알고리듬을 제안하였고 기존의 알고리듬보다 우수함을 계산실험을 통하여 보였다. 그리고 이 문제에 대한 최신논문으로써 Shim et al.[7]은 역방향 및 순방향 개선을 기반으로 하는 2단계 발견적 기법을 제안하였고 실험결과 기존 Hasse[4]의 방법보다 우수함을 보였다. 그 밖에 작업순서 종속 작업준비를 고려하는 로트 크기 결정 및 일정계획 문제에 대한 문헌연구는 Zhu and Wilhelm[9]을 참조하기 바란다. 

본 논문에서는 제지회사 재제조 시스템을 대상으로 주어진 계획시평 동안 기간 별 수요 및 해당 납기를 만족하며 작업순서 종속 작업 준비 비용과 재고유지 비용의 합을 최소화하는 로트 크기 및 작업순서를 결정하는 문제를 다룬다. 구체적으로 단일 기계에서의 CLSP로 볼 수 있으며 작업준비 비용이 작업순서에 종속적인 경우를 고려하고 있다. 또한, 작업준비 상태의 이월을 허락한다. 본 논문에서는 먼저 대상 문제를 명확히 표현하기 위하여 Hasse[4]가 제안한 수리적 모형을 설명하고 최신의 Shim et al.[7] 2단계 발견적 기법을 D 제지회사 실제 사례에 적용하고 그 결과를 제시한다. 

2. 문제 정의

 본 논문에서는 주어진 계획시평 동안 각 기간의 생산용량을 만족하며 작업순서 종속 작업준비 비용과 재고유지 비용의 합을 최소화하는 로트 크기 및 작업순서를 결정하는 문제를 다루고 있으며 이 문제는 기본적으로 단일설비 하의 CLSP로 볼 수 있다. 여기서, 로트 크기란 한 번의 작업준비로 생산할 제품의 생산량을 의미하며 작업순서는 구성된 로트들의 생산 순서를 의미한다. 또한, 작업준비 비용은 해당 작업을 수행하기 위하여 설비를 준비하는데 드는 비용으로 해당 설비에서 수행되는 작업순서에 의존한다. 그리고 재고유지 비용이란 재고를 보유하는데 드는 비용으로 로트 크기에 대하여 작업준비 비용과 상충관계에 있다. 즉, 로트 크기가 작아 작업준비가 빈번하게 발생할 경우 재고량은 줄어드나 작업준비 비용이 증가하게 되며 그 반대의 경우 재고량이 늘어 재고유지비가 늘어나게 된다.

 본 연구에서는 임의의 기간 마지막에 생산되어지는 제품과 그 기간 다음 기간의 처음 생산되어지는 제품이 동일한 경우와 임의의 제품을 생산하다가 중간에 유휴시간이 발생하더라도 유휴시간 후에 동일한 제품을 생산하는 경우 추가적인 작업준비 비용이 발생하지 않는다. 그리고 작업준비 시간의 경우 D 제지회사의 경우 평균 작업준비 시간을 생산 시간에 반영하므로 본 연구에서는 추가적인 작업준비 시간은 고려하지 않는다. 그 밖의 다른 가정 및 제약사항들을 정리하면 아래와 같다.

·전체 계획시평은 1년 각 기간은 1일로 두었다.
·각 제품의 납기는 반드시 만족되어야 한다. 즉, 각 제품의 추후납품과 품절과 같은 재고부족은 허용되지 않는다.
·로트 크기의 상/하한의 제한은 없다.
·장비의 고장 및 유지보수로 인한 시간손실은 고려하지 않는다. 

본 연구에서 대상으로 하는 문제는 다음과 같은 혼합정수계획 모형으로 표현할 수 있다[4]. 먼저, 기호들을 정리하면 아래와 같다.

첨자(indices)
  i, j, k 제품, i, j, k = 1, 2, … N
  t       기간, t = 1, 2, … T
  init   초기 작업준비 상태

자료(parameters)
  sij   제품 i에서 제품 j로의 변경 시 작업준비 비용
  djt   기간 t에서 제품 j의 수요
  h  제품 j의 단위 및 단위기간 당 재고유지 비용
  pj   제품 j의 단위 당 생산시간
  C  기간 t의 생산능력(시간)

결정변수(decision variables)
  qjt  기간 t에서 제품 j의 생산량
  Ijt  기간 t말 제품 j에 대한 재고량 
  xijt  기간 t에서 제품  생산 후 연속해서 제품 j가 생산되면 1, 아니면 0
  zjt  기간 t말 제품 j에 대한 작업준비가 발생하면 1, 아니면 0
  fjt  작업순서에 대한 보조 변수. fjt  값이 클수록, 해당 j의 제품을 기간 t의 마지막에 생산.   

 이상의 기호를 이용하여 대상 문제를 혼합정수계획으로 표현하면 아래와 같다.

먼저, 목적함수는 주어진 계획시평 동안 작업순서 종속 작업준비 비용과 재고유지 비용의 합을 최소화하는 것을 나타낸다. 다음으로 제약식 (1)은 각 기간 말의 재고수준을 나타내며 제약식 (2)는 생산용량의 제약을 나타낸다. 제약식 (3)은 한 제품의 생산 전에는 반드시 해당 제품에 해당되는 작업준비가 발생되어야만 한다는 것을 표현하며 제약식 (4)는 한 기간의 마지막에는 한 특정한 제품에 대한 기계의 작업준비가 반드시 발생한다는 것을 나타낸다. 제약식 (5)는 작업준비의 상태에 관한 제약으로 기간 t-1 과 기간 t에서 임의의 제품 k에 대한 작업준비 발생여부를 나타낸다. 즉, 기간 t-1 에서 제품 k가 작업순서의 마지막에 할당되었을 때 기간 t에서 제품 k가 작업순서의 첫 번째에 할당되거나 또는 기간 t에서 제품 k 하나의 제품만 할당되어야 한다. 다시 말해 연속된 두 기간사이에 작업순서를 최소화하도록 해주는 제약조건이다. 제약식 (6)은 작업순서에 subtour를 방지하는 제약이다. 예를 들어 기간 t에서 부분적인 작업순서(…, i, j, k, …)가 주어져 있을 때(xijt  = xjkt  = 1), fjt  = fit  + 1 및 fkt  = fjt  + 1가 만족되며 이에 따라 fkt  = fit  + 2가 된다. 이에 따라, i ≠ k, j ≠ k 및 i ≠ k가 되어 subtour가 방지된다. 마지막으로, 나머지 제약조건들은 변수에 관한 제약을 나타낸다.

 위에서 설명한 로트 크기 및 작업순서를 결정 문제는 적정 시간 내에 최적해를 구하기가 매우 어려운 문제로 이미 알려져 있다. 다만, 소규모 문제(제품의 종류가 적고 계획기간이 짧은 문제)에 대해서는 앞의 혼합정수계획모형을 상용패키지를 이용하여 최적해를 구할 수 있으나 대상 제지회사 문제의 경우 제품은 네 가지 종류를 고려하고 있지만 전체 계획시평이 365일로 1일의 기간으로 나누어져 있어 대규모 문제로 간주될 수 있으므로 수리모형을 직접 적용하여 최적해를 구하는 것은 매우 어렵다. 따라서 본 연구에서는 Shim et al.[7]의 발견적 기법을 적용하고 실제로 적용한 계획 대비 개선정도를 기준으로 성능을 평가하였다.

<표1> 순서종속 작업준비 비용(단위 : 원)

3. 해 법

본 논문에서 차용한 Shim et al.[7]의 해법은 초기해 생성과 개선으로 구성되는 2-단계 발견적 알고리듬으로 전체적인 개요를 표현하면 <그림 3>과 같다. 

여기서 전처리 과정에서는 기존연구인 Shim et al.[7] 과는 다르게 모든 작업순서별 작업준비 비용을 미리 계산한다. 이는 사례연구로써 본 연구에서 실제 자료를 기준으로 자세한 작업종속 작업준비 비용을 알 수 있기 때문에 기존연구의 일반화된 전처리 과정이 불필요하다.  위의 <표 1>은 본 연구에서 대상으로 하는 D 제지회사의 네 가지 제품에 대한 순서종속 작업준비 비용들을 나타낸다. 다음으로, 알고리듬의 첫 번째 단계에서 각 기간의 생산용량과 각 제품의 수요량을 고려하면서 각 기간 내에서 작업준비 비용이 최소화되도록 작업순서와 생산량을 결정하여 초기해를 구하게 된다. 그리고 두 번째 단계에서 첫 번째 단계에서 구한 초기해를 여러 우선순위 규칙을 적용하여 총비용(작업준비 비용+재고유지 비용) 측면에서 개선한다. 구체적인 알고리듬에 대한 설명은 다음과 같다. 

<그림3> 2-단계 알고리듬 개요

3.1 전처리

 전처리 단계에서는 초기재고를 반영한 실제 수요를 구하고 제품들에 대한 발생 가능한 순서별 순서종속 작업준비 비용을 미리 계산한다. 먼저, 초기재고를 반영한 실제 수요를 구하기 위하여 계획시평 초의 초기재고를 이용하여 초기 계획기간(들)의 수요를 만족시켜 주며 해당 수요를 수정한다. 구체적으로 수요를 수정하는 과정은 아래와 같으며 각 제품 별로 처음부터 마지막 기간까지 순차적으로 진행한다.

·Ii,0 = 0 인 경우 : 변동 없음
·Ii,0 > 0 인 경우
①Ii,0 > di,t 인 경우 : 해당기간의 수요는 0으로 계획시평 초기의 재고는 I'i,0 = Ii,0 - di,t로 수정
②Ii,0 ≤ di,t  인 경우 : 해당기간의 수요를 d'i,t =di,t - Ii,0로 수정하고 계획시평 초기재고가 0이 됨(여기서, d'i,t 은 현재까지 남은 초기재고를 나타냄)

다음으로 각 계획기간 내에서 생산할 제품들의 생산순서를 결정하기 위하여 제품들에 대한 순서별 순서종속 작업준비 비용을 미리 계산한다. 다만, 제품의 종류가 많아 <표 1>과 같이 미리 계산된 자료를 활용하기 어려울 경우 Shim et al.[7]의 발견적 기법을 그대로 적용할 수 있다.  

3.2 초기해 생성

본 연구에서 사용된 초기해는 앞의 전처리에서 미리 계산한 순서종속 작업준비 비용에 따라 각 계획기간에서 최소의 작업준비 비용을 가지는 작업순서를 결정하고 그에 따른 로트 크기를 결정하는 방법으로 구하였다. 단, 로트 크기 결정 시 각 기간 내의 생산용량을 만족하고 재고부족을 허용하지 않도록 하며 마지막 계획기간에서 첫 번째 계획기간으로 남은 누적 수요를 만족시키는 역방향(backward) 기반 방법이다.

본 연구에서 사용된 초기해는 앞의 전처리에서 미리 계산한 순서종속 작업준비 비용에 따라 각 계획기간에서 최소의 작업준비 비용을 가지는 작업순서를 결정하고 그에 따른 로트 크기를 결정하는 방법으로 구하였다. 단, 로트 크기 결정 시 각 기간 내의 생산용량을 만족하고 재고부족을 허용하지 않도록 하며 마지막 계획기간에서 첫 번째 계획기간으로 남은 누적 수요를 만족시키는 역방향(backward) 기반 방법이다.  

·대상 기간 t의 다음 기간 t+1에 최초로 생산되는 제품을 기간 t에서 생산하지 않는 경우 : 다음 기간 t+1의 최초 생산 제품이 마지막에 할당되었다고 가정하고 이를 포함한 제품들에 대해 최소 작업준비 비용을 가지도록 작업순서 결정
·대상 기간 의 다음 기간 t+1에 최초로 생산되는 제품을 기간 t에서 생산할 경우 : 다음 기간 t+1에 최초로 생산되는 제품과 동일한 제품을 대상 기간 t의 마지막에 할당하고 나머지 제품들은 최소 작업준비 비용을 가지도록 작업순서 결정 

 다음으로, 로트 크기를 결정하는 방법은 각 기간의 수요량과 생산용량의 상대적인 크기에 따라 아래와 같이 두 가지 경우로 나눈다. 첫 번째 경우는 기간 t에 모든 제품에 대한 남은 누적 수요의 필요용량이 기간 t의 가용용량보다 작거나 같은 경우를 두 번째 경우는 그렇지 않은 경우를 나타낸다.

·인 경우 : 각 제품의 수요량을 로트 크기로 둠
·인 경우 : 주어진 제품 순서의 마지막 제품부터 기간 의 용량이 허락하는 만큼 할당하고 초과되는 제품의 수요는 기간 로 이월 

이상의 두 단계를 거쳐 구한 해는 각 기간 내에서 작업준비 비용이 최소화되는 가능해가 되며 이를 초기해로 둔다. 앞에서 설명한 초기해를 생성하는 방법을 단계별로 설명하면 다음과 같다.   

절차 1. (초기해 생성)
단계 1 : t = T(마지막 계획기간)으로 둔다.
단계 2 : 기간 t 에서 마지막 기간까지 모든 제품에 대한 남은 누적 수요량(수요량-생산량)을 계산하여 기간 t의 용량(Ct  )과 비교한다. 

·기간 t의 모든 제품에 대한 남은 누적 수요량이 기간 의 용량보다 작거나 같은 경우
 
 기간 t에서 생산해야 할 제품들의 작업순서를 전처리과정을 이용하여 할당한다. 

·기간 t의 모든 제품에 대한 누적 수요량이 기간t 의 용량보다 큰 경우
 
 전처리과정을 이용하여 구한 기간 t에서 작업순서의 마지막부터 할당하고 해당 로트 크기를 기간 t의 남은 용량(ACt )이 허락하는 만큼 할당한다.

<그림4> 역방향 개선

단계 3 : t = t-1로 둔다. 만약 t<1 이면 알고리듬을 종료하고 그렇지 않으면 단계 2로 간다.  

3.3 개선

 앞에서 구한 초기해는 각 기간 내에서의 작업준비 비용은 최소화하고 있지만 전체 계획기간에서는 불필요한 작업준비 비용이 많이 발생한다. 따라서 개선단계에서는 전체 계획기간에 걸쳐 작업준비 비용과 재고유지 비용의 합을 최소화시키는 방향으로 초기해를 수정한다. 이를 위하여 계획시평의 마지막 기간부터 첫 기간까지 순차적으로 개선을 고려하는 역방향 개선(backward improvement)과 그 반대인 순방향 개선(forward improvement) 방법을 순차적으로 적용하며 각 방법에 대한 자세한 설명은 다음과 같다.

(1) 역방향 개선
 이 방법은 현재의 주어진 해의 서로 다른 두 기간 u와 v(u < v)에서 후 기간(v)에 할당된 제품을 선 기간(u)으로 생산용량 제약을 고려하면서 이동시키는 방법으로 해의 변경 후 증가되는 재고유지 비용과 감소되는 작업준비 비용을 고려하여 총비용이 감소하는 경우 후 기간의 해당 제품에 대한 생산량은 전부를 이동시키고 선 기간의 해당 제품에 대한 생산량은 일부를 이동시키며 해를 개선한다(역방향 개선방법에 대한 개략적인 내용은 아래의 <그림 4>와 같다). 이는 제품의 이동으로 재고유지 비용이 증가할 수도 있으나 재고유지 비용보다 상대적으로 큰 작업준비 비용을 감소시켜 전체적으로 비용을 줄이고자 하는 방법이다. 이 방법에서는 후 기간에 선택된 제품의 생산량의 전부를 옮기는 방식을 사용하는데 그 이유는 해당 제품의 생산량 전부를 이동시켜야 작업준비 횟수가 감소하기 때문이다.

 역방향 개선방법에 대하여 구체적으로 설명하면 다음과 같다. 후 기간(v)에 할당된 제품들 중에 한 제품을 선택하고 선 기간(u)에서 여유 생산용량이 존재하며 선택된 제품이 선 기간(u)에 할당되어 있으면 해당 제품의 생산량 전부를 선 기간(u)으로 이동시킨다. 이때, 후 기간(v)에서 어떤 제품을 선택할 지를 나타내는 제품들 간의 우선순위를 결정해야 한다. 이를 위하여 기존 연구에서는 아래와 같은 세 가지 우선순위 규칙을 제안한다.

·MINPT(minimum processing time) : 생산에 소요되는 시간이 가장 짧은 제품을 선택
·MAXSC(maximum setup cost) : 작업준비 비용이 가장 큰 제품을 선택
·MINTIC(minimum total inventory holding cost) : 재고유지 비용이 가장 작게 발생하는 제품(재고량과 재고유지 비용의 곱)을 선택

<그림5> 순방향 개선

 반면, 선 기간(u)에서 여유 생산용량이 존재하지 않으면 선 기간(u)의 생산용량 제약을 고려하지 않으며 선택된 제품을 이동시키고 선 기간(u)의 생산용량 제약을 만족시키기 위해 선 기간(u)에 할당된 제품 하나를 선택하고 해당 제품을 선 기간(u)으로부터 후 기간(v) 사이의 모든 기간(u, u+1,… , v-1 )에 대해서 여유 생산용량을 고려하여 각 기간에 들어갈 수 있는 양만큼 분할하여 이동시킨다. 여기서, 후 기간(v)에서 선택된 제품의 이동량은 앞에서 설명한 바와 같이 후 기간(v)에서의 작업준비 비용을 줄이기 위하여 후 기간(v)에서 생산하는 제품의 양 전체로 둔다. 또한, 선 기간(u)에 할당된 제품이 다음기간(u+1)부터 후 기간(v) 사이의 기간(u+1, …, v)으로 분할 이동하므로 재고부족이 발생할 수 있다. 그러므로 재고부족이 발생하지 않기 위해서는 이동되는 양이 두 기간 사이의 모든 기간(u, u+1,… , v-1 )에 대해서 해당 제품의 재고량보다 작거나 같은 값을 가져야 한다. 여기서, 선 기간에서 후 기간으로 이동시킬 제품에 대한 우선순위 결정을 위해서 다음과 같은 세 가지 방법을 제안한다.

·MAXIC(maximum inventory holding cost) : 단위 재고유지 비용이 가장 큰 제품을 선택
·MAXTIC(maximum inventory holding cost) : 재고유지 비용이 가장 크게 발생하는 제품(재고량과 재고유지 비용의 곱)을 선택
·MINPT(minimum processing time) : 생산에 소요되는 시간이 가장 짧은 제품을 선택 

(2) 순방향 개선
 이 방법은 앞의 역방향 개선에서 선 기간(u)에서 후 기간(v)으로 생산량을 이동시키는 방법과 유사하며 재고유지 비용을 감소시키기 위하여 선 기간(u)에서 선택된 제품의 생산량을 후 기간(v)으로 분할 할당한다(순방향 개선방법에 대한 개략적인 내용은 아래의 <그림 5>와 같다). 단, 계획시평의 첫 번째 기간에서부터 마지막 기간까지 순차적으로 고려되며 앞의 역방향 개선에서와 같이 순방향 개선 중 재고부족이 발생하지 않도록 하기 위해서 선 기간(u)에서 후 기간(v)으로 이동되는 생산량이 선 기간(u)과 후 기간(v) 사이의 모든 기간에 대한 재고량보다 작거나 같은 값을 가져야 한다. 그리고 선 기간에서 이동할 제품을 선택할 때는 앞에서 설명한 MAXTIC, MAXIC 및 MINPT 규칙을 사용한다.

 이상의 개선방법들을 기반으로 본 연구에서 사용하는 Shim et al.[7]의 개선 알고리듬을 구체적으로 설명하면 다음과 같다. 단, 아래의 개선 알고리듬은 역방향 개선의 9 가지 제품선택 우선순위 조합 및 순방향 개선에서 세 가지 제품선택 방법의 조합으로 27가지의 알고리듬으로 정리할 수 있다.

절차 2. (개선 알고리듬)
단계 1 : t = T로 둔다.
단계 2 : (역방향 개선)
2.1) r = t-1로 둔다. 만약 t<1으면 단계 3으로 간다.
2.2) 주어진 제품선택 우선순위 규칙을 이용하여 기간 t에서 제품 i ∈Ht 를 선택하고 기간 r에서 제품 j ∈Fr 를 선택한다. 
2.3) ACr ≥ pi qi,t 이면 제품 i에 대해 후 기간에서 선 기간으로 개선을 수행하고 i를 Ht 에서 제외한다. 그렇지 않으면 단계 2.5로 간다.
2.4) t = t-1로 두고 단계 2.1로 간다.
2.5)pj djr  +  AC ≥ pi di,t 이면 제품 i와 제품 j에 대하여 후 기간에서 선 기간 및 선 기간에서 후 기간으로의 개선을 수행하고 i를 Ht 에서 j를 Fr 에서 각각 제외한 후 단계 2.4로 간다. 그렇지않으면  j를 Fr 에서 제외시킨다. 
2.6) 만약 Fr ≠ ø 이면 단계 2.5로 간다. 그렇지 않다면 r = r-1로 두고 단계 2.3으로 간다.
단계 3 : (순방향 개선)
3.1) t = 1로 둔다.
3.2) s = t+1로 둔다.
3.3) 주어진 제품선택 우선순위 규칙을 이용하여 제품 k ∈Wt 를 선택한다. 만약 ACs > 0 이면 아래의 식을 이용하며 기간 t에서 s로 이동시킬 생산량을 결정하고 개선을 수행한다.

3.4) 만약 기간 t에 제품 k의 생산량이 남아있다면 s = s+1 두고 단계 3.3으로 간다. 여기서, s < 1 이거나 기간 t에 제품 k 의 생산량이 남아있지 않다면 k를 Wt 에서 제외하고 단계 3.3으로 간다. 만약 Wt = ø 이면  t = t+1로 두고 단계 3.2로 간다. 

<표2> 계산실험 결과

4. 계산실험

앞에서 차용한 알고리듬들의 성능을 검증하기 위하여 대상 제지회사의 실제 생산데이터를 이용하여 실험을 수행하였고 그 결과를 본 절에서 설명한다(본 연구에서는 실제 수요 데이터를 사용하고자 하였으나 차용한 알고리듬은 수요데이터에 해당하는 양만큼만 생산하기 때문에 실제 생산과 비교하기가 어려웠다. 이에 따라 실제 생산 데이터를 수요 데이터로 두고 제지회사에서 생산한 양과 동일한 양을 생산하면서 비용을 감소시키는 효과를 보이면 차용된 방법론이 현재 생산방식보다 개선된 값을 준다는 것을 보여줄 수 있다고 판단하였다).

앞에서 설명한 바와 같이 본 연구에서는 네 가지 제품을 고려하고 있으며 재고유지 비용의 경우 대상 제지회사에서 재고유지 비용을 산정하지 않고 있어 본 실험에서는 재고유지 비용을 세 가지 수준(상 : 제품 단가의 30~40%, 중 : 제품 단가의 20~30%, 하 : 제품 단가의 10~20%)으로 구분하여 각각 50문제씩 총 150문제를 생성하여 실험을 수행하였다. 그리고 여기서 기간별 재고유지 비용은 연간 재고유지 비용을 기간 수 365로 나눈 값을 사용한다. 또한 각 제품별 작업준비 비용과 생산 시간과 초기재고는 회사의 실제 데이터를 사용하였고 전체 계획 시평의 크기는 1년 각 기간은 1일로 두고 각 기간의 용량은 1440분으로 두고 실험을 하였다. 

 본 연구에서 사용되는 27개의 규칙조합에 대한 실험 결과는 <표 2>에 정리하였다. 본 실험에서 사용된 평가 척도로는 제지회사의 실제 생산비용대비 개선 정도 백분율(percentage improvement)과 계획시평 전체의 작업준비 횟수 그리고 계산시간으로 두었다. <표 2>에 정리한 결과에서 알 수 있듯이 초기해를 구하는 방법의 경우 기존의 생산비용보다 재고유지 비용이 하일 때 평균 6.5%, 중일 때는 평균 5.4% 그리고 상일 때 평균 4.8% 정도 좋지 않은 결과를 주었다. 하지만, 초기해를 개선한 27가지의 알고리듬은 기존보다 평균적으로 약 30% 이상이 더 개선된 결과를 주었다. 구체적으로, 재고유지 비용이 하위인 경우 제품선택의 우선순위 규칙으로

·역방향 개선 : 후 기간에서는 MINPT, 선 기간에서는 MINPT
·순방향 개선 : MAXIC  

을 조합한 알고리듬이 기존 생산비용보다 약 31.35%로 가장 높은 개선을 나타내었으며 재고유지 비용이 중간인 경우

 ·역방향 개선 : 후 기간에서는 MAXTIC, 선 기간에서는 MINPT
·순방향 개선 : MAXIC을 조합한 알고리듬이 약 33.4%의 개선정도를 나타내었다. 그리고 재고유지 비용이 상위인 경우
·역방향 개선 : 후 기간에서는 MAXTIC, 선 기간에서는 MINPT
·순방향 개선 : MINPT

 을 조합한 시나리오가 기존 생산비용보다 약 34.7%의 개선정도를 나타내었다. 그리고 평균 작업 준비 횟수 측면에서도 기존방식은 230번의 작업 준비가 발생하였으나 차용된 방법론은 최소 163.9번에서 최대 189.8번 사이에서 작업 준비 횟수가 발생하여 작업 준비 비용측면에서 많은 개선효과가 있다는 것을 알 수 있었다. 마지막으로 본 연구에서 사용한 2단계 발견적 기법은 평균 5초안에 모든 문제에 대한 해를 주어 현장 생산관리자가 긴급 상황에 보다 신속하게 대처할 수 있다는 장점을 제공하며 현실적인 생산관리 시스템을 설계하는데 있어 기본해법으로 사용될 수 있다는 것을 의미한다.

5. 결 론

본 연구에서는 연속생산 방식의 라인 공정을 따르는 제지회사 재제조 시스템에 대한 로트 크기 결정 및 일정 계획 문제를 다루었으며 구체적으로 주어진 계획시평 동안 기간별 수요 및 해당 납기를 만족하며 작업순서 종속인 작업준비 비용과 재고유지 비용의 합을 최소화 하는 capacitated lot-sizing and scheduling problem(CLSP) 형태로 접근하여 문제를 정의하고 관련 해법을 기존연구에서 차용하여 실제 생산계획과 성능비교를 하였다. 본 논문에서 사용한 해법은 각 기간의 생산 용량과 각 제품의 수요량을 고려하면서 각 기간 내의 작업준비 비용이 최소화되도록 하는 초기해를 구하고 전 단계에서 구한 초기해를 작업준비 비용 측면에서 개선하는 기존연구의 Shim et al.[7]의 2단계 알고리듬을 차용하였다. 차용한 알고리듬의 성능을 평가하기 위해서 대상 제지회상의 실제 데이터를 이용하여 계산 실험을 수행하였으며 계산 결과 기존 제지회사의 생산방식으로 구한 비용보다 평균적으로 약 30% 이상을 개선되었고 작업준비횟수 측면에서도 많은 개선 효과를 보였으며 계산시간도 5초를 넘지 않았다. 따라서 대상 제지회사의 ERP 시스템과의 연계에서 핵심 알고리듬으로 사용하여 생산 비용을 절감할 뿐만 아니라 추후 공급망 관리로의 확대 등에서 효과적으로 활용될 수 있다고 사료된다. 

Reference

1. Bouchriha, H., Ouhimmou, M., and D'Amours, S.; "Lot sizing problem on a paper machine under a cyclic production approach," International Journal of Production Economics, 105(2) : 318-328, 2007.
2. Drexl, A. and Kimms, A.; "Lot sizing and scheduling -survey and extensions," European Journal of Operational Research, 99(2) : 221-235, 1997.
3. Gupta, D. and Magnusson, T.; "The capacitated lot- sizing scheduling problem with sequence-dependent setup costs and setup times," Computers and Operations Research, 32(4) : 727-747, 2005.
4. Haase, K.; "Capacitated Lot-sizing with sequence dependent setup costs," OR Specktrum, 18(1) : 51-59, 1996.
5. Haase, K. and Kimms, A.; "Lot sizing and scheduling with sequence-dependent setup costs and times and efficient rescheduling opportunities," International Journal of Production Economics, 66(2) : 159-169, 2000.
6. Salomon, M., Kroon, L. G., Kuik, R., and Van Wassenhove L. N.; "Some Extensions of the Discrete Lotsizing and Scheduling Problem," Management Science, 37(7) : 801-812, 1991.
7. Shim, I.-S., Kim, H.-C., Doh, H.-H., and Lee, D.-H.; "A two-stage heuristic for single machine capacitated lot-sizing and scheduling with sequence-dependent setup costs," Computers and Industrial Engineering, 61(4) : 920-929, 2011.
8. Trigeiro, W. W., Thomas, L. J., and McClain J. O.; "Capacitated lot sizing with setup times," Management Science, 35(3) : 353-366, 1989.
9. Zhu, X. Y. and Wilhelm, W. E.; "Scheduling and lot sizing with sequence-dependent setup : a literature review," IIE Transactions, 31(11) : 987-1007, 2006.