한국산학기술학회논문지 Vol. 10, No. 7, pp. 1702-1710, 2009 강용하 1, 이영섭 2, 신현준 2* 1 노스캐롤라이나주립대학교산업공학과, 2 상명대학교경영공학과 Problem space based search algorithm for manufacturing process with rework probabilities affecting product quality and tardiness Yong Ha Kang 1, Young Sup Lee 2 and Hyun Joon Shin 2* 1 Dept. of Industrial and Systems Engineering, North Carolina State University 2 Dept. of management Engineering, Sangmyung University 요약본논문은 rework 발생확률을고려하는병렬기계스케줄링문제를위해문제공간기반탐색알고리즘을제안한다. 각기계와작업유형별로 rework 발생확률이존재하며이것은자동화된공정에서과거데이터로부터산출가능하다. 스케줄링문제의데이터벡터 ( 가공시간, 납기, 셋업시간, rework확률 ) 를교란시킴으로써이웃해를생성하고이로부터도출된해는 EDDR이라는효과적인휴리스틱을이용하여평가한다. 제안된알고리즘은납기지연의최대값과 rewok 발생작업수로평가함으로써제품의품질과납기수준을동시에고려할수있도록한다. Abstract In this paper, we propose a problem space based search(psbs) algorithm to solve parallel machine scheduling problem considering rework probabilities. For each pair of a machine and a job type, rework probability of each job on a machine can be known through historical data acquisition. Neighborhoods are generated by perturbing four problem data vectors (processing times, due dates, setup times, and rework probabilities) and evaluated through the efficient dispatching heuristic (EDDR). The proposed algorithm is measured by maximum lateness and the number of reworked jobs. We show that the PSBS algorithm is considerably improved from the result obtained by EDDR. Key Words : Rework Probabilities, Parallel Machines, Scheduling, Problem Space Based Search 1. 서론 최근제조업체들은제품의생산방식과과정이복잡해지고다양해지면서생산능력을효율적으로사용하는데어려움을겪고있다 [3]. 제조공정의효율성을방해하는대표적인요인들로는불량발생으로인한재작업 (rework). 순서의존적인작업준비시간 (sequence - dependent setup time) 과작업투입시점 (release time) 등을들수있다. Rework는반도체산업뿐만아니라많은제조산업에서도중요한이슈이다 [4]. 만일공정에서불량품이발생 한다면재작업을하거나버려지게되는데이때발생하는비용은기업에게부담을가져올수있으므로불량률을줄이기위한효과적인생산관리가필요하다. Uzsoy et al.[12,13] 는반도체공정과같은고가의설비를운용하며, 순서의존적인작업준비시간과작업투입시점이존재하는제조공정은일정계획을수립할때, 단순하고직관적인수작업방식들을사용한다면생산성및비용측면에서효과적인결과를기대하기가힘들다고밝히고있다. 일반적으로순서의존적인작업준비시간이존재하는경우, 그스케줄링결과에따라서자원의가동률과그에따른납기준수율이크게좌우된다 [5]. 작업투입시점은일반적으 이논문은 2007년정부 ( 교육인적자원부 ) 의재원으로한국학술진흥재단의지원을받아수행된연구임 (KRF-2007-313-D00901) * 교신저자 : 신현준 (hjshin@smu.ac.kr) 접수일 09년 05월 25일수정일 09년 06월 25일게재확정일 09년 07월 22일 1702
로 BOM(bill of material) 상의하위부품조달조달시점또는해당작업의전공정완료시점에의해결정되는데, 작업투입시점이존재하는제조환경에서는기계의유휴시간을최소화하기위해정확한스케줄링이필요하다. Rework와관련한대부분의논문들은 rework 제품의재고관리와재고정책에따른최적의 lot수량을결정하는것들이고근래에들어서 rework 정책을 dispatching규칙과연관지은논문들이발표되었다. Kuhl & Laubisch[6] 는반도체공정에서 dispatching rule과 rework 전략이생산성에가장큰영향을주는두가지요소라고간주하고 5가지의 dispatching 규칙과세가지 rework 전략중어떤조합이가장높은생산성을얻을수있는지에관하여시뮬레이션을통해비교분석하였다. Sha et al.[9] 는반도체포토공정 (photolithography) 의 dispatching을통해전체공정이운용된다고보고고객의납기를만족시키고동시에높은제품품질을얻기위해서는 rework 전략과 dispatching 규칙을적절하게사용해야한다고말했다. 이때세가지의 rework전략과세가지 dispatching 규칙의조합으로시뮬레이션을수행하였다. 본논문에서논의할문제를정리해보면다음과같다. 병렬기계가있고다양한종류의제품타입을갖는작업들이기계에서가공된다. 이때기계와제품타입마다가공시서로다른 rework 확률이존재하고, 제품타입별로순서의존적인작업준비시간과작업별로작업투입시점이존재한다. Rework 확률은작업이어떤기계에서가공되는지에따라서달라질수있으며이는기계자체의특성에의한것이다. 만일임의의기계에서가공을마친작업이불량판정을받았을경우, 양품합격을받을때까지 rework 절차를거친다. 즉 rework이발생하지않을때가지작업이기계군중하나에서반복적으로투입, 가공과정을거치게된다. [ 그림 1] 은이와같은전체시스템을설명하고있다. [ 그림 1] 전체시스템구성도 이상에서논의된문제를효율적으로해결하기위해서는 1)rework 확률을반영한 dispatching 알고리즘과 2)dispatching 알고리즘을통해생성된작업투입순서를보다효과적으로개선하기위한탐색알고리즘의개발이필요하다. 여기서 2) 의탐색을위한알고리즘은자동화된공정에서요구되는신속성을감안해서일정시간내에의사결정을내릴수있도록고안되어야한다는점이중요하다. 따라서본논문에서는 rework 확률, 납기, 작업준비시간등의공정데이터의속성을이용하여문제공간기반탐색 (problem space based search; 이하 PSBS) 기법을사용하는효율적인알고리즘을개발하는것을목표로한다. 목적함수로는납기준수와품질비용측면에서납기지연시간 (lateness time) 의최대값 ( 이하 ) 을최소화하는것이고다른하나는재가공작업수 (number of reworks; 이하 ) 을최소화하는것이다. 본논문에서제안하는 PSBS 알고리즘의성능을평가하기위해초기해로사용되는 rework을고려한 dispatching 알고리즘과비교하여얼마만큼의성능향상을보여주는지실험을통해보여준다. 본논문은다음과같이구성되어있다. 2장에서는본논문이다루고있는문제를정의하였고 3장에서는본논문이제안한 PSBS 병렬기계알고리즘에대하여기술되어있고 4장에서는다양한환경하에서실행된실험결과및분석을, 마지막으로 5장에서결론및추후연구과제를제시한다. 2. 문제정의 본연구에서는 와 을각각최소화하기위해 rework 가능성이존재하는상황에서 개의작업을 개의병렬기계에스케쥴링하는알고리즘을제시한다. 개의작업은같은제품타입 (product type) 을갖는 개의작업군으로나뉘고, 이때작업군 를제품타입이 인작업들의집합이라한다. 작업군 에속한작업들의인덱스를 라고했을때, 이들작업 는각각납기 (due date) 와작업투입시점 (release time) 를갖는다. 각작업 의가공시간 (processing time) 는작업들이기계에서처리되는순서및가공기계와는독립적으로주어지지만작업준비시간은작업들이가공되는순서와속한작업군에따라달라지는순서의존적인준비시간 (sequence dependent setup times) 을갖는다. 여기서순서의존적인작업준비시간이란작업군 에속 1703
한국산학기술학회논문지제 10 권제 7 호, 2009 한작업 의가공을마친후작업군 에속한작업 를준비하는데소요되는시간을 라할때, 인 성질을갖는작업준비시간을의미한다. 물론작업 와 가같은제품군에속한다면 이다. 이때작업군 에속한작업 가기계 에서가공을한후불량판정을받아서재가공을할확률은 이다. 라는시점에기계 이가공중이던작업 ( ) 의가공을완료한후유휴 (idle) 상태가되어투입작업으로작업 ( ) 가선택되었다고하자. 현재 rework확률이존재하기때문에작업 는기계 에서가공을완료한후다시가공을해야만하는상황이발생할수도있다. 만일작업 가기계 에서가공을완료한후 rework판정을받지않을경우에는작업준비시간과가공시간의합인 만큼의시간이소요되지만 rework 판정을받을경우에는 뿐만아니라재가공에필요한시간이더필요하게된다. 이시간을 라고한다면 은재작업판정을받은작업이기계앞으로돌아가대기하다가다시기계에투입될때까지의추정체재시간 (Estimated Sojourn Time) 이라고할수있다. Rework가발생하지않아서가공을바로마칠수있을확률은 (1- ) 이고 rework가발생하여다시기계앞으로돌아가대기할확률은 이므로결국평균적으로작업 를기계 에서가공할경우가공을위해필요한시간은 (1- ) + 라고할수있다. 이를예상가공시간 (Expected Processing Time, 이하 ) 이라고하자. 기계 에작업 를투입하는시점이 이므로작업 는 +(1- ) + 에가공을완료하게되는데이를예상완료시간 (Expected Completion Time, 이하 ) 이라고한다. (1- ) + (1) (1- ) + [Notation] (2) : 작업인덱스 : 제품타입인덱스 : 제품타입이 인작업들의작업군인덱스 ): 병렬기계인덱스 : 작업군이 인작업 j 를기계 에서가공했을 : 작업 j 때재가공확률 (rework probability) 의가공시간 (processing time) s c'c : 제품타입이 인작업 j가투입되기직전에그기계에서가공을완료한작업의제품타입이 일때작업준비시간 (setup time) : 작업 j 의납기 (due date) : 작업 j 의투입가능시간 (release time) : rework 판정을받은작업 j 의추정체재시간 : 제품타입이 인작업 j가투입되기직전에그기계에서가공을완료한임의의작업의제품타입에대한평균작업준비시간 (average setup time), 즉 재가공시체재시간인 는 rework시한번의가공이더발생하게되므로 는작업을가공시필요한시간인 보다같거나큰시간이라고할수있다. 왜냐하면 작업 보다우선순위가높은다른작업들이있다면바로기계에투입되지못하여대기하는시간이발생할수도있기때문이다. 그러므로재가공하는데소요되는시간인 는 ( ) 로나타낼수있다. 여기서 은재가공시간결정모수로서본연구에서는실험을통하여 값을결정하여사용한다. 3. 제안알고리즘 문제공간기반탐색 (Problem space based search : PSBS) 은 Storer et al.[10] 에의해처음제안된이웃해생성방법으로많은스케쥴링문제에서그성과를보여주고있다. Leon & Ramamoorthy는자원제약스케쥴링문제 (resource constrained scheduling)[7] 와유연흐름생산라인스케쥴링문제 (flexible flow line scheduling)[8] 에서 PSBS는우수한성능을보일뿐아니라여러가지스케쥴링문제에서다양하게적용될수있다는점을보여주었다. Avic et al.[2] 는단일기계에서전체가중납기지연값을최소화하는문제를 PSBS를통해해결하였고 Turkcan & Akturket[11] 은생산비용과전체가중납기지연값을통시에최소화하는문제에서 PSBS를적용하여효과적인해를제시하였다. 본논문에서는병렬기계에서재작업확률 (rework probability), 순서의존적인작업준비시간과작업투입시점이존재할때 PSBS를이용하여 와 를최소 1704
화하기위한효과적인스케쥴링방안을제시하고자한다. 3.1 문제공간기반이웃해이장에서는 Storer et al.[10] 가제안한이웃해생성방법인문제공간기반이웃해 (Problem space based neighborhoods: 이하 PSBN) 에관하여기술한다. 다양한국지탐색기법 (local search method) 이근사알고리즘에적용되어왔는데대표적인국지탐색기법으로는타부탐색 (tabu search), 유전알고리즘 (genetic algorithm), 시뮬레이티드어닐링 (simulated annealing) 등이있다 [1]. 스케쥴링문제에서해를구한다는것은일반적으로기계에투입할작업들의순서를정해주는것이라고할수있다. 기존국지탐색방법들이스케쥴링문제에서적용될때정해진해 ( 작업순서 ) 안에서작업들의위치를서로바꾸거나 (swap) 어떤작업을다른위치로이동 (insert) 시킴으로써즉, 기존의작업순서 (job sequence) 를변경하여새로운스케쥴을생성하는방식으로이웃해를생성시킨다. 이것을해공간기반이웃해 (solution space based neighborhoods) 라고할수있다. 대부분의국지탐색방법들이이런식으로최적해값을찾거나일정시간이경과할때까지탐색을계속진행해나간다. 반면 Storer et al.[10] 가제안한 PSBN의방식은정해진해를기반으로이웃해를생성하는것이아니라문제가가지고있는특성을이용하여이웃해를생성한다. 이것이바로 PSBN이다. PSBN은문제가가지고있는특성요소를변동시킨후문제에특화된휴리스틱을이용하여작업순서를만들어줌으로써이웃해를생성해나간다. 이렇게생성된이웃해를평가할때는변형되기전문제특성요소를새로만들어진작업순서에적용하여구해진값을이용한다. 스케쥴링문제에서 를문제를구성하는요소의데이터값 ( 예 : 가공시간, 납기등 ) 의벡터라고하고 를문제에맞는휴리스틱이라고하자. 이때생성되는해 ( 작업순서 ) 는 라고정의할수있다. PSBN에서는데이터값벡터인 를변형 (perturbation) 시키고이를휴리스틱에적용하여새로운이웃해 ( 작업순서 ) 를만든다. 이때변형된데이터벡터들의집합 는식 (3) 과같다. (3) 이때, 는문제의원래데이터값의벡터이고 는임의로생성된데이터값을변동시키는벡터로보통균일분포 (uniform distribution) 로부터생성 된다. 는변동폭을조절하는모수 (perturbed range control parameter) 로서그값은 PSBS 성능에큰영향을끼치게되므로적절한값을찾아서이용하여야한다 [12]. 만일 가 0이면 perturb 성질은사라지게되어원래의데이터를 base heuristic을이용하여푼것이된다. 반면에 가무한대로커지면데이터가심하게변동이되기때문에임의로작업순서를결정하게되는효과를주게된다. 이렇게만들어진 개의데이터벡터 를휴리스틱인 에적용하면 개의새로운이웃해 ( 작업순서 ) 가얻어지게된다. 즉, 이웃해집합 는다음의식 (4) 와같다. (4) 변동데이터값은단지새로운작업순서를얻기위한것이고목적함수값을평가할때는적절하지않다. 실제필요한목적함수값을구하기위해서는변동되기전의데이터가필요하다. 를목적함수값이라고한다면 로정의할수있으며목적함수값의집합 는다음의식 (5) 와같다. (5) 이렇게구해진 중에서문제가요구하는목적함수에따라 가목적함수값으로최종적으로선택된다. 3.3 베이스휴리스틱 (h) Leon & Ramamoorthy[9,10] 에따르면 PSBS에사용되는 heuristic은다음의두가지요구사항을충족시켜야한다. 첫번째로좋은해값을보장해야하며두번째로계산시간이짧아야한다. PSBS의매반복마다휴리스틱 가사용되기때문에만일사용되는 의성능이좋지않다면이는임의탐색 (random search) 과다를바없게된다. 또한계산시간도매탐색마다 에걸리는시간이포함되기때문에만일 자체의탐색시간이길어진다면전체탐색시간은증가하게될것이다. 따라서본논문에서는위의사항들을고려하여 dispatching 알고리즘인 EDDR (Earliest Due Date with Rework probability) 을휴리스틱 로제안한다. 본논문에서제안하는 PSBS 알고리즘에대한자세한설명에앞서 EDDR 휴리스틱을간략히설명하면다음과같다. EDDR 알고리즘은유휴 (idle) 상태인기계가발생할경우적용된다. 이때그기계에서가공했을때 rework 확률이가장작은작업타입인작업들이속한작업군을선호 1705
한국산학기술학회논문지제 10 권제 7 호, 2009 작업군이라하고그렇지않은작업군을비선호작업군이라고한다. 마찬가지로어떤작업타입을가공했을때 rework될가능성이적은기계를선호기계라하며그렇지않은기계를비선호기계라한다. 은 를갖는작업을기계에투입할작업으로최종선정하고유휴기계에투입한다. 즉, rework확률을고려하여대상작업의완료시간을계산하여가장빨리작업을완료할수있는작업을기계에투입하는것이다. [EDDR 알고리즘절차 ] Step 1. 작업분류 1. 현재 queue에있는작업들을작업타입별로분류기계가유휴상태가된시점을 라할때 인작업 와 rework판정을받아서기계앞으로되돌아와서대기중인작업 를작업타입별로분류한다. 2. 작업타입별로분류된작업들을납기가빠른순서 (Earliest Due Date:EDD) 로정렬 Step 2. 대상작업군 선정 1. 선호작업군 step 1에서 EDD로정렬된작업들중가장선두에있는작업을 에포함 2. 비선호작업군모든비선호작업군에대하여선호기계에서먼저투입된작업의가공이종료되는순간까지기다린후, (a) 가공을했을때의예상완료시간 ( ) 과 (b) 현재유휴 (idle) 상태가된기계에서가공했을때의예상완료시간 ( ) 을비교하여 (a)>(b) 인작업들중가장 EDD인작업을선택하여 에포함 Step 3. 대상작업군에서투입할 job 선택 1. 에포함된작업들의현재유휴상태인기계에서의예상완료시간 ( ) 을계산 2. 위단계에서계산한예상완료시간이가장빠른작업을기계에투입 END. Step 1은현재스케쥴링시점 에서기계앞에서자신의가공순서를기다리는작업들 ( 새로주문된작업들과 rework 판정을받고다시기계앞으로돌아온작업들 ) 을 EDD로정렬시킴으로써현재타입별로가장급한작업이무엇인지알기위한단계이다. Step 2는 step 1에서분류된작업순서에의해선호작업군과비선호작업군에서각각후보작업들을선별하는단계이다. step 3에서는 step 2에서선별된후보작업들을대상으로실제기계에투입될작업을선정하는단계이다. 대상작업군 에포함된작업들을현재유휴한기계에서가공했을때각작업들의 를계산하여그중가장작 3.4 문제공간기반탐색알고리즘실험에의하면단순히 EDDR을이용하여구한해는다른할당규칙인 EDD, MS, ATCS 보다는좋은해를보여주지만, dispatching 알고리즘이라는근시안적특성의한계를벗어나지못하기때문에최적해에근접한해 (Near optimal solution) 를보장해주지못한다. 따라서본연구에서는문제공간기반탐색알고리즘 (problem Space Based Search : PSBS) 을통해 EDDR의한계점을보완하여효과적인생산계획을수립하고자한다. 앞의두절에서는문제공간 (PS) 의개념과 PSBS에서사용될기본휴리스틱방법에대하여알아보았다. 본절에서는 PSBS 알고리즘에관하여설명하고자한다. PSBS 는목적함수가 와 을최소화시키는것이기때문에탐색방법으로최대하강법 (steepest descent method) 을이용한다. 즉, 어떤데이터를기준으로일정횟수의이웃해를생성한후그중최고의목적함수값을갖는이웃해를찾아내고다시그이웃해의데이터를기준으로탐색을반복한다. 이런방법으로정해진탐색횟수만큼탐색을완료하면알고리즘은종료된다. 를변동을시킬때기준이되는데이터의개수라하고, 를그데이터를기준으로생성되는이웃해의개수라고하면총탐색횟수는 가된다. 다음은위에서설명한문제공간기반탐색알고리즘의탐색방법이다. [PSBS algorithm 절차 ] Step 0. ( 초기화 ) 기준데이터, 목적함수값설정, Do (S=1 to ) Do (i= 1 to ) Step 1. ( 데이터변동 ) 기준데이터로변동데이터생성 Step 2. ( 이웃해생성 ) 변동데이터를 EDDR에적용하여이웃해생성 1706
Step 3.( 목적함수값평가 ) 생성된이웃해에원래데이터를대입하여목적함수값계산 계산된목적함수가현재최우수목적함수값보다작으면최우수목적함수값변경하고그때의변동데이터를최우수데이터로설정, 이면, End. Step 4. ( 기준데이터값변경 ) S를 1증가시키고기준데이터값변경, End. Step 0은데이터를변동시키기위하여기준이데이터를설정하는단계이다. 여기서원래의문제데이터벡터인 가탐색의기준데이터벡터 가된다. 목적함수의경우 PSBS를적용하기전 EDDR을사용하여구한값을초기목적함수값으로놓는다. 즉, 원래의문제데이터벡터 를 EDDR에적용하여생성한이웃해 에 를대입한값인 가초기목적함수값이된다. 다음으로 Step 1부터 Step 3까지가생성되는이웃해의수인 만큼반복된다. Step 1은기준데이터를변동시키는과정이다. 3.1 절에서설명한것처럼기준데이터 에변동값 를더하여변동데이터 를생성한다. Step 2에서는 를기본휴리스틱인 EDDR에적용하여새로운이웃해 를생성한다. 목적함수값을평가할때는원래데이터인 를이용해야하므로 Step 3에서는 에 를대입하여목적함수값 를구한다. 만일그값이현재최우수목적함수값보다더우수하다면 ( 작다면 ) 최우수목적함수값 는 로바뀌게되고그때의 를최우수변동데이터값인 로설정한다. Step 1부터 Step 3까지의탐색을완료하면기준데이터값을변경하고위의탐색과정을동일한방식으로반복해나간다. Step 4에서는기준데이터값 를최우수목적함수값을구할때의이웃해를생성한데이터값 로치환한다. 초기에설정한 만큼의기준데이터에대하여탐색이끝나면알고리즘은종료된다. 본논문에서는다루고있는문제에서스케쥴링결과에영향을끼치는데이터벡터들은납기, 가공시간, rework 확률그리고순서의존적인작업준비시간의 4개의 벡터로추정할수있다. 4장에서는각데이터벡터별로 PSBS를수행한다. 그리고휴리스틱 로사용된 EDDR과비교하여얼마만큼의성능향상을보이는지를평가하도록한다. 4. 결과분석 4.1 실험설계 본연구에서제시한알고리즘의효과를검증하기위하여동일한실험환경상태에서모의실험을실시하였다. 앞에서도언급했듯이 4가지문제구성요소인납기 (due date; D), 가공시간 (processing time; P), 재가공확률 (rework probability; RP) 그리고순서의존적인작업준비시간 (sequence dependent setup time; S) 에대하여 PSBS 를시행하였고실험결과들을이용하여알고리즘의성능과가장유의한문제요소가무엇인지에관하여분석하였다. 알고리즘의성능을비교하기위한척도로는 와 이사용된다. 실험에사용된데이터의생성기준은다음과같다. 가공시간과작업준비시간은 U[150,200] 의범위를갖는균일분포로부터생성하였고, 작업투입시점은 0으로부터평균최대완료기간 (Expected makespan : ) 의 배까지인 [0,R*T] 의범위를갖는균일분포로부터생성하였다. 여기서 는평균작업준비시간과평균가공시간의합을작업수 과곱한후기계수 으로나누어준값이며, 은작업투입시점의범위모수 (Release Time Range Parameter) 로서본실험에서는고정값으로 1.0이사용되었다. 납기는식 (6) 에의해생성되며, 수식에사용된 값은 [-1,4] 의범위를갖는균일분포로부터발생된다. (6) 본연구의핵심요소인 rework확률은 [ 표 2] 에정리된것처럼작업들의기계선호도에따라확률값을 B(Best), N.B(Not bad), P(Poor) 의세가지단계로나누었고각각 [0,0.001], [0.1, 0.2], [0.2, 0.3] 의범위를갖는균일분포로부터생성하였다. 본실험에서사용하는벤치마킹데이터는 [ 표 1] 과같이작업수와제품타입, 그리고변동될문제요소의조합으로생성된 320개의문제로구성되어있다. 단, 기계수는 3대로고정시켰다. 1707
한국산학기술학회논문지제 10 권제 7 호, 2009 [ 표 1] 실험계획 Values Total No. of Jobs 100, 500, 1000, 2000 4 No. of Job Types 5,10 2 No. of perturbed Factors D, P, RP, S 4 Combination 32 Problems per Combination 10 Total Problems 320 PSBS에서사용되는모수로는변동폭조절모수, 기준데이터수 와탐색횟수 가있는데초기실험을통해그값을각각 0.25, 5, 100으로고정하여사용하였다. 본연구에서제시한알고리즘은모두 C# 를이용하여구현하였고, 펜티엄4 2.4 GHz 컴퓨터에서실험하였다. 4.2 실험결과및분석 이장에서는 4.1에서언급한 320개의실험데이터를사용하여본논문이제시한 PSBS 알고리즘의성능을두가지목적함수인납기지연시간 (lateness time) 의최대값 ( ) 과재가공된작업의수 (Number of reworked jobs : ) 의최소화에대해서분석해보기로한다. 4.2.1 PSBS algorithm 성능분석 목적함수 : [ 표 3] 는 base heuristic인 EDDR과 4가지문제요소에 PSBS를적용한결과를보여주고있다. 표에서보듯이모든문제에서 4가지요인을변동시켜서 PSBS를적용한것이 EDDR보다좋은해값을주는것으로나타난다. 문제별로약간의차이가있지만대체적으로순서의존적인작업준비시간과재작업확률을변동시킨경우가나머지경우보다좋은해값을보여준다. [ 표 2] rework 확률 MC Type 1 2 3 4 5 6 7 A B P N.B N.B N.B N.B N.B B N.B B P N.B N.B N.B N.B C P N.B B N.B N.B N.B N.B D N.B N.B N.B B P N.B N.B E N.B N.B N.B P B N.B N.B F N.B N.B N.B N.B N.B B P G N.B N.B N.B N.B N.B P B H B N.B N.B N.B P N.B N.B I P N.B N.B N.B B N.B N.B J N.B B N.B N.B N.B P N.B [ 표 3] 에대한실험결과값 작업제품타입 EDDR 수수 D P R P S 100 5 4,815 3,115 2,706 3,003 2,533 (995) (472) (215) (419) (181) 10 6,220 4,551 4,633 5,423 3,917 (492) (465) (238) (627) (468) 500 5 14,295 12,754 10,309 9,069 8,197 (3,684) (615) (645) (604) (426) 10 32,041 22,633 22,026 22,842 14,501 (2,966) (1,606) (855) (1,569) (617) 1000 5 26,366 22,386 16,257 13,136 12,893 (6,576) (1,644) (1,427) (754) (553) 10 57,198 39,500 44,539 37,516 24,120 (5,566) (1,994) (1,956) (2,112) (1,645) 2000 5 43,902 40,443 32,330 25,758 22,829 (9,947) (5,498) (2,413) (1,864) (1,646) 10 114,335 79,799 79,973 70,733 41,599 (15,954) (4,426) (2,126) (6,041) (2,415) [ 표 4] 는 PSBS 알고리즘을사용했을때소요되는평균 CPU 시간 (Final CPU time) 과최고해까지도달하는데걸리는최고 CPU 시간 (Best CPU time) 을나타내고있다. 시간도마찬가지로순서의존적인작업준비시간과재작업확률을변동시켰을경우가나머지 2가지경우보다빠른시간안에전체수행을마쳤다. 이는순서의존적인작업준비시간이나재작업확률은작업수만큼의데이터가변동되는것이아니라제품타입수만큼이변동이되기때문에상대적으로변동되는양이작아져서시간이감소되는것으로추정된다. 목적함수 : [ 표 5, 6] 은각각목적함수가 인경우의목적함수값과 CPU 시간에관한결과를보여주고있다. 표에서보듯이목적함수가 일때도모든문제에서 일때와비슷한결과를보여준다. 문제별로약간의차이가있지만대체적으로순서의존적인작업준비시간과재작업확률을변동시킨경우가나머지경우보다좋은해값을보여준다. 5. 결론및추후연구 본연구에서는작업이속한제품타입과가공되는기계에따라 rework확률이달라지는병렬기계문제에서 와 의두가지목적함수를최소화하는 PSBS 알고리즘을제시하였다. 두목적함수에대하여 4가지요인별 1708
로각각실험을시행하였고, 그결과 PSBS 알고리즘이동일한문제에대해최근연구에서효율적 dispatching 알고리즘으로제시된 EDDR보다매우우수한해를산출한다는것을보였다. 또한문제요인별로는대부분의경우에순서의존적인작업준비시간과재작업확률을변동시켰을경우가좋은해를산출하였으며가장유의한요소로밝혀졌다. 추후연구로는 job shop과같은매우복잡한작업장에서실시간적으로효율적인 dispatching 규칙을선정해서사용해야될때, 본연구에서제시한 PSBS 알고리즘의문제데이터벡터분석방법을활용하는방안을적용하는것이있다. 또한다른메타휴리스틱탐색방법들과의비교실험을통하여 PSBS의성능을세밀하게분석하여성능개선가능여부를파악할필요가있다. [ 표 4] 에대한최고해도달시간과평균시간 Problem Best CPU time Final CPU time D P R P S D P R P S 100_5 2.6 3.0 1.1 2.9 5.2 5.4 5.2 5.4 (1.4) (1.7) (1.4) (1.5) (0.5) (0.3) (0.5) (0.4) 100_10 3.8 3.7 1.6 3.9 6.6 6.9 6.7 6.9 (2.1) (1.9) (1.6) (1.9) (0.6) (0.4) (0.6) (0.5) 500_5 14.7 12.1 40.8 31.1 63.8 78.3 59.5 68.6 (16.9) (17.3) (13.6) (18.8) (3.3) (4.3) (4.1) (4.5) 500_10 82.9 61.9 57.7 87.8 135.9 143.0 137.8 124.2 (33.4) (42.1) (48.3) (24.2) (5.7) (4.6) (4.5) (4.4) 1000_5 60.2 80.1 165.5 148.2 265.8 305.5 244.6 254.9 (69.8) (45.5) (38.6) (58.4) (10.5) (12.5) (11.7) (12.4) 218.9 242.7 301.3 288.8 507.4 591.2 475.2 433.2 1000_10 (207.2) (191.6) (119.5) (115.1) (14.5) (14.3) (12.6) (15.4) 2000_5 62.4 187.3 433.0 727.5 1059.1 1299.2 965.1 1020.8 (85.4) (160.1) (295.6) (193.7) (29.1) (112.3) (31.0) (69.9) 1070.0 1117.3 1025.8 1213.9 2219.3 2766.0 2163.1 1704.3 2000_10 (741.8) (685.3) (623.3) (483.7) (59.7) (322.7) (84.7) (63.0) 작업수 [ 표 5] 에대한실험결과값 제품타입수 EDDR D P R P S 100 5 16 8 7 9 6 (3) (3) (3) (3) (3) 10 18 9 7 12 8 (4) (4) (3) (4) (3) 500 5 59 42 44 34 39 (6) (4) (4) (4) (3) 10 82 60 59 54 50 (8) (4) (3) (7) (6) 1000 5 115 80 76 60 67 (14) (7) (7) (9) (7) 10 159 127 123 106 103 (17) (7) (7) (10) (7) 2000 5 211 158 158 107 132 (22) (11) (11) (12) (10) 10 319 265 263 227 208 (22) (13) (13) (21) (11) [ 표 6] 에대한최고해도달시간과평균시간 작업제품타 Best CPU time Final CPU time 수 입수 D P R P S D P R P S 100 5 1.2 1.2 0.8 2.6 5.2 5.4 5.2 5.3 (1.1) (1.4) (1.0) (1.8) (0.5) (0.3) (0.6) (0.3) 10 3.3 3.1 1.5 3.1 6.9 7.0 6.6 6.8 (2.3) (2.4) (1.6) (2.0) (0.6) (0.5) (0.6) (0.5) 500 5 15.9 22.9 35.0 41.3 63.4 78.8 57.2 71.1 (10.1) (24.9) (17.4) (26.0) (3.5) (4.7) (3.6) (3.0) 10 83.4 72.6 103.9 91.6 134.7 143.8 135.7 121.7 (33.2) (47.0) (36.1) (28.4) (6.6) (4.8) (5.9) (5.6) 1000 5 123.2 188.5 197.5 190.4 261.3 321.7 238.5 255.7 (93.6) (90.2) (37.3) (42.5) (10.3) (20.7) (9.8) (13.5) 10 142.3 323.9 307.3 232.3 510.1 601.1 468.2 444.3 (122.5) (215.2) (142.0) (145.0) (14.7) (31.3) (16.3) (30.5) 2000 5 649.5 539.1 714.2 729.8 1121.0 1253.7 915.5 964.0 (397.1) (413.4) (162.9) (148.1) (52.4) (31.0) (48.4) (42.7) 10 875.4 1414.6 1489.8 1080.9 2203.1 2740.9 2140.2 1780.8 (638.0) (770.5) (727.0) (343.9) (63.1) (150.0) (104.7) (93.9) 참고문헌 [1] 김여근, 윤복식, 이상복, [ 메타휴리스틱 ], 영진출판사, 1997. [2] Avic, S., M.S. Akturk and R.H. Storer, "A problem space algorithm for single machine weighted tardiness problems", IIE Transactions, Vol.35, pp.479-486, 2003. [3] Demirkov, E. and R. Uzsoy, "Decomposition methods for reentrant flow shops with sequence-dependent setup times", Journal of Scheduling, Vol.3, pp.155-177, 2000. [4] Flapper, S.D.P., J.C. Fransoo, R.A.C.M. Broekmeulen and K. Inderfurth, "Planning and control of rework in the process industries : review", Production Planning & Control, Vol.13, No.1, pp.26-34, 2002. [5] Kim, S.C. and P.M. Bobrowski, "Impact on sequence-dependent setup time on job shop scheduling performance", International Journal of Production Research, Vol.32, No.7, pp.1503-1520, 1994. [6] Kuhl, M.E. and G.R. Laubisch, "A simulation study of dispatching rules and rework strategies in semiconductor manufacturing", IEEE/SEMI Advanced Semiconductor Manufacturing Conference, 2004. [7] Leon,V.J. and B. Ramamoorthy, "strength and adaptability of problem space based neighborhoods 1709
한국산학기술학회논문지제 10 권제 7 호, 2009 for resource-constrained scheduling", Operations Research Spektrum, Vol.17, No.2, pp.173-182, 1995. [8] Leon, V.J. and B. Ramamoorthy, "An adaptable problem-space based search method for flexible flow line scheduling", IIE Transactions, Vol.29, pp.115-125, 1997. [9] Sha, D.Y., S.Y. Hsu, Z.H. Che and C.H. Chen, "A dispatching rule for photolithography scheduling with an online rework strategy.", Computers & Industrial Engineering, Vol.50, pp.233-247, 2006. [10] Storer, R.H., S.D. Wu and R. Vaccari, "New search spaces for sequencing problems with application to job shop scheduling", Management Science, Vol.38, No.10, pp.1495-1509, 1992. [11] Turkcan, A. and M.S. Akturk, "A problem space algorithm in multi-objective optimization", Journal of Intelligent Manufacturing, Vol.14, pp.363-378. [12] Uzsoy, R., C.Y. Lee and L.A. Martin-Vega, "A review of product planning and scheduling models in the semiconductor industry Part I : Systems characteristics, performance evaluation and production planning", IIE Transaction on Scheduling and Logistics, Vol.24, No.4, pp.47-61, 1992. [13] Uzsoy, R., C.Y. Lee and L.A. Martin-Vega, "A review of product planning and scheduling models in the semiconductor industry Part II : Shop-floor control", IIE Transaction on Scheduling and Logistics, Vol.26, No.5, pp.44-55, 1994. 이영섭 (Young Sup Lee) [ 정회원 ] 1987 년 2 월 : 고려대학교산업공학과 ( 공학사 ) 1989 년 2 월 : 한국과학기술원산업공학과 ( 공학석사 ) 2007 년 3 월 ~ 현재 : 상명대학교경영공학과박사과정 < 관심분야 > 생산관리, 공급사슬망관리, 스케줄링, 금융공학 신현준 (Hyun Joon Shin) [ 종신회원 ] 1995 년 2 월 : 고려대학교산업공학과 ( 공학사 ) 1997 년 2 월 : 고려대학교산업공학과 ( 공학석사 ) 2002 년 2 월 : 고려대학교산업공학과 ( 공학박사 ) 2002 년 5 월 ~ 2004 년 4 월 : 미국 Texas A&M 대학교산업공학과 Post-Doc 004 년 6 월 ~ 2005 년 2 월 : 삼성전자 LCD 총괄책임연구원 005 년 3 월 ~ 현재 : 상명대학교경영공학과조교수 강용하 (Yong Ha Kang) [ 정회원 ] < 관심분야 > 생산관리, 공급사슬망관리, 스케줄링, 금융공학 2001년 2월 : 고려대학교산업시스템정보공학과 ( 공학사 ) 2003년 2월 : 고려대학교산업시스템정보공학과 ( 공학석사 ) 2008년 2월 : 고려대학교산업시스템정보공학과 ( 공학박사 ) 2008년 5월 ~ 현재 : 미국노스캐롤라이나주립대학교산업공학과 Post-Doc < 관심분야 > 생산관리, 공급사슬망관리, 스케줄링 1710