장치이상을 고려한 동적 생산계획 최적화 모델 개발
하진국·이의수† 동국대학교생명화학공학과
100-715 서울시중구필동 3가 26 (2005년 8월 5일접수, 2005년 9월 5일채택)
A Development of the Optimization Model for Reactive Scheduling Considering Equipment Failure
Jin-Kuk Ha and Euy Soo Lee†
Department of Chemical & Biochemical Engineering, Dongguk University, 26, 3-ga, Pil-dong, Chung-gu, Seoul 100-715, Korea (Received 5 August 2005; accepted 5 September 2005)
요 약
불연속화학공정은소비자수요에탄력성있게대처할수있는장점이있는반면에그특유의동특성때문에복잡 하고, 계획된조업시간과실제조업시간사이에서외란(disruption) 또는불확실변수(uncertainty)에의한차이가자 주발생하는단점이있다. 이에, 본논문에서는예측생산계획(predictive scheduling)에의해결정된생산계획에서미 래에발생하는공정변수값의변화를실시간으로예측생산계획을수정, 제시하여주는생산계획시스템인동적생 산계획(reactive scheduling) 기법을개발하였다. 불확실인자를고려한동적생산계획에서, 본논문에서는장치이상
(equipment failure)이발생하였을때공정운전조건의변화를실시간으로반영하여, 예측생산계획(predictive scheduling)
모델에의하여제시된전체생산계획을최대한유지하고공정변수의변화를실시간으로반영하기위하여 right shift rescheduling과 total regeneration 기법을사용하였다. 또한, 불확실인자의발생전후의 predictive scheduling과 reactive scheduling 간의변화정도를측정하는수단인 schedule stability 위하여, 본논문에서는수정된 sequence deviation과
percentage change in makespan을사용하여제안된동적생산계획의안정성을측정하였다. 본논문에서제안한동적 생산계획시스템은기존에제시되었던경험법칙에의한결과값에비해좋은결과를보여주었다.
Abstract− We propose a new optimization framework for the reactive scheduling. The proposed rescheduling scheme is specially focused on how to generate rescheduling results when equipment failure occurs. The approach is based on a continuous-time problem representation that takes into account the schedule in progress, the updated information on the batches still to be processed, the present plant state, the deviations in plant parameters and the time data. To update the predictive scheduling, we used right shift rescheduling and total regeneration when equipment failure occurs. And, a practical solution to the rescheduling problem requires satisfaction of two often confliction measures: the efficiency measure that evaluates the satisfaction of a desired objective function value and the stability measure that evaluates the amount of change between the schedules before and after the disruption. In this paper, the efficiency is measured by the makespan of all jobs in the system. And, the stability is measured by the percentage change in makespan and the mod- ified sequence deviation in the predictive scheduling and rescheduling.
Key words: Reactive Scheduling, Optimization, Machine Failure, Uncertainty
1. 서 론
오늘날글로벌시장경쟁에서시간과가격에서의효과적인생산계 획이더욱중요시되고있다. 따라서, 제품의생산계획(production
scheduling)은제조공정에서중요한역할을담당하고있다. 그러나
불연속화학공정은소비자수요에탄력성있게대처할수있는장
점이있는반면에그특유의동특성때문에복잡하고, 계획된조업
시간과실제조업시간사이에서외란또는불확실변수(uncertainty)
에의한차이가자주발생하는단점이있다. 일반적으로생산계획 을고려하는데있어서대부분의연구에서는공정의변수값들이생 산공정의전공정시간까지결정론적이며어떠한변화가일어나지 않는다고가정하여생산계획문제를다루어왔다. 이러한공정의변 수가결정론적인경우(deterministic case)의생산계획은제품을생 산하는운전의관리와원료의수습, 원료의할당과같은계획된작
†To whom correspondence should be addressed.
E-mail: [email protected]
업들을위하여항상선행되어왔다. 그러나회분식생산공정은그 특유의동특성적인환경때문에계획된조업과실제조업사이에서장 치이상, 원료의공급지연, 제품의생산시간변경등의외란(disruption)
또는불확실변수(uncertainty)에의한차이가자주발생한다. 이러한 외란은이미결정된생산계획즉예측생산계획(predictive scheduling)
의효율성을낮추며, 더는새로운환경에적용할수없게된다. 이에 외란이발생하였을때의생산계획문제는더는예측생산계획의문 제가아니고동적생산계획(reactive scheduling)의문제가된다. 동 적생산계획은외란이발생하였을때새로운환경에서생산계획을 실행할수있게예측생산계획을새롭게형성시키는작업이라고할 수있으며, 또한외란의영향을최소화시키기위한실질적이고강 제적인생산공정의운전작업이다. 앞서언급한바와같이, 지금까 지최적예측생산계획에관한연구와예측생산계획의목적함수에 대한최적화를위한방법에관한연구에많은노력이행해졌으며,
이러한연구는조합의최적화에관한최적예측생산계획을수식화 하는데있다.
불연속화학공정의실제운전상황에서결정된공정변수값들의 변동이나, 공정의 운전상황에서예기치 않는불확실 변수들을
rescheduling factors라고한다. 생산공정의환경에서발생하는
rescheduling factors는갑작스런파업(strike)과같은전혀알수없 는인자(complete unknowns), 작업자의숙련도에의해발생하는미 래에대한추론(suspicions about the future) 그리고장치이상, 원료 의부족등과같이일반적으로자주발생할수있는알려진인자
(known uncertainties)로구분할수있다. 예측생산계획모델에서불 확실변수가발생했을때실시간으로최적생산일정계획을수정제 시하여주는동적생산계획모델전략에는 robust scheduling, right shift rescheduling, regeneration 그리고 partial rescheduling 등의전 략들이있다. 공정의운전상황에서외란이발생하였을때, 공정의 변화에빠르게대처하고그다음단계의대책을세우는것이가장 좋은방법이나, 불연속화학공정에서는예측하기어려운부분이많 이발생하므로외란발생시에도영향을적게받는방안을마련하 고변화의추세를미리예측하여생산계획모델을강건하게할필 요가있다. 이와같이통계적인데이터를기초로앞으로의변화추 세를나타내는파라미터를이용한통계적인기법을사용하여외란
(disruption)이발생하여도이를흡수할수있도록강건한예측생산
계획을세우는기법을 robust scheduling이라한다. Robust scheduling
은실제생산공정에서외란이발생하였을때빠른대처가어려우며,
외란과통계데이터값의차이가발생하면목적함수가계속증가하여 좋지않은결과를가져온다. Right-shift rescheduling은 Fig. 1에서
와같이장치 U1에서 Tbreak시간에장치고장이일어났을때장치
U1의고치는시간인 Trepair동안제품의처리를중단하였다가장치
U1이정상이되면공정을계속하도록하는기법으로 Fig. 1과같이
Gantt chart를오른쪽으로이동시켜계속공정운전을할수있도록
하는동적생산계획기법이다. 즉, 장치 U1가정상이되는시간동 안이후제품들에대한각공정에서의조업시작시간을늦추는생산 계획기법이다. Partial rescheduling은공정의운전상황에서외란이 발생했을경우, 직·간접적으로영향을받는생산관련변수및소비 자변수만을 rescheduling 하는 기법이다. 이러한 이유로 partial rescheduling을 ‘affected operations rescheduling’이라고도 한다.
Regeneration은공정의운전상황에서장치이상등과같은외란이
발생한시점, 즉 rescheduling point에서공정의운전상황에서외란
의영향을받지않는변수들뿐만아니라공정을시작하지않은변수 모두에대하여새롭게 rescheduling하는기법이다. 이러한이유로 total regeneration 또는 complete regeneration 이라고도한다.
동적생산계획(Rescheduling) 문제는예측생산계획(predictive scheduling)의연구에비해최근에와서야연구되었다. Hasebe 등[2]은
다품종 회분식공정에서 reordering 알고리즘을이용하여 initial
scheduling을수정하는모델을발표하였다. Wu 등[3]은단일장치에 서의장치이상(machine failure)이발생하였을때 initial scheduling
과 new scheduling의각단위공정에서의시작시간(starting time)과
생산순서(production sequence)의차이와조업완료시간을최소화하
는 rescheduling 기법을발표하였다. Unal 등[4]은새로운작업이발 생하였을때전체생산계획의순수납기지연(tardiness)과전체생산 시간(total flow time)을최적화하는기법을개발하였으며, 단일장치 에서장치이상시순수납기지연을최적화하는 rescheduling은 Ronan
등[11]에의해제안되었다. 또한, Carlro와 Jaime[12]는다품종회분 식공정에서새로운작업(jobs)이발생하였을때 rescheduling을위 한MILP 모델을발표하였다. Carlro에의해제안된 rescheduling 모 델은 local reordering과장치의재할당기법을이용하였다.
본논문에서는 UIS 저장운용방안을채택한다품종회분식공정 에서장치이상이발생하였을때, 예측생산계획(predictive scheduling)
에의해결정된최적생산계획을미래에발생하는공정변수값의변 화에대해실시간으로수정제시하여주는생산계획시스템인동적 생산계획(reactive scheduling) 기법을개발하였다. 불확실인자를고 려한동적생산계획에서장치이상(equipment failure)이발생하였을 때공정운전조건의변화를실시간으로반영하여예측생산계획
(predictive scheduling) 모델에의하여제시된전체생산계획을최 대한유지하면서, 공정변수의변화를실시간으로반영하기위하여
right shift rescheduling과 total regeneration기법을사용하였다. 또한, 불 확실인자의발생전후의 predictive scheduling과 rescheduling 간의변 화정도를측정하는수단인 schedule stability 측정을위하여, 본논문 에서는수정된 sequence deviation과 percentage change in makespan
을사용하여제안된동적생산계획의안정성을측정하였다. 2. 다품종 회분식 공정에서 장치이상을
고려한 동적 생산계획
먼저, 회분식공정의운전상황에서장치이상이발생하였을때, Fig. 1. Right-shift rescheduling on Gantt chart.
장치이상이예측생산계획에의해결정된전체생산일정계획에미 치는영향을알아보면다음과같다.
(1) 실제생산공정상황에서장치이상혹은고장이발생하게되
면, 예측생산계획모델에의해결정된생산일정계획을불가피하게 일부또는전체생산공정에서의조업시작시간을조절해야한다.
(2) 생산제품들의 due date를맞추기위해서는일부또는전체
제품의생산순서를변경해야하는상황이발생하게된다. (3) 장치고장으로인해직·간접으로영향을받는제품및장치
를분류하여새롭게작업(task)을재활당해야한다.
본논문에서는이러한영향들을고려하여실시간으로대처할수 있는동적생산계획모델을개발하였다. 그리고공정의운전상황에 서발생하는예기하지않은 rescheduling factors에대한동적생산 계획의연구에서요구되는특징은공정변수값이특정한값으로고 정되어있을경우에대한예측생산계획모델로부터결정된전체 생산계획을최대한유지되어야하며, 얼마나빨리대처해야하는가 에달렸다. 따라서불확실변수가발생하였을때예측생산계획모 델에서결정된전체생산계획의변화정도를평가하고측정할수 있는기준(criteria)이필요하다. 즉, 동적생산계획(rescheduling)에서 는불확실인자의발생전후의 predictive scheduling과 rescheduling
간의변화정도를측정하는수단(measures)을요구한다. 이러한수
단(measures)에는다음세가지그룹으로나눌수있다. (1) schedule efficiency, (2) schedule stability 그리고 (3) cost로나눈다. Schedule
efficiency에는공정의조업시간과관련하여측정하는수단으로일
반적으로 생산계획에서의 최종조업완료시간(makespan), mean tardiness, mean flow-time 그리고 maximum lateness를측정수단으 로사용한다. 생산계획의안정성(Schedule stability)은생산공정의 수정이필요하지않은예측생산계획에서는의미가없으나, 동적생 산계획환경에서는아주중요한측정수단으로알려졌다. 이를불 규칙한공정운영을측정한다고하여 ‘impact of schedule change’
라불리기도한다. 이러한측정수단으로는 predictive scheduling과
rescheduling 간의각단위공정에서의시작시간(starting time)과제 품생산순서(sequence)의차이를분석하는두가지방법이있으며, Abumaizar와 Sevstka[6]이제안한최종조업완료시간의 percentage
change 등이있다. 이들방법에대한측정방법은다음과같다.
(1) 제품생산순서의차이를측정하는방법은 Watatani와 Fujii[5]
가제안한방법을사용하였으며, 제품생산순서(sequence)의차이를 측정하는방법은아래와같다.
For every machine j:
For every job i on machine j in the rescheduling:
Define:
S1=set of operations processed before job i in the predictive scheduling
S2=set of operations processed after job i in the rescheduling S=Nij=cardinality of S
Sequence deviation = (1)
(2) 조업시작시간(starting time)의차이를측정하는것은 rush
order cost와원료의조기도착등에외란이발생하였을때경제적
측면에서의중요한측정수단이며장치설비에관계된동적생산계 획 알고리즘에서는유용한측정방법으로알려졌다. 이방법은
Wu 등[3]에의해제안되었다. 조업시간의차이는두개의요소로 구성되어있으며다음과같다.
delay=the sum of the positive differences in ending times, and rush=the sum of the absolute value of negative difference in ending
times
starting time deviation=delay+rush (3) Percentage change in makespan (P)
(2)
여기서, Mmethod= MR, MA또는 MT. MR은 right shift rescheduling
의최종조업완료시간, MA는 affected operations rescheduling의최 종조업완료시간을나타내며, MR은 total regeneration의최종조업완 료시간을나타낸다. M0은예측생산계획의최종조업완료시간을의 미한다.
본논문에서는 schedule efficiency는대상공정에서의최종조업완 료시간(makespan)을사용하였으며, schedule stability를측정하기위 하여식 (2)에주어진최종조업시간의 percentage change를이용하 여예측생산계획과본논문에서제안한동적생산계획간의 schedule stability를측정하였다. 또한, predictive scheduling과 rescheduling
간의각단위공정에서의제품생산순서(sequence)의차이를측정하 는방법인식 (1)을수정하여, 다품종회분식공정에서의제품생산
순서(sequence)의차이를적용하였다. 이는본논문에서동적생산
계획을위한대상공정인다품종회분식공정의운영특성상생산순 서가결정되면각단위공정에서의생산순서는일정하기때문이다.
따라서, 식 (1)은다음식 (3)과같이수정될수있다.
Sequence deviation = (3)
여기서, cardinality of J는단위공정의총개수를의미한다.
2-1. UIS 운용방안을 채택한 다품종 회분식 공정에서의 rescheduling 기법
2-1-1. Deterministic scheduling with UIS
Predictive scheduling은불연속화학공정의모든공정변수값들 이특정한값으로고정되어있을경우의생산계획모델로본논문 에서고려한생산공정은 UIS 운영방안을채택한다품종회분식공 정을대상으로하였다. 공정변수값들의고정되어있을경우의상 세일정계획(short-term scheduling) 문제를위하여, 본논문에서는사
건의시작과끝만을결정하는이진변수(binary variable)만이필요한
연속시간표현기법과장치의할당을위한시간간격을나타내는 time slots(or time events)을 기초로한 MILP(mixed-integer linear pro- gramming) 모델을이용하였다. 이는장치이상(machine failure)이발
생하였을때 reschedule을위하여필요한정보는고장이난장치
jbreak, 고장이발생한시점(rescheduling point) Tbreak, 장치이상을보
수하는시간 Trepair그리고고장이발생한시점에서의각단위공정
의 운영상태이다. 앞에서언급한정보들중 jbreak, Tbreak 그리고
S1∩S2
Nij
∑j
∑i
P Mmethod–M0
M0
---
⎩ ⎭
⎨ ⎬
⎧ ⎫×100
=
Nij
∑j
∑i
cardinality of J ---
Trepair정보는장치이상이발생하였을때결정되는데이터값들이지 만, 각단위공정에서의운영상태를알기위해서는각단위공정에 서제품들의공정시작시간(starting time), STkj과끝나는시간(ending
time), ETkj을알고있으면쉽게각공정의운영상태를알수있으
며, 또한 장치 jbreak에서 고장이발생한 시점(rescheduling point)
Tbreak에의해직·간접적으로영향을받는제품들을분류하기가용이
하기때문이다.
다품종회분식공정의상세일정계획은목적함수인최종조업완료 시간을최소화하는문제로구성된다.
Minimize (4)
먼저, 모든생산은생산순서에따라정확히할당되어야하며, 이 진변수 Xik는다음의제약식을만족하여야한다.
Allocation constraints:
(5) (6)
이진변수 Xik은다음과같이정의된다.
Time slot k에있는단위공정 j를위한시작시간 STkj와끝나는시
간 ETkj는다음과같이정의된다. Sequencing constraints
(7)
여기서, Pij는단위공정 j에서의제품 i의공정시간(processing time)
이다.
주어진경로에서연속적인단위공정 j와 j+1 사이의시간은식 (8)
과같이표현되고식 (9)는연속적인 time slot 사이의관계를나타 내는식이다.
(8) (9)
여기서 는마지막단위공정, 는마지막 time slot을의미한다.
이상과같이 MPC에서 UIS 운용방안을채택한다품종회분식공
정에서의최종조업완료시간을최소화하는식은식(4)와같으며제 약조건은식(5)-(9)로표현된다.
2-1-2. Right-shift rescheduling approach
Right shift rescheduling은장치이상이발생하였을때계획된예 측생산계획(predictive scheduling)에의해결정된스케줄을실행할
수있도록필요한시간(장치수리시간, Trepair)만큼각단위공정에서
남아있는제품의시작시간과끝나는시간을연기하는기법이다.
본논문에서는회분식공정에서장치이상이발생하였을때 right shift rescheduling을위하여다음과같은가정을설정하였다.
- 각단위공정은특정시간에서하나의제품만생산할수있다.
- 전체단위공정에서제품의우선권조업(preemptions)은허락하지 않는다.
- 특정시간에장치이상이발생하였을때 Trepair동안에는다른단 위공정에서외란은발생하지않는다.
- 장치이상이발생한시점, Tbreak그리고장치수리시간, Trepair
- Tbreak에장치이상이발생한단위공정에서조업중인제품 i는
reschedule 된다.
위가정에서마지막가정인 Tbreak에장치이상이발생한단위공정
에서조업중인제품 i는 reschedule 된다는의미는 Fig. 2에서와같
이 Trepair시간동안일시적으로중간저장조에저장후장치이상이
발생한단위공정이수리된후즉시투입되어공정을재시작한다는 의미이다.
Predictive scheduling(deterministic schedule)은 앞에서 언급한
MILP 모델식을이용하여먼저계산된다. 따라서, 모든이진변수 Xik
는각단위공정에모든제품들을할당하며연속변수들은정해진 제품의순서와각단위공정에서시작시간과끝나는시간에따라공
정운영을시작하게된다. 만약특별한시간, Tbreak에단위공정 jbreak
에서장치이상이발생하였을때, 장치이상의영향을반영하기위하 여새로운제약조건및집합이도입된다. 장치이상이 Tbreak에단위 공정 jbreak에서발생하고, 고치는시간 Trepair이요구되는 right shift
rescheduling은다음알고리즘을통하여고려될수있다.
Step 1: Predictive schedule에서의할당된각단위공정에서의제 품순서를위하여이진변수 Xik를고정한다.
Step 2: Step 1은장치고장에의하여영향을받지않는제품 i와
time slot k에대한 right shift rescheduling 단계이다.
For ( ) {
IF ( and )
{
}
IF (j=jbreak) and ( and )
{
} }
Makespan ET≥ kj
Xik
k K∑∈ =1 ∀i I∈
Xik
k I∑∈ =1 ∀k K∈
Xik 1 if product i is manufactured in time slot k,
0 otherwise,
⎩⎨
=⎧
ETkj–STkj XikPij ∀ k K j J∈ , ∈
i I∑∈
=
STkj+1–ETkj≥0 ∀ k K j J j∈ , ∈ –{ }
STk+1j–ETkj≥0 ∀ k K k∈ –{ }, j J∈
j k
j J k K∈ , ∈
j j≠ break STkj<Tbreak
STkj=STkjr
ETkj=ETkjr
STkj<Tbreak ETkj≤Tbreak
STkj=STkjr
ETkj=ETkjr
Fig. 2. Operation strategy on machine jbreak when machine failure occurs.
Step 3: 장치고장에의하여영향을받는 product i와 time slot k
에대한 right shift rescheduling 단계이다. 또한, 장치고장이발생한 단위공정 jbreak에서의 shift starting times(=Trepair)을 위한 time constraints 조건식이추가된다.
For (j=jbreak, ) {
Case 1: IF ( )
{ }
Case 2: IF ( and )
{
} }
Step 4: 각단위공정에서남아있는제품의시작시간과끝나는시
간의재설정으로인하여아래식과같이목적함수가변경된다. Minimize
Fig. 3, 4와 5는 right shift rescheduling의 Step 2과 Step 3의단
계를설명하기위해특별한시간 Tbreak에단위공정 jbreak에서장치
이상이발생하였을때각단위공정의상태를간트차트(Gannt chart)
로나타내었다. Fig. 3(a)는 predictive scheduling에의해결정된각 단위공정에서의공정상황을그림으로나타내었으며, Fig. 3(b)는단
위공정 3에서특별한시간 Tbreak에장치이상이발생하였을때장치
수리시간(=Tbreak) 동안 right shift rescheduling한간트차트로 Step 2
에서와같이장치이상으로영향을받지않는작업들인 P3, P4의 값과같다는것을알수있다.
Fig. 4(a)는 predictive scheduling에의해결정된각단위공정에서 의공정상황을그림으로나타내었으며, Fig. 4(b)는 jbreak인단위공정
3에서특별한시간 Tbreak에장치이상이발생하였을때장치수리시간
(=Trepair)으로 right shift rescheduling 한간트차트로 Step 3에서의
case 1과같이장치이상으로직접적으로영향을받는작업인 P3의시
작시간이 일경우에는 를만족해
야함을알수있다.
Fig. 5(a)는 predictive scheduling에의해결정된각단위공정에서 의공정상황을그림으로나타내었으며, Fig. 5(b)는 jbreak인단위공
정 3에서특별한시간 Tbreak에장치이상이발생하였을때장치수
리시간(=Trepair)으로 right shift rescheduling한간트차트로 Step 3
에서의 case 2와같이장치이상으로직접적으로영향을받는작업
인 P3의시작시간이 그리고 일경우에
는 와 를만족해야함
을알수있다.
2-1-3. Total regeneration approach
Total regeneration은제품의생산공정에서외란이발생하였을때외 란에의해직·간접적으로영향을받는제품과외란이발생한시점 에서공정을시작하지않은제품을 reschedule하는기법이다. 따라서, initial schedule(predictive scheduling)에의해서결정된정보로부터외 란이발생한시점에서동적생산계획을위한필수적인데이터를분류,
추출이필요하다. 외란이발생하였을때새로운스케줄을위해예측 생산계획(predictive scheduling)에서얻어지는정보는다음과같다.
k K∈
STkj>Tbreak
STkjr ≥Tbreak+Trepair j∀ =jbreak,k K k∈ –{ }
STkj>Tbreak ETkj>Tbreak
STkj STkjr and ETkjr STkjr XikPij+Trepair i I∑∈r
+
= ≥
j
∀ =jbreak, k K k∈ –{ }
Makespan ET≥ kjr
STkj=STkjr
STkj>Tbreak STkjr ≥Tbreak+Trepair
STkj<Tbreak ETkj>Tbreak
STkj=STkjr ETkjr STkjr XikPij i I∑∈ r Trepair
+ +
≥
Fig. 3. Case of Step 2 on right shift rescheduling.
Fig. 4. Case 1 of Step 3 on right shift rescheduling.
- the present state
- production order of products i in machine j - starting & ending times of product i in machine j
또한, 장치이상이단위공정 j에서특별한시간, Tbreak에발생하였 을때다음과같은데이터를분류할수있다.
- the entire set of jobs not processed at Tbreak,
- the set of jobs affected directly or indirectly by machine failure on unit j,
- the set of jobs not affected by machine failure on unit j, - - the entire set of time slots not processed at Tbreak,
- the set of time slots affected directly or indirectly by machine failure on unit j,
- the set of time slots not affected by machine failure on unit j, -
따라서, total regeneration은단위공정 j 에서 Tbreak시간에장치 이상이발생하였을때대상공정의예측생산계획을수정·보완하기 위하여집합 Kr에대하여동적생산계획(rescheduling) 기법인 total
regeneration을실행한다. 이를위하여다품종회분식공정의생산계
획모델인 MILP 수학적모델은다음과같이수정되며, 새로운제
약조건식 (13), 식 (17)과식 (18)이추가된다.
Minimize (10) Allocation constraints
(11) (12) (13) Sequencing constraints
(14) (15) (16) (17) (18)
식 (13)은데이터분석에의해분류된집합 은장치이상이
발생하였을때생산공정에서영향을받지않는제품군으로예측생 산계획에서할당받은 time slot에 Xik=1이되게고정한다. 식 (17)은 장치이상이발생한단위공정이비워져있을때제품의시간에대한 제약조건이다. 식 (18)은장치이상이발생한단위공정에서장치이상 이발생한시점에서공정을마치지못한제품의끝나는시간에대 한제약조건이다.
3. 적용 예제
Guo와 Nonaka[7]는다품종회분식공정에서장치이상이발생하
였을때 right shift scheduling 기법을이용하여각단위공정에서의 시작시간을변경하였을때 initial scheduling의최종조업완료시간의 변화를최소화하는제품생산순서를결정하는 robust scheduling 기 법을제안하였다. 본예제에서는 Guo에의해제안된기법과본논
문에서제안한 rescheduling 기법을비교하였다. 본예제의문제는
Guo가발표한논문을인용하였다. 예제는 7개의다른생산물로이 루어진다. 각생산물은단계당하나의장치를가지는 3개의단위공 정을거치며, 모든제품의각단위공정에서의생산시간은 Table 1과
같다. Guo에의하면 Fig. 6에서와같이다품종회분식공정에서장
치이상이발생하였을때 initial scheduling의최종조업완료시간의변 화를최소화하는생산순서로 P3-P1-P5-P4-P2-P7-P6으로결정하였 으며최종조업완료시간은 82 h이다. Guo의 initial scheduling을단 위공정 2에서장치이상이 Tbreak=12 h에서발생하고, 단위공정 2의 장치수리시간, Tbreak=6 h일때 right shift rescheduling에적용하여 계산한결과를 Fig. 7에 Gannt chart로나타내었다. 이때의최종조 업완료시간은 83 h이다.
Guo의예제를본논문에서제안한기법을적용하였다. 예측생산 계획에의한최적조업순서는 P5-P1-P3-P6-P4-P7-P2이며, 최종조
INPr IAPr
INAPr
Ir=INAPr ∪IAPr
KNAr
KAAr
KNAAr
Kr=KNAAr ∪KAAr
Makespan ET≥ kjr
Xik=1
k K∈∑r ∀ i I∈ r
Xik=1
i I∑∈r ∀ k K∈ r
Xik=1 ∀ i I∈ NAPr , k K∈ NAAr
ETkjr STkjr XikPij i I∑∈r
– ≥ ∀k K∈ r, j J∈
STk j 1r,+ – TE kjr ≥0 ∀k K∈ r, j J j∈ –{ }
STkr+1 j,≥ETkjr ∀ k K∈ r–{ }k ,j J∈
STkjr ≥Tbreak+Trepair ∀ k K∈ r, j j= break ETkjr STkjr XikPij
i I∑∈r Trepair
+ +
≥ ∀ k K∈ AAr , j j= break
INAAr
Fig. 5. Case 2 of Step 3 on right shift rescheduling.
업완료시간은 80 h이다. Fig. 8은예측생산계획에대한최적해를
Gannt chart로나타내었다. 또한, Guo의 initial scheduling에적용 한장치이상의정보를적용하여, 본논문에서제안한 right shift rescheduling에적용한결과를 Fig. 9에 Gannt chart로나타내었다.
본논문에서제안한 right shift rescheduling에의해계산된최종조 업완료시간은 80 h이며, 또한수정된 MILP 모델식 (10)-(18)에적
용한최적화된 total regeneration 기법을적용한최종조업완료시간
은 80 h로제안한 right shift rescheduling의값과같은결과를보 였으며, Guo와 Nonaka[7]가제안한 robust schedule 보다좋은결 과를보였다. 최적화된동적생산계획(rescheduling)의 total regeneration
결과는 Fig. 10에나타내었다. 최적제품생산순서는 P5-P1-P3-P6- P4-P2-P7이다. 본예제의예측생산계획, right shift rescheduling과
total regeneration에의해계산된제품순서, 최종조업완료시간, 수 정된 sequence deviation과 percentage change of makespan을비 교한결과는 Table 2와 Table 3에나타내었다.
Table 1. Data for example (flowshop under UIS) Product
unit P1 P2 P3 P4 P5 P6 P7
Unit 1 15 7 9 28 1 1 7
Unit 2 5 4 14 11 17 8 2
Unit 3 14 2 18 9 4 3 4
Fig. 6. Gantt chart for example of Guo proposed on flowshop under UIS.
Fig. 7. Gantt chart for example of Guo-right shift rescheduling on flowshop under UIS.
Fig. 8.Gantt chart for example of predictive scheduling on flow- shop under UIS.
Fig. 9. Gantt chart for example of the right shift rescheduling on flowshop under UIS.
Fig. 10. Gantt chart for example of the total regeneration on flow- shop
Table 2. Results of compare with Guo’ schedule for example (flowshop under UIS)
Initial scheduling of Guo Predictive scheduling Product order P3-P1-P5-P4-P2-P7-P6 P5-P1-P3-P6-P4-P7-P2
Makespan 82 h 80 h
Makespan in right shift
rescheduling 83 h 80 h
Percentage change
in makespan 1.2％ 0％
Table 3. Results of the proposed rescheduling for example (flowshop under UIS)
Predictive scheduling Right shift rescheduling Total regeneration
Product order P5-P1-P3-P6-P4-P7-P2 P5-P1-P3-P6-P4-P7-P2 P5-P1-P3-P6-P4-P2-P7
Makespan 80 h 80 h 80 h
Sequence deviation - - 1
Percentage change in makespan - 0％ 0％
4. 결 론
불확실인자를고려한동적생산계획에서장치이상(equipment
failure)이발생하였을때공정운전조건의변화를실시간으로반영
하여예측생산계획(predictive scheduling) 모델에의하여제시된전 체생산계획을최대한유지하면서, 공정변수의변화를실시간으로 반영할수있는 right shift rescheduling과 total regeneration을위한
MILP 모델식을 개발하였다. 또한, 불확실인자의발생 전후의
predictive scheduling과 rescheduling 간의변화정도를측정하는수단 인 schedule stability 측정을위하여, 본논문에서는수정된 sequence deviation과 percentage change in makespan을사용하여제안된동적 생산계획의안정성을측정하였다. 이러한 schedule stability 측정은
right shift rescheduling과 total regeneration의선택기준을제시해 준다.
감 사
본연구는한국과학재단의특정기초연구(R01-2002-000-00007-0)
의연구비지원에의해이루어졌으며지원해주신한국과학재단에깊 은감사를드립니다.
사용기호
i : product
j : unit
: the last unit
jbreak : the unit of occurring equipment failure k : time slot
: the last time slot
Pij : processing time for the product i on unit j STkj : starting time for unit j on the time slot k ETkj : ending time for unit j on the time slot k
: starting time for unit j on the time slot k under rescheduling : ending time for unit j on the time slot k under rescheduling Trepair : repairing time on the jbreak
: the entire set of jobs not processed at Tbreak
: the set of jobs affected directly or indirectly by machine failure on unit j
: the set of jobs not affected by machine failure on unit j
Ir :
: the entire set of time slots not processed at Tbreak : the set of time slots affected directly or indirectly by
machine failure on unit j
: the set of time slots not affected by machine failure on unit j
Kr :
참고문헌
1. Pinto, J. M. and Grossmann, I. E., “A Continuous Time Mixed Integer Linear Programming Model for Short Term Scheduling of Multistage Batch Plants,”Ind. Eng. Chem. Res., 34(9), 3037- 3055(1995).
2. Hasebe, S., Hashimoto, I. and Ishikawa, A., “General Reorder- ing Algorithm for Scheduling of Batch Process,”Journal of Chemical Engineering of Japan, 24(4), 484-489(1991).
3. Wu, D. S., Storer, R. H. and Chang, P. C., “One-Machine Reschedul- ing Heuristics whth Efficiency and Stability as Criteria,”Comput- ers and Operation Research, 20(1), 1-14(1993).
4. Unal, A. T., Uzsoy, R. and Kiran, A. S., “Rescheduling on a Sin- gle Machine with Part-Type Dependent Setup Times and Dead- lines,”Annals of Operation Research,70, 93-113(1997).
5. Watatani, Y. and Fujii, S., “A Study on Rescheduling Policy in Production Systems,”Processings of the JAPAN/USA Sympo- sium on Feasible Automation, ASME,2, 1147-1150(1992).
6. Abumaizar, R. J. and Sevstka, J. A., “Rescheduling Job Shops Under Random Disruption,”INT. J. PROD. RES., 35(7), 2065-2082(1997).
7. Guo, B. and Nonaka, Y., “Rescheduling and Optimization of Schedules Considering Machine Failures,”Int. J. Production Economics, 60(61), 503-513(1999).
8. Alagöz, O. and Azizo lu, M., “Rescheduling of Identical Paral- lel Machines Under Machine Eligibility Constraints,” European Journal of Operational Research, 149(3), 523-532(2003).
9. Li, R.-K., Shyu, Y.-T. and Adiga, S., “A Heuristic Rescheduling Algorithm for Computer-Based Production Scheduling Systems,”
INT. J. PROD. RES., 31(8), 1815-1826(1993).
10. Wu, H.-H. and Li, R.-K., “A New Rescheduling Method for Computer Based Scheduling Systems,”INT. J. PROD. RES., 33(8), 2097-2110(1995).
11. Ronan O’Donovan, Reha, Uzsoy and Kenneth, N. Mckay, “Pre- dictive Scheduling of Single Machine with Breakdowns and Sensitive Job,”INT. J. PROD. RES., 37(18), 4217-4233(1999).
12. Carlos, A. M. and Jaime, C., “A MILP Reactive Scheduling Frame- work for Resource-Constrained Multistage Batch Facilities,”
FOCAPO 2003, 335-338(2003).
13. Abumaiza, R. J. and Svestka, J. A., “Rescheduling Job Shops Under Disruptions,”INT. J. PROD. RES., 2065-2082(1997).
j
k
STkjr
ETkjr
INPr
IAPr
INAPr
INAPr ∪IAPr
KNAr
KAAr
KNAAr
KNAAr ∪KAAr
