| Home | E-Submission | Sitemap | Editorial Office |  
top_img
Journal of the Korean Society for Quality Management > Volume 47(4); 2019 > Article
전용기계가 있는 혼합흐름공정의 생산 일정 계획 수립을 위한 2단계 접근법

Abstract

Purpose

This study deals with a production planning and scheduling problem to minimize the total weighted tardiness on hybrid flow shop with sets of non-identical parallel machines on stages, where parallel machines in the set are dedicated to perform specific subsets of jobs and sequence-dependent setup times are also considered.

Methods

A two-stage approach, that applies MILP model in the 1st stage and dispatching rules in the 2nd stage, is proposed in this paper. The MILP model is used to assign jobs to a specific machine in order to equalize the workload of the machines at each stage, while new dispatching rules are proposed and applied to sequence jobs in the queue at each stage.

Results

The proposed two-stage approach was implemented by using a commercial MILP solver and a commercial simulation software and a case study was developed based on the spark plug manufacturing process, which is an automotive component, and verified using the company's actual production history. The computational experiment shows that it can reduce the tardiness when used in conjunction with the dispatching rule.

Conclusion

This proposed two-stage approach can be used for HFS systems with dedicated machines, which can be evaluated in terms of tardiness and makespan. The method is expected to be used for the aggregated production planning or shop floor-level production scheduling.

1. 서 론

오늘날 하드웨어의 발달로 기계가 범용 및 다기능화 되면서 병렬 기계들로 구성된 제조 시스템의 수는 증가 추세에 있다. 또한, 주문생산방식이 확산되고 기업 간 경쟁이 치열해지면서 납기준수가 중요한 관리목표가 되고 있다. 혼합흐름공정(Hybrid Flow Shop, HFS)은 일반적으로 각 단계에서 복수의 병렬 기계를 가진 확장된 흐름생산(Flow Shop) 공정으로 정의될 수 있는데, 많은 제조 환경에서 생산성과 생산제품의 다양성을 동시에 추구하기 위해 HFS는 전형적인 흐름생산공정보다 널리 이용되고 있다. 이러한 HFS는 전기/전자, 반도체, 제지, 섬유 산업 등 산업 전반에 걸쳐 발견된다(Huang and Li, 1998; Lee et al., 2016). 또한, 비제조업 분야인 토목공학, 인터넷 서비스 아키텍처와 컨테이너 물류 취급 시스템에서도 HFS를 발견할 수 있다(Ruiz and Vázquez-Rodríguez, 2010).
많은 제조 시스템에서 자원 할당, 제품 배치 및 생산 일정 계획 문제가 주요한 세 가지 의사결정 문제로 다뤄지는데, HFS 제조 시스템 역시 같은 문제들을 다룬다. 이러한 HFS에서 생산계획 및 일정 계획 문제는 통상의 흐름공정에서처럼 첫 번째 공정 단계(Stage)의 투입을 중심으로 계획을 수립하는 것이 현업에서는 일반적이나, 실제로는 각 단계에서 복수의 기계 중 가용한 기계를 선택해야 하므로 Job shop 일정 계획 문제의 성격을 동시에 갖게 된다. 즉, 각 단계마다 작업의 선택과 기계의 선택 문제가 발생하여, 일반적인 흐름공정에서의 생산계획 및 스케줄링보다는 복잡하다. 추가적으로, 작업의 동적 또는 임의 도착, 기계 셋업-타입, 또는 예기치 않은 기계 고장 시간의 고려 등에 따라 문제의 난이도가 증가되고, 연구에 따라 다양한 목적함수를 사용함으로써 문제의 유형은 다양하다(Sudipta, 2017).
본 연구에서는 각 스테이지가 이종 병렬 기계로 구성되어, 각 기계가 특정 작업군만 가공 가능한 혼합흐름공정을 대상으로 생산 일정 계획을 수립하기 위하여, 정수계획법에 따른 작업 할당과 시뮬레이션과 디스패칭 규칙을 함께 적용하는 2단계 방법을 연구한다. 제안된 2단계 방법을 평가하기 위한 기준으로 전체 주문 처리시간(Makespan), 총 납기지연시간(Total Weighted Tardiness)을 함께 고려한다. 본 논문은 다음과 같이 구성된다. 2장에서 관련 문헌연구를 요약하고, 3장에서 문제 설명, 4장에서 MILP(Mixed Integer Linear Programing) 모형과 디스패칭 규칙을 사용하는 2단계 방법을 제안한다. 또한, 제안된 방법에 대한 검증을 위해, 5장에서 자동차 엔진용 스파크 플러그 제조기업의 생산라인을 대상으로 시뮬레이션 모형을 기반으로 한 실증 사례 분석을 수행한다. 마지막으로 6장에서는 결론과 추후 연구과제에 대해 논의한다.

2. 관련 문헌연구

HFS에서의 일정계획에 대한 연구들은 (de Fátima Morais et al., 2014)에 의하면 다음과 같이 5가지 기준에 의해 구분될 수 있다.
1) 성능 평가 지표: Min (Max, Mean) Tardiness, Min Makespan,
2) 접근 방법: exact method(MILP, B&B methods), Heuristic, Meta-Heuristic, Dispatching Rules
3) 제약 조건: (sequence dependent or independent) setup time, reentrance,
4) 고려하는 목적함수의 수: Single/Bi/Tri/Multi-Criteria
5) 각 스테이지에서 가용한 기계 그룹: identical or non-identical dedicated machine (DED)
HFS의 생산계획 및 스케줄링 문제에서는 대부분 납기지연 감소를 목적으로 하나, 일부는 생산성 향상을 동시에 고려한다. 대부분의 경우에서, 이러한 HFS의 스케줄링 문제는 가장 간단한 형태인 2단계에 각 단계별로 동일한 복수 기계가 있는 경우라 할지라도 NP-hard이다(Gupta, 1988). 그러므로 MILP 모형의 최적해를 구하기 위해서는 Branch and Bound (B&B) 방법이 가장 선호된다. Lee and Kim(2004)은 2단계 HFS에서 total tardiness를 최소화하는 B&B 알고리즘을 제안하였고, 이후 Choi and Lee(2007)은 같은 2단계 HFS에서 number of tardy Jobs를 최소화하기 위한 B&B 알고리즘을 제안하였다. Fattahi et al.(2014)은 셋업 타임이 있고 HFS과 흐름공정이 이어진 시스템에서 병목공정을 고려하여 makespan을 최소화하는 B&B 알고리즘을 제안하였다.
수리적 모형으로 스테이지 수와 기계의 수가 큰 현실적 문제에서 최적 해를 찾는 시간이 오래 걸려 현실에서는 사용을 하지 못하였다. 이러한 이유로 많은 연구들이 실제 제조 시스템에서 발생할 수 있는 크기의 문제들에 대해 최적해는 아니지만 우수한 해를 적절한 시간 내에 찾아 줄 수 있는 발견적 알고리즘(휴리스틱, heuristic)들을 제안하여 문제를 해결하였다. 가장 간단한 유형의 휴리스틱은 일정 예약 정책 또는 목록 스케줄링 알고리즘이라고도 하는 디스패칭 규칙(Dispatching Rule)이다. 많은 연구가 디스패칭 규칙에 관해서 수행되었는데, 예를 들어 Brah(1996)는 10 개의 디스패칭 규칙을 비교하였고, Yoon et al.(2013)은 각 스테이지마다 다른 디스패칭 규칙을 조합하여 최적의 디스패칭 규칙의 조합을 찾아내려 하였다.
디스패칭 규칙 외에 일반적으로 널리 사용되는 휴리스틱 방법론으로써 Meta-Heuristics는 유용한 조합 최적화 기법을 활용될 수 있는데, Kim and Cho(2005)Jun(2015)은 이종 병렬 기계를 가진 HFS에서 유전 알고리즘(Genetic Algorithm)을 적용하여 납기지연을 최소화하는 생산 일정 계획을 수립하는 방법을 제안하였다.
HFS에 대한 광범위한 문헌 연구인 Ruiz & Vázquez-Rodríguez(2010)에 의해 평가된 200편 이상의 논문들은 모두 동종 병렬 기계(identical parallel machine) 사례만을 다루고 있고, de Fatima Morais et al.(2014)에 따르면 조사 대상이 목적함수가 Multicriteria인 경우만으로 제한되기는 하나, 포함된 46편의 논문 중 한 편(Lin and Liao, 2003)만이 DED 문제를 다루고 있다. 본 연구는 순서 의존적 셋업 타임이 있고, 이종 병렬 기계에서 전용기계가 있는 DED HFS에서 납기 지연을 고려한 생산 일정 계획 문제를 다루고자 한다.

3. 전용기계가 있는 HFS에서 일정계획 문제

본 연구에서는 HFS 형태의 제조 시스템의 생산 일정 계획 문제를 다룬다. Figure 1은 HFS 시스템의 개념도를 보여준다. 투입물에는 원료, 부품 또는 미완성 제품 등이 포함되며, m 단계 HFS에서 가공된다. 일반적으로 버퍼는 중간 제품을 저장하기 위해 각 공정 단계(stage) 사이에 있으며, 크기의 제한이 없다고 가정한다. 각 단계별 기계의 수는 같지 않으며, 각 기계는 반드시 같지는 않다.

3.1 Notation

다음은 문제 설명을 위한 기호이다.
<Indices>
i : order index i=1,…,n
j : stage index j=1,…,m
kj : machine index at each stage, k=1,…, Kj
d: day index d=1, …, r (planning horizon = r days)
l: shift index l=1, 2
<Parameters>
α : OEM 품번을 우선적으로 할당하기 위한 가중치
β: 기계 평균 가동률
βi,j : i 주문이 j스테이지에서 가공해야 하면 1, 아니면 0
γi,j,k : i 주문이 j스테이지 k 기계에서 가공할 수 있으면 1, 아니면 0
δi,j,k : i 주문의 j스테이지 k 기계에서의 가공 시간,
Wl: l 시프트에서의 근무 시간(작업 가능 시간)
Ck,d,l : k 기계를 dl시프트에서 사용 가능하면 1, 아니면 0
Di: i 주문의 납기일

3.2 문제의 가정

본 연구에서 다루는 HFS는 다음과 같은 특징과 가정을 갖는다.
1) 주문 및 작업 내역은 계획 초기에 알려져 있다. (동적 주문 도착과 긴급 생산은 고려하지 않는다.)
2) 각 작업(주문 또는 제품)의 생산 순서는 공정마다 한 개 이상의 병렬 기계가 존재하는 흐름공정과 같이 한 방향으로 진행되나, 제품의 유형에 따라 특정 단계는 거치지 않을 수도 있다.
3) 공정 간 버퍼 사이즈는 무한하며, 각 기계에서의 작업시간은 상수로(deterministic) 알려져 있다.
4) 각 작업은 로트(lot) 단위로 진행되는데, 하나의 기계는 동시에 하나의 로트만 가공할 수 있으며, 나머지 작업들은 재공 재고(WIP)으로서 각 단계 중간에서 대기하게 되고, 하나의 기계가 가용하게 되면 대기 중인 작업 중 주어진 순서에 따라 투입된다. 공정 간 이동거리나 이동시간은 무시한다.
5) 순서 의존적 셋업 시간: 각 작업 간에는 제품의 종류에 따라 셋업 시간이 발생한다. 셋업 시간은 선후 작업의 유사도에 따라 달라진다.
6) 작업 우선순위: 각 주문은 2가지 수준의 우선순위(OEM = 높은 우선순위, AS = 낮은 우선순위)와 납기일이 주어진다.
7) 작업 일정에 따른 가용한 기계의 변화: 작업자는 2교대로 작업하며, 이에 따라 날짜 및 shift, 잔업 수행 등의 사유에 의해 일정별로 사용 가능한 기계가 달라질 수 있다. 예를 들어, 여러 가지 현실적인 제약에 의해 주간과 야간작업자 수가(ex., 주간 6명, 야간 3명) 다르므로, 가용한 기계의 종류 및 대수도 작업자 일정에 따라 달라질 수 있다.
8) 각 스테이지는 이종 병렬 기계로 이뤄져 있으며, 일부 작업은 특정 기계 또는 특정 기계 군에서만 가공 가능(DEDicated machine)하고, 기계에 따라 가공 소요시간은 달라질 수 있다. (이하 DED)
위에서 제시한 가정 중, 1) ~ 5)는 HFS 시스템에서 보편적인 사항이나, 6) ~ 8)은 본 연구에서 다루는 특수한 고려 사항에 해당한다. 특히, 8) 조건을 가진 HFS에서는 각 오더마다 갈 수 있는 기계, 공정이 다르기 때문에 오더의 투입 순서에 따라 후속 공정의 상황이 크게 바뀌므로 첫 공정의 투입이 가장 중요하다. 또한, 동종 병렬 기계(identical parallel machine)의 경우와 달리, 이종 병렬 기계 하에서 DED 문제의 경우에는 각 스테이지에서 기계별 부하를 고려하여야 한다. 특정 기계에만 작업이 가능한 품번들만 생산되면 해당 스테이지가 병목이 되기 때문에, 각 스테이지의 설비들이 모두 작업 가능하도록 workload balancing을 고려하여야 한다.
고려하는 제조 시스템에서 생산물량은 미리 지정되어 있고, 주문은 OEM과 AS로 두 가지 우선순위를 가지며, 특정 제품의 종류에 따라 생산 가능한 경로, 수량, 납기 등의 정보를 갖고 있으며, 이런 정보는 생산계획 시 모두 알려져 있다고 가정한다. 실제 사례에서는 ERP 시스템과 연계하여 BOM 정보로부터 MIP 모델 생성 시 자동화하여 추출할 수 있다. 실제 각 공정에서는 선후 작업의 품번에 따라 그 셋업 타임을 가지는데, 위에 제시한 수리 모형에서는 순서-의존적인 셋업 타임은 고려하고 있지 않고, 대신 기계의 평균 가동률을 생산 가능 시간에 곱해줌으로써 셋업타임을 위한 여유시간을 반영하고 있다. 모든 제품의 첫 공정은 1번 스테이지이며, 중간에 특정 스테이지는 건너뛸 수 있으나, 그 방향성인 가공 순서는 모두 동일하다. 실제 하나의 주문이 여러 로트(Lot)로 나뉘어 가공될 수 있으나, 본 연구에서는 하나의 주문은 하나의 로트로 가공되나, 로트 사이즈는 주문량에 따라 다를 수 있다고 가정한다.

3.3 목적함수

생산 일정 계획 문제에서는 용도에 따라 다양한 목적함수가 사용될 수 있다. 이 중 흔히 많이 사용되는 것으로 완료 시간(maximum/total/average completion time), 흐름 시간(maximum/total.average flow time), maximum/total/average lateness, maximum/total/average tardiness, maximum/total/average earliness, 납기 지연된 로트 수 등이 있는데, 그중 아래에 제시되는 2가지를 가장 보편적으로 고려할 수 있다.
(1)
f2=tatalweightedtardiness=i=1nwiti
(2)
f2=makespan:Cmax=max{Ci}i=1,2,,n
식(1)은 로트 별 가중치(wi)를 고려한 납기지연(tardiness)의 합을, 식(2)은 최대 완료 시간을 최소화하는 것이고 것이다. 본 연구에서는 이 중 식(1)에 표현된 납기지연을 주 성능지표로 삼고, 사례연구에서는 참고적으로 식(2)의 완료 시간을 제시한다.

4. 제안 방법

본 연구에서는 2단계 접근법을 제안한다. 구체적인 생산 일정 계획을 수립하기 전에 각 스테이지의 부하를 고려한 생산계획(Production Planning)을 할당하는 1단계와 생산계획에 따라 투입하되 각 스테이지에서 실시간 디스패칭 규칙에 의한 일정 계획(Production Scheduling) 수립의 2단계 접근법을 제안한다. 1단계에서는 문제를 단순화하여 각 스테이지에서 기계 별 부하를 고려하면서 납기를 최소화하는 수리 모형을 제안하고, 이를 활용하여 주간 생산계획을 수립한다. 2단계에서는 시뮬레이션과 디스패칭 규칙을 적용한 생산 일정 계획을 수립한다.

4.1 1단계: 생산계획을 위한 MILP 모형

생산계획과 스케줄링을 한 번에 수리적으로 모델링 할 수는 있겠으나 문제의 클래스가 NP-hard임을 고려할 때, B&B 방법 등을 이용하지 않고 MIP 모형을 직접적으로 사용하면 실용적인 문제에서는 그 최적해를 찾는 것은 어렵다. 본 연구에서는 수리 모형을 기계 별 부하 평준화를 고려하여, 납기를 최소화하기 위한 Bin Packing 모형의 변형을 제안한다. 경우에 따라서는 시간이 많이 걸릴 수 있겠으나, 이런 경우 시간 제약을 주고 구해진 현재 최적해를 2단계 생산 스케줄링을 위한 입력 자료로 사용한다.
본 연구에서 고려하는 1단계 작업 할당 문제를 혼합 정수계획법 모형으로 표현하면 다음과 같다.
<Decision Variables>
ti: i 로트의 납기지연,
xi,j,k,d : i 로트가 j 스테이지의 k 기계에서 d 일에 작업하면 1, 아니면 0
(3)
MinαiΦti+(1α)iΩti
s.t.
(4)
kdγi,j,kxi,j,k,dβi,j,i,j
(5)
kdδi,j,kxi,j,k,dρiWlCk,l,d,k,d
(6)
kd((d+δi,j,k)xi,j,ddxi,j+1,k,d),i,j
(7)
kddxi,m,k,dtiDi,i
(8)
xi,j,k,d(0,1),i,j,k,d
(9)
ti0,i
식(3)의 목적함수는 OEM Tardiness와 AS Tardiness의 가중합을 최소화하는 것을 나타내는데, 첫 항목은 총 OEM 오더들의 총 납기지연을, 두 번째 항목은 AS 오더들의 총 납기지연을 각각 나타낸다. 두 납기지연은 가중치에 의해 조정된다. 식(4)는 각 작업은 한 스테이지에서 가공 가능한 기계에 한에 한 번만 할당되어야 한다는 제약을 표현한다. 식(5)은 기계 별, 일 별 capacity 제약을 표현한다. 좌변에 표현된 기계 kd일에 할당된 작업 시간 합은 우변에 표현된 각 기계(k)가 d일에 총 가능한 작업시간보다 같거나 작아야 한다. 식(6)는 작업 순서에 따른 precedence relation과 선후 작업의 시작 시간 제약을 표현한다. 좌변의 첫 번째 수식은 선행하는 스테이지 j에서의 작업일 d에 작업시간을 더한 값을 나타내고, 두 번째 부분은 후속 스테이지 j+1에서의 작업일을 나타내는데, 그 값은 첫 번째 항의 값보다 같거나 크다. 식(7)는 각 오더의 납기지연(ti)를 계산하는 표현식이다. 식(8)은 결정 변수의 이진정수조건, 식(9)은 결정변수가 비음의 실수임을 나타낸다.
참고로 수리 모형에서 그리스문자로 표기된 모수들은 공정과 제품의 기준정보에 의해서 추출되는 상수 값이고, 영문 대문자로 표기된 모수들은 오더 정보와 작업자 일정 계획 등에 따라 생산계획 수립 시 변경되는 상수 값을 나타낸다.
1단계의 결과는 각 로트가 어느 기계에서 가공될지 모두 결정하지만, 그 결과를 2단계에 투입될 때는 3가지 방식으로 사용될 수 있다. Case 1은 모든 스테이지에서 각 로트에 특정 기계를 지정, Case 2는 첫 번째 스테이지에서만 특정 기계를 지정, Case 3은 결과를 바탕으로 일별 투입 순서만 설정하는 것이다. 이에 대한 논의는 5장 사례 연구에서 자세히 설명된다.

4.2 2단계: 스케줄링을 위한 디스패칭 규칙

공정 중에는 두 가지 경우의 선택 상황이 발생한다. 첫 번째는 job 디스패칭 상황으로, 한 기계에서 가공이 완료된 로트는 다음 스테이지에 도착할 때, 해당 스테이지의 기계 중 해당 품번의 로트를 가공할 수 있는 기계들이 모두 가공 중이면 그 로트는 해당 스테이지에서 대기하게 되고, 가공 가능한 기계가 가용하게 될 때, 그 가공을 마친 기계는 대기 중인 로트 중에서 선택을 하게 되는데, 이때 미리 지정된 디스패칭 규칙이 적용된다. 본 연구에서는 납기지연을 최소화하기 위해 널리 사용되는 EDD(Earliest Due Date), MDD(Modified Due Date), MST(Minimum Slack Time) 규칙과 더불어 문제의 특성을 고려한 몇 가지 디스패칭 규칙을 제안한다. 두 번째는 기계 디스패칭 상황으로, 하나의 로트가 어느 스테이지에 도착할 때, 2개 이상의 기계가 가용하면 그 로트는 기계 중 하나를 선택해야 한다. 이때는 앞서 제시한 EDD 등의 디스패칭 규칙을 사용할 수 없으므로, 기계 선택과 관련된 선택 규칙이 필요하다.

4.2.1 Job 디스패칭 규칙

시뮬레이션은 수리 모형의 Planning 결과를 Input으로 하여 작업 순서를 부여하는 것이 목적이다. 기계 앞에 여러 개의 오더가 대기하고 있을 때, 가공을 마치고 가용하게 된 기계가 어떤 로트를 선택하여 가공할 것인지에 대한 규칙이다. 디스패칭 규칙에서 고려하고 있는 사항은 다음과 같다.
1) 납기 지연 최소화(MDD),
2) 기계 가동률 향상(MAM),
3) 셋업 시간 최소화(MSeT),
4) 병목 공정 회피(WINQ).
납기 지연 최소화를 위해 개발된 많은 디스패칭 규칙이 있다. 예를 들어, EDD(Earliest Due Date)는 maximum tardiness를 최소화 할 수 있고(Jeong and Kim, 1998), MDD는 납기와 현재 기계에서의 가공 시간을 고려하는 규칙으로 Max{d, t+d}값이 가장 작은 로트를 선택하는데 총(또는 평균) tardiness를 최소화하는데 좋은 성과를 보여준다고 알려져 있다(Kim et al., 2003). MST(Min Slack Time)는 대기 중인 로트 중 Slack (s=d-r-t)이 가장 작은 로트를 선택하는 규칙이며, 이는 납기에서 가공시간을 뺀 여유시간이 적은 로트를 선택하는 규칙이다. 여기서 d는 납기, t는 현재 시간, p는 현재 공정에서 가공시간, r은 남은 공정의 총 가공시간을 나타낸다. 본 연구에서는 MDD 규칙을 사용한다. MDD 규칙은 jobshop에서뿐만 아니라, HFS에서도 총 Tardiness를 최소화하는데 효과적이다(Kang, 2018).
MAM(Min Available Machines, 최소 가공 가능 설비 수)은 대기열 중에서 가공할 수 있는 기계의 수가 가장 적은 로트를 선택하는 규칙이다. 대기열에 하나의 기계에서 밖에 가공될 수 없는 A 로트와, 여러 대의 기계에서 가공이 가능한 B 로트가 있다면 A 로트를 우선적으로 기계에 할당한다는 의미이다. 이는 설비 가동률을 향상하는데 기여할 수 있다. B 로트는 향후 B 로트를 가공할 수 있는 다른 기계가 가용하게 될 때 가공될 수 있으며, 가공 가능한 설비가 이미 다른 로트를 가공하여 로트가 대기하는 상황을 미연에 방지할 수 있다.
MSeT(Min Setup Time) 규칙은 Setup Time이 적은 오더를 우선적으로 할당하겠다는 의미이다. 로트들은 각의 유사성에 따라 순서 의존적 셋업 시간이 모두 주어진다. WINQ(Work in Next Queue) 규칙은 다음 공정이 수행될 기계에 부하가 가장 작은 작업(대기 중인 로트 수가 가장 작은)을 선택한다. 이는 거시적인 측면에서 병목공정을 회피하기 위해서 사용될 수 있다(Holthaus and Rajendran, 1997).
시뮬레이션 상에서는 위에서 제안한 4가지 고려 사항을 가중 합의 형태로 합산하여 점수가 가장 작은 로트를 선택한다. 가중 합은 아래와 같이 계산될 수 있다.
(10)
z=w1MDD+w2MAM+w3MSeT+w4WINQ
각 디스패칭 규칙의 값은 arctangent 함수와 평행이동을 이용하여 범위로 변환되어 각 값의 크기와 범위를 통일한다. 가중치 wi는 실험에 의해 최적값을 설정할 수도 있겠으나, 본 연구에서는 4 가지 고려 사항의 상대적 중요도에 의해서 실무적으로 결정한다. 일반적으로 셋업 시간을 줄이는 것이 makespan을 감소하는 효과를 보여서 유사 제품을 연속 투입하는 경향이 있는데, 셋업 타임을 감소시키고자 비슷한 품번만 연속해서 생산하면, 후속 공정에서 어느 특정 기계만 가동되는 현상이 발생할 수 있다. 따라서 전체적인 설비 가동률을 고려하고 특정 기계가 병목공정이 되는 것을 방지하기 위해, 셋업 시간이 증가하더라도 다른 종류의 로트를 교대로 투입하는 방법도 고려하여야 한다.

4.2.2 기계 디스패칭 규칙

한 로트가 현재 기계에서 작업이 완료되고 기계가 2대 이상 가용하면, 머신 디스패칭 규칙을 사용하여 다음 기계를 선택한다. 다양한 방법을 고려할 수 있겠으나, 본 연구에서는 다음의 규칙을 사용한다.
1) 셋업 시간 최소화(MSeT): 후보 기계의 이전 로트와 유사성이 높은 기계에서 가공한다.
2) SPT(Shortest Processing Time): 설비에 따라 가공시간이 다른 경우, 가공시간이 짧은 기계에서 가공한다.
실제로는 뒤 두 규칙을 합산하여, 셋업 시간과 가공시간의 합이 작은 기계를 선택한다.

5. 사례 연구

5.1 실험 대상 제조 시스템

본 연구에서 실험한 대상 기업은 국내 자동차 제조업의 1차 협력업체로 자동차 엔진용 스파크 플러그 제조업체이다. 스파크 플러그 제조 공정은 크게 CF(냉간단조) 공정, CM(선반가공 및 용접) 공정, 도금 공정, 그리고 조립 및 검사 공정(SAS)으로 이루어져 있으며, 본 연구에서는 조립 및 검사 공정만을 고려한다. 조립공정은 7 스테이지로 이뤄져 있으며, 이종 병렬 기계가 배치된 공정은 전반부 4개 공정이다. 첫 공정은 자동조립기 공정으로 6기가 있으며, 주간 6기, 야간 3기만 가동된다. 두 번째 공정은 용접 공정, 세 번째는 절단, 네 번째는 굽힘 공정이고, 외관 검사, 중축 및 선 패킹 검사, 내전압 검사 공정이 이어진다. 각 공정별 기계 대수는 Figure 2를 참조할 수 있다. Figure 2는 또한 어떤 3개 주문이 생산 가능한 경로(현업에서는 생산 버전이라 함)의 예시를 보여주고 있다. 예를 들어, 첫 번째 스테이지의 이종 병렬 기계 중, 주문 1 로트는 2, 6번 기계에서 가공이 가능하며 주문 2는 4번 기계에서, 주문 3은 3번 기계에 각각 가공될 수 있다. 두 번째 스테이지에서 주문 1은 1, 2번 기계에서, 주문 2는 3번 기계에서, 주문 3은 2, 3번 기계에서 각각 가공될 수 있다. 이처럼 각 오더는 각 스테이지별로 가공 가능한 기계가 다르다.
이 생산 라인에서는 총 370여 종의 제품을 생산 가능하나, 실질적으로는 145개 품종을 생산하고 있으며, 주당 평균 100여 개의 주문을 생산하고 있다. 각 주문에는 품번에 따라 OEM 용 생산과 AS 용 생산으로 나눠지며, 업종의 특성상 OEM용 생산의 납기는 우선적으로 지켜야 한다. 로트 사이즈는 5520개이며, 각 로트는 최대 7개 스테이지에서 가공되어야 한다.

5.2 실험 조건 및 데이터

대상 기업의 2017년 전반기 6개월 실제 생산 자료로부터 OEM과 AS용 주문의 비율을 적용하여 가상의 주문 목록을 만들었다. 이 주문 목록은 주간 생산 기준 88개의 로트로 구성되어 있으며, 총 30개의 주문 목록을 생성하여 실험하였다. 30개의 주문 목록별로 납기일을 2가지 버전(납기일 기본, 기본 + 1일)으로 총 60개 실험 데이터를 생성하였다.
MILP 모형에서 기계 평균 가동률(ρ)는 실제 가동률을 감안하여 85%로 설정하였으며, OEM 주문의 납기지연에 대한 가중치(α)는 0.9, 디스패칭 규칙의 가중치는 w1 = 103, w2 = 102, w3 = 10, w4 = 1로 실무자와의 협의 하에 결정하였다. 이는 각각의 규칙을 순서대로 우선 적용하되, 동률 발생 시 tie-break 규칙으로 이하의 디스패칭 규칙을 사용한다는 것을 뜻한다.
1단계 생산계획을 위한 수리 모형은 Excel add-in 소프트웨어인 Solver Foundation2.0과 Microsoft OML을 이용하여 모델링 되었고, 상용 MILP Solver 중 가장 빠른 것으로 알려진 Gurobi 7.5.2를 이용하였다(Amsterdam Optimization Modeling Group LLC, 2009; Campbell and Nikoukhah, 2018; Mittelmann, 2017). 2단계 생산 일정 계획 수립을 위해 해당 공정은 Rockwell Software의 Arena® ver.14.7로 모델링 하였고, 모든 실험은 인텔 i7 (2.4GHz) CPU, 메모리 8GB가 설치된 PC를 이용하여 실시하였으며, 모든 실험에서 30분 내에 주어진 모형의 해를 도출하였다.

5.3 실험 결과

1단계에서 나온 결과가 2단계에 투입될 때는 다음과 같이 4가지 방식으로 사용될 수 있다.
1) Dispatching Only: 디스패칭 규칙만 사용(1단계 사용하지 않음)
2) Priority +Dispatching: 1단계 결과를 바탕으로 우선순위만 설정하고 디스패칭 규칙 적용
3) Stage 1 + Dispatching: 첫 번째 스테이지의 기계만 1단계 결과를 활용하여 특정 기계 지정
4) All: 1단계 결과를 모든 스테이지에서 적용하고, 보조적으로 디스패칭 규칙 사용
첫 번째 Dispatching Only는 제안된 방법을 사용하지 않고 전통적인 디스패칭 규칙만을 사용하는 것이고, 네 번째는 제안된 방법이고, 두 번째와 세 번째는 그 중간 수준에서 섞어 사용하는 방법이다. 아래 Table 1은 위의 4가지 실험 조건에 따른 시뮬레이션 결과 값의 평균을 보여준다. 전체 평균으로 보면, 제안된 방법론을 적극적으로 사용할수록 해의 성능이 낮아지는 것으로 보인다. 실제 All 방법이 극단적으로 나쁜 성능을 보이는 것은 각 스테이지에서 기계 디스패칭 규칙을 전혀 사용할 수 없기 때문에 가공 가능한 유휴 기계가 있어도 할당된 기계가 가용할 때까지 버퍼에서 대기를 하게 되기 때문이다. 그러나 실제 시뮬레이션 기반의 의사결정에서는 다양한 실험 결과를 활용하여 최선의 선택을 할 수 있다.
Table 2는 각 방법별로 60회의 실험에서 OEM tardiness가 작은 등수의 요약한 것이다. 총 60회의 실험 중 Dispatching Only가 34회 가장 좋은 결과를 보이긴 하나, Priority + Dispatching 조합 방법과 Stage 1 + Dispatching 조합 방법도 역시 각각 13회와 18회 가장 좋은 해를 가진다. 1위와 2위의 총개수가 각각 65회와 63회로 실험 횟수인 60회보다 많은 것은 동률이 있었기 때문이다.
실험 결과를 볼 때, All 조합 방법은 위에 설명한 대로 기계 디스패칭 규칙을 사용할 수 없어서 항상 나쁜 결과를 보이지만, 나머지 세 가지 방법은 항상 우위를 점하는 방법은 존재하지 않으므로, 3가지 방법으로 모두 실험 후 최선의 결과를 선택하면 항상 기존의 디스패칭 규칙만 사용할 때보다 같거나 나은 결과를 보장하게 된다. 이렇게 Dispatching Only 방법을 포함한 3가지 방법을 모두 사용하고 최선의 방법을 선택할 경우, OEM Tardiness를 기준으로 총 60회의 실험 중 26회에서 1단계 결과를 활용할 경우 더 나은 결과를 보이며, OEM Tardiness 평균은 32.6으로 Dispatching Only에 비해 4.1% 감소함을 알 수 있다. 1단계 수리 모형의 결과를 활용하여 Dispatching Only 방법보다 작은 OEM Tardiness를 보이는 26개 사례만을 추출하여 3가지 조합 방법의 평균 OEM Tardiness를 구하면 Table 3과 같다. 이 26개 사례만을 보면 조합된 방법을 사용할 때, 평균 OEM Tardiness는 9.2% 감소한다. All 방법을 제외한 모든 조합 방법에서 Makespan은 유의미한 차이를 보이지 않았다.

6. 결 론

본 논문에서는 전용 병렬 기계가 있는 HFS에서 가중 납기 지연을 최소화하기 위한 생산 일정 계획 문제를 다루었다. 전용 병렬 기계 때문에 야기되는 기계 간의 부하 불균형 문제를 해결하기 위해 문제를 2단계로 구분하여, 1단계에서는 기계의 부하를 고려한 작업 할당 문제로 모형화하고, 2단계에서는 디스패칭 규칙을 이용하여 스케줄링 하는 방법을 제안하였다. 1단계 문제는 MILP 모형을 만들고 상용 솔루션을 이용하여 해를 도출하였으며, 2단계 디스패칭 규칙으로 MDD를 적용하되 Tie Break를 위한 3가지 새로운 디스패칭 규칙을 제안하였다. 제안된 방법론을 검증하기 위하여 HFS 형태의 제조 시스템의 실제 자료를 바탕으로 수리 모형과 시뮬레이션 모형을 만들고, 실제 생산 자료를 바탕으로 주문 목록을 생성하여 실험을 실시하였다. 실험 결과, 제안된 방법과 디스패칭 규칙만 사용하는 기존의 방법을 조합하여 사용하는 것이 납기 지연을 감소시킬 수 있었다.
이번 연구에서는 새로 제안된 3가지 디스패칭 규칙의 성능 평가를 위한 독립적인 실험이 실시되지 않았으며, 이는 추후 연구로 지속할 예정이다. 또한, 디스패칭 규칙 간의 상대적 가중치에 따라 디스패칭 규칙의 우선순위가 결정되는데, 상황에 따라 또는 스테이지 별로 독립적인 최적의 가중치 조합을 결정하는 연구가 필요하다. 이를 위하여 기계 학습 기법을 적용할 수 있을 것으로 기대한다.

REFERENCES

Amsterdam Optimization Modeling Group LLC 2009. "“Modeling with Excel+OML, a Practical Guide.”." http://www.amsterdamoptimization.com/models/msf/oml.pdf, accessed 11/8/2019..

Brah, Shaukat A 1996. "“A Comparative Analysis of Due Date Based Job Sequencing Rules in a Flow Shop with Multiple Processors.”." Production Planning & Control 7(4):362-73.
crossref
Campbell, Stephen L, and Nikoukhah, Ramine 2018. "“Introduction to OML”." In Modeling and Simulation with Compose and Activate. In Campbell Stephen L, Nikoukhah Ramine (eds.), Cham. Springer International Publishing. pp 9-60.
crossref
Choi, Hyun-Seon, and Lee, Dong-Ho 2007. "“A Branch and Bound Algorithm for Two-Stage Hybrid Flow Shop Scheduling: Minimizing the Number of Tardy Jobs.”." Journal of the Korean Institute of Industrial Engineers 33(2):213-20.

de Fátima Morais, Márcia, and et al 2014. "“Multicriteria Hybrid Flow Shop Scheduling Problem: Literature Review, Analysis, And Future Research.”." Independent Journal of Management & Production 5(4):1004-31.

Fattahi, Parviz, Hosseini, Seyed Mohammad Hassan, Jolai, Fariborz, and Tavakkoli-Moghaddam, Reza 2014. "“A Branch and Bound Algorithm for Hybrid Flow Shop Scheduling Problem with Setup Time and Assembly Operations.”." Applied Mathematical Modelling 38(1):119-34.
crossref
Gupta, Jatinder ND 1988. "“Two-Stage, Hybrid Flowshop Scheduling Problem.”." The Journal of the Operational Research Society 39(4):359-64.
crossref pdf
Holthaus, Oliver, and Rajendran, Chandrasekharan 1997. "“Efficient Dispatching Rules for Scheduling in a Job Shop.”." International Journal of Production Economics 48(1):87-105.
crossref
Huang, Wanzhen, and Li, Shanling 1998. "“A Two-Stage Hybrid Flowshop with Uniform Machines and Setup Times.”." Mathematical and Computer Modelling 27(2):27-45.
crossref
Jeong, K-C, and Kim, Y-D 1998. "“A Real-Time Scheduling Mechanism for a Flexible Manufacturing System: Using Simulation and Dispatching Rules.”." International Journal of Production Research 36(9):2609-26.
crossref
Jun, Choi Yu 2015. "“A Genetic Algorithm for Minimizing Total Tardiness with Non-identical Parallel Machines.”." Journal of the Society of Korea Industrial and Systems Engineering 38(1):65-73.
crossref
Kang, Jun-Gyu 2018. "“A Simulation Based Scheduler Development for Hybrid Flow Shop.”." Proceedings of the Annual Conference of the Korea Society for Simulation. 514-19.

Kim, Bong-jin, and Cho, Dong-Bock 2005. "“A Genetic Algorithm to Minimize Total Weighted Tardiness on Two Types of Nonidentical Parallel Machines.”." Journal of the Korean Society of Maintenance Engineers 10(1):23-31.

Kim, Yeong-Dae, Shim, Sang-Oh, Choi, Bum, and Hwang, Hark 2003. "“Simplification Methods for Accelerating Simulation-Based Real-Time Scheduling in a Semiconductor Wafer Fabrication Facility.”." IEEE Transactions on Semiconductor Manufacturing 16(2):290-98.
crossref
Lee, Geun-Cheol, and Yeong-Dae, Kim 2004. "“A Branch-and-Bound Algorithm for a Two-Stage Hybrid Flowshop Scheduling Problem Minimizing Total Tardiness.”." International Journal of Production Research 42(22):4731-43.
crossref
Mittelmann, Hans D 2017. "“Latest Benchmarks of Optimization Software.”." INFORMS Annual Meeting. Houston, TX.

Ruiz, Rubén, and Vázquez-Rodríguez, José Antonio 2010. "“The Hybrid Flow Shop Scheduling Problem.”." European Journal of Operational Research 205(1):1-18.
crossref
Sudipta, Saha 2017. "“Simulation-Based Decision Support Framework for Hybrid Flow Shop (HFS) Scheduling Problem.”." MSc Dissertation,. Graduate School of Engineering, Seoul National University; available at http://hdl.handle.net/10371/137370..

Yoon, Sungwook, Ko, Daehoon, Kim, Jihyun, and Jeong, Sukjae 2013. "“A Study on Combinatorial Dispatching Decision of Hybrid Flow Shop: Application to Printed Circuit Board Process.”." Journal of Korean Institute of Industrial Engineers 39(1):10-19.
crossref pdf

Figure 1.
A schematic view of general HFS (source: Fattahi et al., 2014)
jksqm-47-4-823f1.jpg
Figure 2.
The schematic view of the experimented HFS in this study
jksqm-47-4-823f2.jpg
Table 1.
Average KPI of the proposed approaches
Method OEM Tardiness (hours) AS Tardiness (hours) Maximum Completion Time (hours)
1) Dispatching Only 34.0 7.8 140.0
2) Priority + Dispatching 35.8 7.5 140.2
3) Stage 1 + Dispatching 36.5 7.3 139.9
4) All 50.7 8.8 155.2
Table 2.
The count of rankings for each method
Method Rank sum
1 2 3 4
1) Dispatching Only 34 14 12 60
2) Priority + Dispatching 13 31 16 60
3) Stage 1 + Dispatching 18 18 24 60
4) All 60 60
sum 65 63 52 60 240
Table 3.
Average OEM Tardiness of 26 cases that Dispatching Only rule was defeated
Average OEM Tardiness
1) Dispatching Only 37.1
2) Priority + Dispatching 33.6
3) Stage 1 + Dispatching 33.9
Total Average 35.4
TOOLS
PDF Links  PDF Links
PubReader  PubReader
ePub Link  ePub Link
Full text via DOI  Full text via DOI
Download Citation  Download Citation
  E-Mail
  Print
Share:      
METRICS
0
Crossref
172
View
5
Download
Related article
Editorial Office
13F, 145, Gasan digital 1-ro, Geumcheon-gu, Seoul 08506, Korea
TEL: +82-2-2624-0357   FAX: +82-2-2624-0358   E-mail: ksqmeditor@ksqm.org
About |  Browse Articles |  Current Issue |  For Authors and Reviewers
Copyright © Korean Society for Quality Management. All rights reserved.                 developed in m2community
Close layer
prev next