search
Contact Us
HOME

  • Crossref logo
  • Crossref Similarity Check logo
Journal Search Engine

to

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.37 No.3 pp.113-121
DOI : https://doi.org/10.11627/jkise.2014.37.3.113

A Two-Machine Flowshop Scheduling with Outsourcing Strategy Allowed

Ik Sun Lee†
School of Business, Dong-A University
Corresponding Author : lis1007@dau.ac.kr
August 21, 2014 August 12, 2014

Abstract

This paper considers a scheduling problem in a two-machine flowshop with outsourcing strategy incorporated. The jobs can be either processed in the first machine or outsourced to outside subcontractors. This paper wants to determine which jobs to be processed in-house and which jobs to be outsourced. If any job is decided to be outsourced, then an additional outsourcing cost is charged The objective of this paper is to minimize the sum of scheduling cost and outsourcing cost under a budget constraint. At first this paper characterizes some solution properties, and then it derives solution procedure including DP (Dynamic Programming) and B&B (Branch-and-Bound) algorithms and a greedy-type heuristic. Finally the performance of the algorithms are evaluated with some numerical tests.

Scheduling , Outsourcing , Two-Machine Flowshop , Branch-and-Bound, Heuristic

아웃소싱 전략을 활용하는 두 단계 흐름생산라인의 일정계획

이 익선†
동아대학교 경영학과

초록

    Dong-A University

    1.서 론

    아웃소싱(Outsourcing)이란 기업의 업무나 기능을 보다 전문적인 외부업체에 의뢰하는 것을 뜻하며, 기업은 아 웃소싱 전략을 도입함으로써 비용을 줄이고 업무의 리드 타임을 감소시켜 시간과 비용 등의 측면에서 경쟁력 강 화를 꾀할 수 있다.

    아웃소싱은 근래에 보다 포괄적으로 업무의 프로세스 와 기능을 위탁하는 방향으로 그 영역을 확대시켜나가고 있으며, 또한 기업의 핵심적인 기능들도 경우에 따라서 아웃소싱되기도 한다. 아웃소싱 전략은 기업의 역량향상 을 저해하고 회사의 역할이 외부의 아웃소싱 업체에 맡 겨지는 과정에서 여러 위험이 존재하기도 하지만, 비용 의 절감으로 인한 재무적인 부담을 줄일 수 있으며, 결국 타이밍이 기업의 경쟁역량이 되는 상황에서 필수적인 옵 션이라고 말할 수 있다.

    본 논문은 생산설비의 아웃소싱 전략을 활용할 수 있 는 환경에서 일정계획 문제를 논의하고자 한다. 즉 작업 의 가공이 자체적인 설비에서 직접 처리되거나, 아웃소 싱으로 외부에 위탁되어 구매되어 조달되는 선택이 공존 하는 경우에 먼저 작업들 중에서 아웃소싱에 해당되는 작업들을 선택(job selection)하고 자체적으로 처리되는 작 업들의 순서를 결정(job scheduling)하는 문제를 다룬다. 생산설비는 두 설비를 가지는 2 Machine Flowshop을 고 려하며 작업이 아웃소싱된다면 추가적으로 아웃소싱 비 용을 지불해야 하며, 그 작업은 즉시로 조달된다. 본 논 문은 이러한 아웃소싱 전략하에서 총 아웃소싱 비용이 예산제약(budget constraint)의 범위 내에서 아웃소싱 작 업의 선별과 일정계획을 동시에 결정된다.

    아웃소싱에 관한 기존의 연구들은 다음과 같다. 아웃 소싱의 전략적인 성과를 평가한 연구들이 존재하는데, 즉 시스템의 운영 측면에서, 아웃소싱이 얼마나 비용적 인 측면에서 이득인지를 분석한 연구들로서 Nicholson et al.[16], Kaipia and Tanskanen[9], Cachon and Harker[5] 등이 있다.

    아웃소싱 전략을 보다 원활히 운영하기 위해 Framework 을 제안하는 논문들이 있는데, Abdel-Malek[2]은 다층 공 급사슬(multi-layered supply chains)의 상황에서 아웃소싱 의 성능을 평가하였다. Wu[21], Kouvelis and Milner[12], Ngwenyama and Bryson[15]는 기업의 아웃소싱을 관리하 기 위한 구조를 제안하였으며, Offodile and Abdel-Malek [17], Dekkers[7]는 경영관리기법들과 아웃소싱을 연계하 는 구조를 제안했다.

    아웃소싱의 효율을 향상시키기 위한 연구들이 있는데, Kim[11]은 아웃소싱 공급자 선정과 효율화를 연구하였다. Yang[22]은 아웃소싱 전략의 활용 하에서 재고 운용을 연 구했으며, Huiskonen and Pirttila[8]는 아웃소싱 위탁회사 와 본사간의 조정(coordination) 등의 문제들을 다루었다. Tarakci[19, 20]는 유지보수(maintenance activities)의 기능 에 대한 아웃소싱 전략을 논의하였다.

    본 논문의 위의 문헌연구와 비교해볼 때, 마지막 경우 에 해당되는데, 아웃소싱 수단의 효율적인 활용을 목적으 로 한다. 기존의 일정계획 논문들은 거의 작업들을 자체 적으로 처리하는 상황을 고려하지만, 본 논문은 아웃소싱 전략을 활용하여 시스템 자체의 비용과 리드타임을 줄이 는 일정계획을 수립코자 한다. 본 논문과 유사한 연구가 최근에 Lee and Sung[13, 14], Lee and Yoon[1]에 의해서 진행되었다. Lee and Sung[13, 14]는 단일설비의 상황에서 아웃소싱 전략을 고려하였으며, Lee and Yoon[1]은 병렬 설비의 상황에서 아웃소싱 전략을 연구하였다.

    Choi and Chung[4], Choi and Chung[6], Lee and Chung [10], Qi[18]은 는 두 단계의 흐름생산라인에서 아웃소싱 을 고려하였는데, 본 논문과 유사하게 아웃소싱 비용과 작업완료시간의 총합을 최소화하는 일정계획 수립연구 를 다루었다. 기존의 연구들은 작업을 아웃소싱하게 되 면 두 단계의 흐름생산라인에서의 모든 처리공정을 위탁 하지만, 본 논문은 첫 번째 설비에서의 가공을 외부의 전 문업체에 위탁할지, 혹은 직접적으로 처리할지를 의사결 정하는 상황을 고려한다. 본 논문에서 고려하는 문제의 작업흐름 구조는 다음의 <Figure 1>을 참조할 수 있다.

    본 논문에서 고려하는 문제가 NP-complete임을 고려 하여 비교적 작은 크기의 문제에 대해 최적해를 구해줄 수 있는 동적계획 알고리즘과, 상대적으로 큰 문제에 대 해 최적해를 구해주는 분지한계 알고리즘, 동시에 근사 해를 제공해주는 휴리스틱 알고리즘을 제안코자 한다.

    2.문제정의와 분석

    본 논문은 처리할 n개의 작업을 고려하며, 두 설비가 연속적으로 배열되어 있는 flowshop을 고려한다. 첫 번 째 설비에서의 처리가 자체적으로 이행되거나 외부업체 에 아웃소싱될 수 있다. 두 번째 설비에서는 반드시 자체 적으로 처리함을 가정한다. 작업 i(i = 1, 2,, ..., n)가 첫 번 째 설비에서 자체적으로 가공되는 경우에는 pi 시간이 소 요되고, 만일 작업 i가 아웃소싱된다면 아웃소싱 비용 oi 가 발생한다. 외부에 아웃소싱되면 즉시에 중간가공품을 구매해오는 것으로 상정할 수 있으며, 이는 즉시에 이루 어질 수 있음을 의미한다. p 는 자체 처리되는 작업들의 집합이고, p가 아웃소싱되는 작업들이라고 볼 때, 아웃소 싱의 총비용 OC(p)는 ∑ i ∈ π o i 이다. 두 번째 설비에서의 처 리 소요시간은 qi으로 가정하는데, 두 번째 설비에서는 아 웃소싱 전략을 고려하지 않는다. 즉 첫 번째 설비에서 아 웃소싱 되었어도 두 번째 설비에서는 모든 작업들이 직 접 처리됨을 원칙으로 한다. 본 논문은 “아웃소싱 예산제 약”을 고려하는데, 아웃소싱 총 비용 OC(p)가 예산 K 를 넘지 못한다는 뜻으로, OC π = ∑ i ∈ π o i ≤ K 으로 표현할 수 있다.

    본 논문의 목적함수는 작업완료시간과 아웃소싱 소요 비용의 합이다. 자체적으로 가공하는 작업들의 수가 증가 하면 총 작업완료시간이 커지고, 아웃소싱 작업들의 수 가 늘어나면 아웃소싱 비용이 늘어난다. 따라서, 운영하 는 측면에서는 두 비용간의 trade-off 관계를 감안하여 총 비용을 최소화하는 의사결정을 수립해야 한다. 본 논문 이 고려하는 총 비용 TC 는 다음과 같다.

    TC = δ ∑ i ∈ π o i + 1 − δ C max
    (1)

    Cmax는 작업완료시간을 뜻하고, δ는 아웃소싱 비용과 작업완료시간과 간의 중요도를 설정하기 위해 감안하기 위해 0과 1사이의 실수 값으로 가정하며, 이는 운영자가 설정할 수 있는 값으로 상정한다. 본 논문은 아웃소싱 예 산 OC(p) ≤ K 범위 내에서, 총 비용을 최소화하는 일정 계획을 수립하는 것인데, 구체적으로는 아웃소싱되는 작 업들 p를 정하고, 나머지 작업들 p 의 두 설비 Flowshop 에서의 생산일정계획을 수립한다. 본 논문에서 고려하는 일정계획문제를 편의상 FSO(Flowshop scheduling with outsourcing)문제라고 명명하기로 상정한다. 그러면 FSO 문제의 수리모델은 다음처럼 정리될 수 있다.

    FSO 수리모형 Min δ ∑ i o i y i + 1 − δ C max
    (2)
    s . t . C max ≥ C i for ∀ i
    (3)
    C i ≥ x ik ∑ l = 1 k ∑ j = 1 n p j x jl + q i for ∀ i , k
    (4)
    C i ≥ x ik ∑ j x jk − 1 C j for ∀ i , k
    (5)
    ∑ i o i y i ≤ K
    (6)
    ∑ k x ik + y i = 1 , for ∀ i x ij , y i ∈ 0 , 1 .
    (7)

    수리모델에서의 변수 yi는 작업 i가 아웃소싱 된다면 1의 값을 가지고, 그렇지 않으면 0 값을 가진다. 변수 xik 는 작업 i가 첫 번째 설비에서 k번째 위치에서 직접 가공 된다면 1의 값을 가지고, 그렇지 않으면 0 값을 가진다. Ci 는 두 번째 설비에서 작업 i의 처리완료시간을 뜻한다. 식 (2)는 목적함수로서 아웃소싱 비용과 작업완료시간의 합을 최소화함을 뜻한다. 식 (3)~식 (5)는 일정계획문제에 서 작업완료시간을 계산하기 위한 제약들이다. 식 (6)은 예산제약을 의미하고, 식 (7)은 작업 i가 아웃소싱되든지 k번째 위치에서 직접 생산되든지 결정된다는 뜻이다.

    위의 수리모델의 제약식 (4)와 식 (5)에서 변수들의 곱 으로 표현되어 있으므로, 비선형계획(Nonlinear Programming) 이라고 판단하며, 이러한 형태의 수리모델에서 효 과적인 해법을 개발하는 것은 간단한 일이 아니다.

    본 논문의 FSO 문제가 경영과학 분야에서의 NP-complete 문제임을 감안하길 바란다. Lee and Sung[14]의 논 문에서처럼 설비가 단일인 경우에도 NP-complete임을 참 조할 수 있다. 본 논문은 시간복잡도 pseudo-polynomial 의 동적계획 알고리즘과 분지한계 알고리즘을 제안하고, 효과적인 해를 빠른 시간에 구하는 휴리스틱 알고리즘을 개발코자 한다. 이러한 알고리즘들을 도출하기 위해서 다 음과 같은 성질들을 활용할 수 있다.

    성질 1 :

    자체적으로 처리하는 작업들의 작업순서 순열 일정(permutation schedule)을 따르는 것이 이득 이다.

    증명 :

    인접작업교환(pairwise job interchange)으로 간단히 확인할 수 있으므로, 세부적인 증명을 생략한다. □

    본 논문이 다루는 FSO 문제는 직접 처리하는 작업들 과 아웃소싱 작업들을 구분하는 문제와, 자체적으로 처 리하는 작업들의 가공순서를 결정하는 두 가지 의사결정 이 내포되어 있다. 만일 아웃소싱할 작업들이 이미 결정 되어 있다면 처리순서를 결정하는 두 번째 의사결정문제 는 다음의 성질들을 활용하여 해결할 수 있다.

    성질 2 :

    아웃소싱하는 작업들은 설비 2에서 최대한 우 선적으로 처리하는 것이 이득이며, 아웃소싱 작업들 간의 처리순서는 임의로 결정해도 손해 가 없다.

    증명 :

    인접작업교환(pairwise job interchange)으로 간단히 확인할 수 있으므로, 세부적인 증명을 생략한다. □

    성질 2의 내용을 활용한다면, 아웃소싱하는 작업들이 결정된 상황이라면, 설비 2에서는 이러한 아웃소싱 작업 들을 최우선적으로 처리하는 것이 이득이며, 또한 이러 한 작업들 간의 처리순서는 어떤 식으로 처리해도 무관 함을 알 수 있다. 다음의 성질 3은 자체적으로 처리하는 작업들에 대한 처리순서에 관한 분석내용이다.

    성질 3 :

    자체적으로 생산하는 작업들은 다음의 Johnson’s rule에 의해서 최적의 처리순서를 결정할 수 있다.

    증명 :

    인접작업교환(pairwise job interchange)으로 간단히 확인할 수 있으므로, 세부적인 증명을 생략한다. □

    <Johnson’s Rule>

    단계 0 :

    작업들을 집합들 U와 V으로 구분한다. U={j|pj < qj}, V = {j|pj ≥ qj.

    단계 1 :

    U에 속한 작업들을 pj의 오름차순으로 정렬하고, V에 속한 작업들을 qj의 내림차순으로 정렬한다.

    단계 2 :

    U에 속한 작업들을 먼저 처리하고, V에 속한 작 업들을 이후에 순서대로 처리한다.

    자체적으로 가공되는 작업들의 처리순서는 위의 Johnson’s Rule으로부터 결정되어 질 수 있으며, 아웃소싱되는 작업 들은 설비 1의 단계는 생략되며 외부로부터 즉시에 구매 하며, 설비 2에서는 우선적으로 처리되는 것이 이득임을 성질 2로부터 확인할 수 있다. 그러므로 성질들 2와 3으 로부터 기본적으로 작업들의 Indexing은 Johnson’s Rule 을 통해서 결정될 수 있음을 확인할 수 있다. 즉 기본적 으로 Johnson’s Rule을 활용해서 처리순서를 결정해놓고, 만일 아웃소싱으로 결정된다면 설비 2에서만 최우선적 으로 처리할 수 있는 것이다.

    이러한 결과로부터 작업들의 번호를 Johnson’s rule에 따라서 새롭게 매긴다면, 위의 [FSO 수리모형]은 다음과 같이 [New_FSO 수리모형]으로 새롭게 표현될 수 있다. 새로운 수리모형을 활용한다면 보다 효율적으로 해법을 탐색할 가능성을 높일 수 있을 것이다.

    [ New _ FSO   수리모형 ] Min δ ∑ i o i y i + 1 − δ C max s . t . C max ≥ C i for ∀ i C i ≥ ∑ j = 1 i p j x j + q i for ∀ i ∑ i o i y i ≤ K x i + y i = 1 , for ∀ i x i , y i ∈ 0 , 1 .

    변수 xi는 작업 i가 첫 번째 설비에서 자체적으로 가 공된다면 1의 값을 가지고, 그렇지 않으면 0 값을 가진다. 이제까지는 아웃소싱 작업들과 자체 처리작업들이 구분 된 경우의 가공순서를 결정하는 방안에 대해서 고려하였다. 여기서는 아웃소싱의 고려대상에서 배제가능한 작업들을 구분할 수 있는 방안을 제시코자 한다. 다음의 성질 4의 조건을 만족한다면 해당 작업은 아웃소싱의 대상에서 원 천적으로 배제가 가능하다.

    성질 4 :

    작업 j가 다음의 조건을 만족한다면, 아웃소싱 대상에서 제외되는 것이 이득이다.

    δ o j > 1 − δ p j + q j
    (8)

    증명 :

    작업 j가 아웃소싱 된다면, 발생되는 목적식 증가 분의 최소값은 δoj이다. 반대로 작업 j를 직접 가공 한다면 발생하는 목적식의 증가분의 최대값은(1 - δ)(pj + qj)이다. 따라서 식 (8)이 성립한다면 작업 j를 아웃소싱하는 비용 자체가 상대적으로 너무 크다는 것을 뜻하므로, 아웃소싱의 가능성을 배제 하는 편이 보다 이득이다. □

    본 장에서는 FSO 문제를 위한 해법으로서 동적계획법, 분지한계법, 발견적 휴리스틱 등을 제시한다.

    FSO 문제 해법

    f j x 1 , y 1 , y 2 = min ∞ , if y 1 > y 2 − q j i min 0 ≤ k ≤ y 2 − q j − x 1 f j − 1 x 1 − p j , y 1 , y 2 − q j − k , if x 1 ≤ y 2 − q j ii f j − 1 x 1 , y 1 + q j , y 2 + 1 − δ q j + δ o j iii

    본 장에서는 FSO 문제를 위한 해법으로서 동적계획법, 분지한계법, 발견적 휴리스틱 등을 제시한다.

    3.1.동적계획법

    FSO 문제가 이미 NP-complete 문제라는 점을 언급하 였다. 다항식 시간복잡도를 가지는 최적해법을 제안할 수 없음을 뜻한다. 그래서 이번 절에서는 FSO 문제 자체가 아니라 다양한 환경에 따라서 어떠한 해법이 존재하겠는 지를 논의코자 한다.

    먼저 FSO 문제가 NP-complete 문제이지만, 아웃소싱 예산이 충분한 경우에 대해서는 Johnson’s rule에 기반한 아래와 같은 동적계획법을 활용하여 최적해를 다항식 시 간복잡도 내에서 구할 수 있다.

    <DP 알고리즘 X>

    • 정렬(indexing) : Johnson’s rule을 활용하여 작업들을 정 렬한다.

    • 가치함수(value function), fj(x1, y1, y2 : 작업 1에서부터 j까지의 작업들이 설비 1에서 [0, x1] 동안에 처리되고, 설비 2에서 [y1, y2] 시간 동안에 처리되는 상황에서의 최소 목적함수 값이다.

    • 초기조건 : f0(0, 0, 0) = 0

    • 최적해 : min{(x1,y1,y2)|0 ≤ x1A, 0 ≤ y1 ≤ y2 ≤ B}fn(x1, y1, y2),

      where A = ∑ j = 1 n p j , B = ∑ j = 1 n q j

    • 순환식(recursive equation) : 순환식에서 식 (i)은 작업 j를 설비 2에서 처리할 여유가 없음을 뜻한다. 따라서 무한대 의 상태값을 가진다. 식 (ii)는 작업 j를 직접적으로 가공 하는 경우를 뜻한다. 식 (iii)는 작업 j를 아웃소싱함을 뜻한다. 위의 DP 알고리즘 X의 상태(state)의 수는 최대 AB2이므로 O(AB2)의 시간복잡도를 가진다.

    <DP 알고리즘 Y>

    • 정렬(indexing) : Johnson’s rule을 활용하여 모든 작업들을 순서대로 나열한다.

    • 가치함수(value function), fj(x1, y1, y2; b) : 작업 1에서 부터 j까지 작업들을 설비 1에는 [0, x1]시간 동안에 처리되고, 설비 2에서는 [y1, y2]시간 동안에 처리하며, 아웃소싱 소요비용은 b를 활용하는 목적함수의 최소 값을 나타낸다.

    • 초기조건 : f0(0, 0, 0; 0)

    • 최적해 : min {(x1, y1, y2, b)|0 ≤ x1 ≤ A, 0 ≤ y1 ≤ y2 ≤ B, 0 ≤ b ≤ K},

      fn(x1, y1, y2; b)

      where A = ∑ j = 1 n p j , B = ∑ j = 1 n q j

    • 순환식(recursive equation) :

      f j x 1 , y 1 , y 2 ; b = min ∞ , if y 1 > y 2 − q j i ∞ , if x 1 > y 2 − q j and   o j > b ii min 0 ≤ k ≤ y 2 − q − x 1 { f j − 1 ( x 1 − p j , y 1 , y 2 − q j − k ; b + 1 − δ q j + k , iii if x 1 ≤ y 2 − q j f j − 1 x 1 , y 1 + q j , y 2 ; b − o j + 1 − δ q j + δ o j , if o j ≤ b iv

      순환식에서 식 (i)은 작업 j를 설비 2에서 처리할 여유 가 없음을 뜻한다. 따라서 무한대의 상태값을 가진다. 식 (ii)는 작업 j를 아웃소싱할 비용적인 여유가 없으며 설 비 1에서 직접 처리할 시간적 여유도 없음을 뜻한다. 따 라서 무한대의 상태값을 가진다. 식 (iii)는 작업 j를 직 접적으로 가공하는 경우를 뜻한다. 식 (iv)는 작업 j를 아웃소싱함을 뜻한다. 위의 DP 알고리즘 Y의 상태(state) 의 수는 최대 AB2K이므로 O(AB2K)의 시간복잡도를 가진다.

    3.2.휴리스틱 알고리즘

    여기서부터는 짧은 시간 안에 효율적인 해결책을 얻 을 수 있는 휴리스틱 알고리즘을 제안한다. 제안되는 휴리 스틱은 Greedy 유형이다. 먼저 작업별로 1 − δ p j + q j δ o j + 1 − δ q j 을 구하고, 관련되는 값이 클수록 아웃소싱에 따른 이익이 클 것이라는 아이디어에 착안하였다. 그러한 작업들에게 우선적인 아웃소싱의 기회를 제공하는 바, 이름을 “휴리 스틱 Greedy”으로 명명하였으며, 세부적인 절차는 다음과 같이 정의될 수 있다.

    <휴리스틱 Greedy>

    단계 0 :

    작업들을 1 − δ p 1 + q 1 δ o 1 + 1 − δ q 1 ≥ 1 − δ p 2 + q 2 δ o 2 + 1 − δ q 2

    ≥ ... ≥ 1 − δ p n + q n δ o n + 1 − δ q n 이 성립하도록 순서를 정한다. q = 1, B = K 초기화한다.

    >단계 1 :

    q < n의 조건을 만족한다면, 자체적으로 처리하 는 작업들을 Johnson’s rule으로 처리순서를 정하 고 종료.

    단계 2 :

    성질 4의 조건에 해당되거나, 조건 o[q] ≥ B 이 충 족한다면, 작업 [q] 는 아웃소싱되지 않고, q = q + 1으로 업데이트를 한 후에, 단계 1로 이동한 다. 그렇지 않으면, 단계 3으로 이동한다.

    단계 3 :

    작업 [q] 가 아웃소싱 된다. q = q + 1, B = B-o[q]업데이트하고, 단계 1로 이동한다.

    4.분지한계 알고리즘

    4.1.분지규칙

    본 논문은 최적해를 구하기 위한 분지한계(Branch-andbound) 알고리즘을 제안한다. 앞서 제안한 DP 알고리즘 Y를 활용하면 최적해를 구할 수 있다. 제 5장에서 DP 알고리즘의 성능을 확인하겠지만, DP 알고리즘의 효율 성은 그다지 높지 않음이 일반적인 견해이다. 따라서 보 다 효율적으로 최적해를 구하기 위한 분지한계 알고리즘 을 제시코자 한다.

    본 논문의 분지한계 알고리즘의 노드는 작업들의 부 분집합이며, 일부작업들은 직접 처리하고, 나머지 작업 들은 아웃소싱으로 구분된다. 직접 처리하는 작업들은 Johnson’s rule에 의해 순서가 결정된다. 분지한계 알고리 즘은 하나의 노드를 선택하고, 아직 결정되지 않은 하나 의 작업을 선택하여, 해당 작업을 직접 처리하거나, 아웃 소싱하는 경우들을 상정하여 두 개의 새로운 노드를 만 들어서 접목시킨다. 본 논문의 분지한계 알고리즘의 트 리구조는 다음 <Figure 2>와 같다.

    <Figure 2>에서 기호 NOr은 해당 노드 r에서 직접적 으로 처리하는 작업들 집합이고, Or은 해당 노드 r에 아 웃소싱되는 작업들을 뜻한다. Or = {g,h}는 작업들 g와 h가 아웃소싱으로 처리됨을 뜻한다. 노드 r에서 결정되 지 않은 작업들 중에서 임의의 작업 s를 선별하고 두 개 의 새로운 노드들(r + 1)과 (r + 2)을 생성한다. 노드 (r + 1) 는 작업 s가 직접 처리되는 경우이며, Johnson’s rule에 기반하여 처리 순서를 결정한다. 노드 (r + 2)은 작업 s를 아웃소싱으로 처리하는 경우이다.

    본 논문은 깊이우선 검색(depth-first search)을 노드 선 택을 위한 방법론으로 활용한다. 즉 분지한계 트리에서 가장 많은 수의 작업들을 포함하는 노드를 우선적으로 선택함을 뜻한다.

    4.2.한계규칙(Bounding Rule)

    분지한계 알고리즘에서 한계규칙은 분지한계 탐색트 리의 노드들을 검색하여, 조건에 만족하는 노드들의 제 거 여부를 결정함으로써 보다 효과적인 해의 탐색을 가 능토록 만든다. 먼저 본 논문에서는 초기상한 값으로 제 3.2절에서 제시된 휴리스틱 Greedy의 해 값을 적용한다. 또한 노드 제거를 위해서 구하는 하한값을 구하는데, 구 체적으로 노드 r의 하한값 LBr은 다음의 계산 값을 활 용한다.

    LB r = TC π r + 1 − δ ∑ j ∈ π ˜ r q j

    4.3.노드제거규칙(Fathoming Rules)

    본 논문의 분지한계 알고리즘은 두 가지 노드제거 규 칙들을 활용하는데, 첫 번째는 성질 4를 활용한다. 두 번 째는 다음의 성질 5에 기반한다.

    성질 5 :

    작업들 i, j가 pi < pj <, qj, oi ≥ oj <을 만족한 다면, 만일 i가 아웃소싱 된다면, j도 반드시 아 웃소싱되는 것이 이득이다.

    증명 :

    인접작업교환(pairwise job interchange)으로 간단히 확인할 수 있으므로, 세부적인 증명을 생략한다. □

    5.성능 평가

    이제는 제 3장에서 유도된 DP 알고리즘과 휴리스틱 Greedy와 제 4장에서 제시된 분지한계 알고리즘의 성능 을 분석한다. 성능의 측정을 위해 활용되는 파라메터들 은 다음과 같이 셋팅될 수 있다.

    1. 설비 1에서 작업들의 처리시간 pi와 설비 2에서의 처 리시간 qi는 U(1, 10)으로부터 생성시킨다. U(a, b)는 이산형 균등분포이다.

    2. 아웃소싱에 필요한 비용 oi은 U(1, 30)으로 생성시킨다.

    3. 예산 K와 δ는 각각 U(1, 150)와 U(0.3, 0.7)으로 생 성시킨다.

    작업의 수는 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70 75, 80의 총 16가지를 고려하였다. 각 작업에 대하여 20개 인스턴스들을 랜덤으로 생성하여 여러 알고 리즘들을 평가하였다. 결과는 <Table 1>에 정리되어 있 는데, 분지한계 알고리즘에 대해서는 최적해를 구하기까 지의 평균 노드수, 최대노드 수, 평균시간, 최대시간을 구하였다. DP 알고리즘 Y가 최적해를 구하기까지의 평균 states 수, 최대 states 수, 평균시간, 최대시간을 구하였다. 휴리스틱 Greedy에 대해선 최적해와의 Gap을 계산하였 다. OPT가 최적해이고 Heuristic이 휴리스틱 Greedy를 통해 얻은 값이라면, <Table 1>에 나타난 Gap(%)은 다음 과 같다.

    Gap % = Heuristic − OPT OPT × 100

    Table의 알고리즘들의 성능평가를 확인해보면 분지한 계 알고리즘의 경우 비교적 큰 수의 작업에 대해서도 최 적해를 도출하고 있다. DP 알고리즘 Y의 경우는 상대적 으로 그다지 크지 않은 수의 작업들에 대해서 최적해를 구하는 것을 확인할 수 있다. 제안된 휴리스틱 Greedy의 경우도 작업의 수가 증가함에 따라서 Gap(%)이 크게 떨 어지지 않고 오히려 안정적인 성능을 나타냄을 확인할 수 있다.

    아웃소싱을 위한 예산제약의 변동에 따른 알고리즘들 의 성능을 평가하기 위한 실험을 진행하였다. 예산 K를 U(50, 100), U(100, 150), U(150, 200), U(200, 250) 4가지 로 설정하여 테스트하였으며, 결과를 <Table 2>에 정리 하였다. 예산의 변동에 따라서 분지한계 알고리즘의 성 능은 크게 변동이 없었으나, 휴리스틱 Greedy의 성능은 다소 저하되었으나, 변동폭은 그다지 크지 않았다.

    아웃소싱에 소요되는 비용 oj의 변동에 알고리즘들 성 능을 분석하였다. oj는 U(10, 30), U(20, 40), U(30, 50), U(40, 60)을 고려했으며, 결과는 <Table 3>에 정리되어 있다. 비용이 커질수록 분지한계 알고리즘과 Greedy 휴리스틱 의 성능이 향상되는 것을 확인할 수 있다.

    6.결 론

    본 논문은 두 설비에서 연속적으로 가공하여 제품을 완성하는 경우에, 아웃소싱을 위한 예산의 제약을 상정 하고 설비 1에서의 작업의 가공을 자체적으로 처리하거 나 외부설비에 아웃소싱하는 전략을 선택할 수 있을 때, 최적의 의사결정계획을 수립하는 문제를 고려하고 있다. 작업완료시간으로서의 일정계획 코스트와 아웃소싱 비 용간의 합을 최소화하는 동적계획법, 분지한계 알고리즘, 휴리스틱 등을 제시하였다.

    본 논문의 내용은 생산시스템에서 경쟁이 치열하며, 시간적으로 압박이 크며, 아웃소싱 전략을 빈번히 고려 하는 경쟁환경에서 활용될 수 있으며, 예산에 따른 제약 이 크게 고려되는 환경에서 효율적으로 작용할 가능성이 있다.

    기존 일정계획 논문들은 자체적인 설비에서 작업들을 모두 처리하는 경우만을 상정하고 있으나, 본 논문은 아 웃소싱 전략을 일정계획 문제에 접목하는 새로운 의사결 정문제를 다루고 있으며, 다변적인 환경과 제약을 고려 함으로써 보다 광범위한 연구를 검토할 수 있다.

    Figure

    JKISE-37-113_F1.gif

    The Job-Process Work-Flow in this Paper

    JKISE-37-113_F2.gif

    The Node Structure in the Branching Tree

    Table

    The Test Summary of DP Algorithm Y, Branch-and-Bound and Greedy Heuristic

    (*)indicates the case that the optimal solutions are not found within the computation time.

    The Test Summary for the Outsourcing Budget

    The Test Summary for the Outsourcing Cost

    Reference

    1. Lee I.S , Yoon S.H (2008) A Parallel Machine Scheduling Problem with Outsourcing Options , Journal of the Society of Korea Industrial and Systems Engineering, Vol.31 (3) ; pp.101-109
    2. Abdel-Malek L , Kullpattaranirun T , Nanthavanij S (2005) A Framework for Comparing Outsourcing Strategies in Multi-layered Supply Chains , International Journal of Production Economics, Vol.97; pp.318-328
    3. Baker K.R (1974) Introduction to Sequencing and Scheduling, John Wiley and Sons, Inc, pp.118-119
    4. Byung-Cheon C , Jibok C (2011) Two-machine flow shop scheduling problem with an outsourcing option , European Journal of Operational Research, Vol.213; pp.66-72
    5. Cachon G.P , Harker P.T (2002) Competition and Outsourcing with Scale Economies , Management Science, Vol.48; pp.1314-1333
    6. Dae-Young C , Byung-Cheon C (2013) Outsourcing and scheduling for two-machine ordered flow shop scheduling problems , European Journal of Operational Research, Vol.226; pp.46-52
    7. Dekkers R (2000) Decision Models for Outsourcing and Core Competencies in Manufacturing , International Journal of Production Research, Vol.38; pp.4085-4096
    8. Huiskonen J , Pirttila T (2002) Lateral Coordination in a Logistics Outsourcing Relationship , International Journal of Production Economics, Vol.78; pp.177-185
    9. Kaipia R , Tanskanen K (2003) Vendor Managed Category Management-an Outsourcing Solution in Retailing , Journal of Purchasing and Supply Management, Vol.9; pp.165-175
    10. Kangbok L , Byung-Cheon C (2011) Two-stage production scheduling with an outsourcing option , European Journal of Operational Research, Vol.213; pp.489-497
    11. Kim B (2003) Dynamic Outsourcing to Contract Manufacturers with Different Capabilities of Reducing the Supply Cost , International Journal of Production Economics, Vol.86; pp.63-80
    12. Kouvelis P , Milner J.M (2002) Supply Chain Capacity and Outsourcing Decisions : the Dynamic Interplay of Demand and Supply Uncertainty , IIE Transactions, Vol.34; pp.717-728
    13. Lee I.S , Sung C.S (2008) Single Machine Scheduling with Outsourcing Allowed , International Journal of Production Economics, Vol.111; pp.623-634
    14. Lee I.S , Sung C.S (2008) Minimizing Due Date Related Measures for a Single Machine Scheduling with Outsourcing Allowed , European Journal of Operational Research, Vol.186; pp.931-952
    15. Ngwenyama O.K , Bryson N (1999) Making the Information Systems Outsourcing Decision A Transaction Cost Approach to Analyzing Outsourcing Decision Problems , European Journal of Operational Research, Vol.115; pp.351-367
    16. Nicholson L , Vakharia A.J , Erenguc S.S (2004) Outsourcing Inventory Management Decisions in Healthcare : Models and Application , European Journal of Operational Research, Vol.154; pp.271-290
    17. Offodile O.F , Abdel-Malek L.L (2002) The Virtual Manufacturing Paradigm : The Impact of IT/IS Outsourcing on Manufacturing Strategy , International Journal of Production Economics, Vol.75; pp.147-159
    18. Xiangtong Q (2009) Two-stage production scheduling with an option of outsourcing from a remote supplier , Journal of System Science and System Engineering, Vol.18; pp.1-15
    19. Tarakci H , Tang K , Moskowitz H , Plante R (2006) Incentive Maintenance Outsourcing Contracts for Channel Coordination and Improvement , IIE Transactions, Vol.38; pp.671-684
    20. Tarakci H , Tang K , Moskowitz H , Plante R (2006) Incentive Maintenance Outsourcing of a Multi-process Manufacturing System with Multiple Contractors , IIE Transactions, Vol.38; pp.67-78
    21. Wu F , Li H.Z , Chu L.K , Sculli D (2005) An Outsourcing Decision Model for Sustaining Long-term Performance , International Journal of Production Research, Vol.43; pp.2513-2535
    22. Yang J , Qi X , Xia Y (2005) A Production-inventory System with Markovian Capacity and Outsourcing Option , Operations Research, Vol.53; pp.328-349
    Copyright © KOREAN SOCIETY OF INDUSTRIAL AND SYSTEMS ENGINEERING. All rights reserved.
    #425, Anyang trade-center, Simin-daero 161, Dongan-gu, Anyang-si, Gyeonggi-do, 14048, Korea