Sequencing CONWIP flow-shops: Analysis and heuristics

econstor www.econstor.eu Der Open-Access-Publikationsserver der ZBW – Leibniz-Informationszentrum Wirtschaft The Open Access Publication Server of the ZBW – Leibniz Information Centre for Economics Nutzungsbedingungen: Die ZBW räumt Ihnen als Nutzerin/Nutzer das unentgeltliche, räumlich unbeschränkte und zeitlich auf die Dauer des Schutzrechts beschränkte einfache Recht ein, das ausgewählte Werk im Rahmen der unter → http://www.econstor.eu/dspace/Nutzungsbedingungen nachzulesenden vollständigen Nutzungsbedingungen zu vervielfältigen, mit denen die Nutzerin/der Nutzer sich durch die erste Nutzung einverstanden erklärt. Terms of use: The ZBW grants you, the user, the non-exclusive right to use the selected work free of charge, territorially unrestricted and within the time limit of the term of the property rights according to the terms specified at → http://www.econstor.eu/dspace/Nutzungsbedingungen By the first use of the selected work the user agrees and declares to comply with these terms of use. zbw Leibniz-Informationszentrum Wirtschaft Leibniz Information Centre for Economics Framiúnan, Jose M.; Ruiz-Usano, Rafael; Leisten, Rainer Working Paper Sequencing CONWIP flow-shops: Analysis and heuristics Wirtschaftswissenschaftliche Diskussionspapiere // Ernst-Moritz-Arndt-Universität Greifswald, Rechtsund Staatswissenschaftliche Fakultät, No. 15/1998 Provided in cooperation with: Ernst-Moritz-Arndt-Universität Greifswald Suggested citation: Framiúnan, Jose M.; Ruiz-Usano, Rafael; Leisten, Rainer (1998) : Sequencing CONWIP flow-shops: Analysis and heuristics, Wirtschaftswissenschaftliche Diskussionspapiere // Ernst-Moritz-Arndt-Universität Greifswald, Rechtsund Staatswissenschaftliche Fakultät, No. 15/1998, http://hdl.handle.net/10419/48887 ~ app/eMsj!aJ6-!un-ZJ@UaIS!al l!eW-3 6Bvl9B-vCBC+6v + IUI xe;j 06vl9B-vCBC+6v + IUI lal ANV~~3D 'a1VMS;j13~D 6BvL~-a 'OL ,IS-Jaljj301-';j PleMSj!aJDjO AI!SJall!Un 'sSaU!Sn8 pue Me1 jO Alln:>e;j 'Iuawa6eue~ uo!pnpoJd ( NIVdS '3111"3S Z60~v U/S SOIUa!w!Jqn:>saa SOl ap Ou!we~ 'all!lIas jO AI!SJall!Un 'soJa!ua6UI ap Jo!Jadns elan:>S3 'sesaJdW3 ap uO!ISaD A le!JlsnpUI Uo!:>ez!ue6Jo ap Oluawe~edaa z sasnolnld@aso[ :/!eW-3 6lCLBvvS+vC + IUI :xe;j v~ZLBvvS+vC + IUI lal NIVdS '3111"3S l60 ~ V u/s SOIUa!w!Jqn:>saa SOl ap ou!we~ 'all!lIas jO AI!SJall!Un 'soJa!ua6UI I ap Jo!Jadns elan:>s3 'sesaJdW3 ap UO!ISaD A le!Jlsnpul uo!:>ez!ue6JO ap oluawe~edaa , -- 8661 j;}qW;}:>;}O ! 86/S I j;}d1!d uo!ssn:>s!o .N3.LSI31 'M3NNM .I zONVSn-ZIn'M 13V:WH ; ,NV~Ir'NH:i W 3S0f SJ!}S!JnJq PU8 S!SAI8UY ...j :SdOqS-MOU dIMNO:J ~u!JuJnbJS j .. "O!)II.I)S!"!WPV SS;lII!SII{) plIlI S;)!WOIIO;):!I "! s.I;ldlld IIO!SSII;)S!O f SS;lUISI18 pUl! Ml!l.1° f.1111:>1!~ ,i-: i j' PIII,\\SJ!J.I~ I.I!S,IJ,\!Ull-)PII.ly-:tI!.lOI-\i-ISII.l3 ~. ~.";.,,..; ..\ßSTI~AL'T In this paper. we address the backlog sequencing problem in a flow-shop conlrolled by a CON\VIP production conlrol system with the objective to mini mise the makespan We characlerise the problem and analyse its similarities and ditlerences with the permutation 110\\-shop problem A comparison of same well-known flow-shop heuristics is carried out. and a simple and fast dispatching rule is proposed Regarding the more simple and laster heuristics. the proposed dispatching rule outperforms those commonly used für the permutation flow-shop problem! Key\vords: Scheduling, Sequencing, Flow-Shop. Constant Work in Process (CONWIP). Heuristics, Dispatching Rules ZUSAMMENFASSUNG In diesem Arbeitspapier wird das Reihenfolgeproblem fur die Einsteuerung von Aufträgen in ein Fenigungssystem (backlog sequencing) bei Reihenfenigung (Flow-Shop) behandelt, wenn das System durch eine 'Konstanles Arbeitsvolumen in der Fenigung'-Steuerung (CONstanl Work In Process = CONWIP) gefuhn wird Als Zielfunktion wird die Minimie- ! rung der maximalen Durchlaufzeit (C...J angenommen Das Problem wird zunächst cha- ; rakterisien Seine Ähnlichkeiten und Unterschiede zum klassischen Reihenfolgeproblem bei Reihenfenigung mit konstanter Auftragsfolge auf allen Maschinen (Permutation-FlowShop) werden analysien Bekannte Heuristiken fur den Permutation-Flow-Shop werden auf den CONWIP-Flow-Shop übertragen und verglichen Eine einfache und schnelle Prioritätsregel wird vorgeschlagen Wird diese Regel mit einfachen und schnellen Heuristiken fur den Permutation-Flow-Shop verglichen. schneidet sie in Simulationsuntersuchungen besser als letztgenannle ab 1. Introduction The production control system CONWIP -acronym für CONstant Work In Process- (Spearman el '1/. 1989) is a pull system thaI appears to share the benefits of Kanban while being applicable in a wider range ofsituations The key poinl ofCONWIP is that it does not limit the single station's WIP or its butTer size, hut the total WIP in the system Several studies (eg Spearman el al. 1989, Lambrecht and Seagert ]990. Chang and Yih 1994, Gstettner and Kuhn 1996. and Bonvik "I al. 1997) indicate thaI in certain production scenarios. this conlrol system is prelerable to others 2 L- ,;,,;' ):::"1 c (S661 Ul?wJI?;ldS pUl? ddoH) sl:>npoJd IU;lJ;llIIP .10 ;lnUI?J J;)PIM I? ;)lpUl?4 UI?:> I! 11?41 S! ul?qul?'I J;)AO S;)nI?IUI?Apl? SI! jO ;)UO ;I:>U!S 'SIU;)WUOJ!AU;I d\,'I\NOJ \Ul?lU UI UOIII?n)!S uowwo:> I? ;lq 01 p;lsoddns S! ;lSI?:> II?J;lU;l3 SI41 11?41 P;lUO!IU;lW ;)q Pln04s 11 (0661 Iv /;1 Ul?wJI?;ldS) p;lSS;lJpPI? AII1!:>Y!:>;lds ;)q Isnw W;lISAS dIMNOJ I? U! 3U!\np;l4:>S jO w;llqoJd ;141 pUl? w;I\qoJd ;luI4:>I?W-;lUO I? 01 p;I:>np;lJ ;lq 10UUI?:> w;llqoJd 3U!:>u;lnb;ls ;141 ju;lpu;ld;lp-;l:>u;lnb;ls S! ;lU!4:>l?w 'I:>;lU;lllloq ;141 ;lJ;l4M ;lSI?:> II?J;lU;l3 ;141 U! 'J;lA;lMOH SISO:> dn-l;ls pUl? SU!PI04 snu!w P;lI:>;lI;lS 'IJOM ;l41jO ;lnll?,,\ ;141 S;)SIW!XI?W 11?41 4:>l?oJddl? 4:>JI?;lS ooql?ll? dO\;lA;lP A;l41 S;lW!1 dn-l;ls Iu;lpu;ld;lp ;I:>u;lnb;ls 41!M ;lUII dIMNOJ I? U! w;llqoJd 3U!:>u;lnb;ls ;141 p;lSS;lJpPI? (Z661) Ul?wJI?;ldS PUi jJlUpooM «(661 O:)!IU;ld PUi uo~oW 3;1 ;I;IS 'w;llqoJd Su!:>u;lnb;lS ;lU!4:>iW ;lISU!S UO M;I!A;lJ I? JOj) S;lSi:> ;ls;l41 JOj ;llqil!iAi ;lJi SW41!JOSli PUi (S661 UI?WJi;ldS PUi ddoH) ;lU!4:>l?w ;l1~U!S I? uo w;llqoJd ~u!:>u;lnb;ls ;141 01 p;I:>np;lJ ;lq Ui:> S;lSi:> ;lWOS U! SOI)(:>iq ;141 ~u!:>u;lnb;lS (9661 u4n)! PUi J;lUII;lISQ pUl? '1:661 Iv /;1 ddoH 'Z66\ S!UI?ZiZ PUi UiWJi;ldS 'Z66! Iv /;l13-JiQ 3;1 ';I;lS) p;I~od;lJ U;);lq ;lA1?4 suo!lnq!JIUOO liJ;lA;lS ';llnpow SÖM ;141 U! U;I'Iil SUO!SI:>;lP ;141 01 ~U!JJ;lj;l~ p;lsn ;lq 01 SpJI?:> jO J;lqwnu ;141 P;lU!UJJ;lI;lP SI?4 ;I\npow SÖM ;141 ;I:>UO P;l4S!lqiIS;I S! ~Ol'l:>iq ;)41 jO ;):>u;)nb;)s ;)41 J;)llil ;)41 UI ;)1!4M P;lXY ;)Ji -dIM wnWIXiW ;)41 'SI li41 -Iuno:> pJi:> ;)41 pUl? pou;ld uo!l:JnpoJd ;)41 JOj ilonb uo!l:>npoJd i 'sno!A;)Jd ;)41 uI ;llnpow (SU!4:>li8 PUi 5u!:Ju;lnb;)s) 8S ;)41 pUl? ;)Inpow (SU!II;)S ilonö PUi dIM) SÖM ;141 ;lJi 'IJOM;)WiJj S!41 U! P;)q!J:>S;)P s;llnpow :>Y!:>;lds-dIMNOJ OMI ;)41 .dIMNOJ JO.I 'IJOM;lWiJj ~U!UUild uo!l:>npoJd 11?:>14:>JiJ;)!4 i ;)sodoJd (0661) Iv /,1 UiWJi;ldS W;lISAS dIMNOJ 11 U! äu!lnp;lq:>s "' nol'l:>l?q ;)41 UI sqof3ul:>u;)nb;)s (q pUl! 'SpJI!:>jO J;lqlunu ;)41 nuIUIWJ;)I;)Q (I? sw;I\qoJd OMI jO SIS!SUO:> ;lJOj;lJ;)41 W;lISAS dlMNOJ I? ~UIUUl?ld ;)U4dl:>SIP (P;),\J;lS ISJI,j ;lWOJ ISJ!,j) S,jJ,j i Aq U;I/llJp 'SUOIII?IS ;)Alln:>;)Suo:> OMI U;I;lMI;)q P;l4sllql?ls;I .. ;)JI! sJ;I.unq ;)lilp;lWJ;)IU\ pJi:J 3UIPUods;)JJo:> I! In0411M ;)U4 ;)41 OIUI J;lIU;) 01 P;lMOIII! Gor R SI S;):>UI1ISUIIl:JJI:> ou J;)pUn fil)l~:Jl!lj ;)41UI )lUIIII?," Gor IX;)U ;)41 01 P;)4:>1!111! ;)q AI?UI U ;)J;)4M ';)UII ;)41,10 nuluuln;)q ;141 01 ~:>I!q P;)SI!;)I;lJ pUl! 110 p;lddoJp S! pJI?:> ;)41 'UOIII!IS leuy ;)41 IR P;)ss;I:Jo.ld SI qof I! U;)4M nol~:>eq I? UI IleM IsnUI qof ;)41 ';)SIMJ;)410 ;lUII ;)41 jO nUIUU!3;)q ;)41 JI! ;llql!lle.'\1! Sp.ll!:J ;)JI! ;)J;)41 P;)pl/loJd 'qor ;141 01 P;)4:>illl! S! pJI?:> I! ';)U4 dlMNOJ R 01 S;)'\IJ.II? J;)pJI) ljor e U;)4M SMo1lo,1 se P;lljIJ:>S;lP;)lj UI?:> 11 'AII1!:>lse8 (S661) Ul!llIJR;)dS PIII! ddoll \q P;)S!iIl:JSlp "1;)\1511:-1";) SI .lli'l\NO.) ,lI) lIlSIIIR4:J;llU II)JIIIO:> "'°[1 P;lI!I!I;)P "41 -~-~ ;,~'ßj,,~;Ii 011 Ihis general CONWIP sequencing problem, very litlle work has been reportcd I)lll:nyas (1994) sludies Ihe most suilable dispalching rules tor a CONWIP lilIe by USillg nel\\ork queues TarditT (1995) designs an MRP-C based Iramework tor sequencing in a C'ONWIP system Finally, Herer and Masin (1997) lormulate a mathematical programming version of the problem of sequencing the back log in a CONWIP system with the objeclive of minimising total costs In this paper we address the backlog sequencing problem in a CONWIP system in Ihe CONWIP framework described by Spearman I!f al (1990). sequencing is a slatic issue, sincc Ihe back log is generaled by an MPS (Master Production Schedule) taking imo accoum customers demand. so the composilion of the backlog is known at the beginning of Ihe production period It is supposed thaI the number of cards to be employed in the system has beeIl fixed within the previous WQS module. and thus there is no way to schedule the emrance of jobs into the system once the jobs are arranged in the backlog This means thaI a .job in the backlog will enter whenever there is a card available given it has been sequenced first in the queue in front ofthe system. In Ibis context, a plausible objective für sequencing the backlog seems to be minimising the makespan because: (I) Meaning ofthe backlog in a CONWIP system: thaI is, the set ofjobs thaI are going to be processed within the next production period Thus, unless a high priority is assigned to a specific job, the completion of all jobs is a major issue If different priorities are assigned to the jobs. a relevant objective could be minimisation of the weighted tlow time (2) According to Schonberger (1984) and Spearman I!f al. (1990), the production period für a pull system in general -and particularly für a CONWIP system -must be divided into a regular production time in which the production quota can be achieved and a catch-up time which provides a time-buffer to reach the production quota if, due to unforeseen circumstances (eg machine breakdowns or lack of raw materials), it cannot be accomplished within the regular production time Usually, the catch-up period is used für housekeeping, preventive maimenance, etc In this context, makespan minimisation has the effect of ensuring the production quota to be reached within the regular production time On the long run, it also provides a basis für a reduction ofthe regular production time and für shor1eninglead limes 4 : ~;;:;:":i!i '-' -, -~ -- S ;l1!U!JU! Sl1 p;lI;lJdJ;lIII! ;lq 148!w 4:J!4M SIUll1JISUO:> J;lJJnq OU ;I!) w;llqoJd fiu!:>II;lnb;ls p:!ull1JISuo:>un ;141 S;lSl1:> ;lW;lJIX;I aMI S114 w;llqOJd fiu!:Ju;lnb;ls d04S-MOU P;lU!l1JISUO:J J;lllnq ;14.1 ;lSl1JOIS J;I.unq P;lI!W!1 411M w;llqoJd \Ju!:>u;lnb;ls d04S-MOU I11J;lU;l11 ;lJOlll ;141 .10 ;lSl1:> 111!:J;lds 11 Sl1 p;lI;lJW;lIU! ;lq 14S!W OSll1 w;llqoJd fiu!:>u;Jnb;ls dIMNOJ ;J4.1 'SUO!1111nWJ;Jd 01 SUO!)nloS Jo ;J:>l1ds ;J41 S1:>!JIS;JJ W;J1sf.s ;J41 U! SJ;J.unq ;J111!p;JUJJ;JIU! ;J41 Jo ;JU!ld!:>s!p S:lJ:l :1' ;J41 ;J:>U!S 'p;JWWO ;Jq 14S!W UO!11110U ;J41 U! ;J1nq!J1111 IILu.Jd ;J41 11141 ;J10N n"".Jldt,-.IIIO.JI'":1 Sl1 p;JSU;JI:>l1J114:> ;Jq Ul1:> 3u!lnp;J4:>s d04s MOU dIMNOJ ;J41 '(6L61) }O 1;1 W11411J!) . Äq p;J:>npOJIU! SW;JlqoJd SUllnp;J4:>s JoJ UO!11110U ;J\dul pJl1pUl1lS ;J41 01 SU!pJOJ:>Y '(17961) uo)n;J.1 PUl1 )j;Jpna S;J ;J;JS 'suo!ldwnSSl1 ;JS;J4IJo IS!I ;J1;Jldwo:> 11 J°:l :>I;J 'S;JW!1 3U!ss;J:>oJd :>!IS!U!UJJ;JI;Jp 'SUO!1111S 1111 pUl! sqof 1111 Jo f.1!I!ql1\!11l\l1 SnO;JU111Inw!s :;JJml1J;J1!1 SU!lnp;Jq:>s :>!SSl1\:> ;J41 U! l11m!q114 ;JS041 ;Jpn\:>u! W;JlqoJd S!41 Jo uo!ll1lnwJoj ;J41 U! ;Jp1!W suo!1dwnSSl1 J;J410 UOlll1lS 4:>11;J U! qof 4:>11;J Jo S;JWII SU!ss;J:>oJd ;J41 41!M fiuoll1 :lN PUl1 LU '11 f.q p;Jq!J:>S;Jp ;Jq 1111:> lU;JlqOJd S!41 jO ;J:>Ul1ISU! UV ,W;JlqOJd 3u!:>u;Jnb;Js dIMNOJ, ;J41 SI41 ;JWl1U II!M ;JM 'fiU!MOIIOj ;J41 UI Ul1dS;J)jl1W ;J41 jO UOlll1S!W!U!W ;J41 S! ;J1\!1:>;Jfqo ;J4.L 'SpJ1!:> jO J;Jqwnu ;J41 01 l11nb;J SI I! PUl1 ,lN f.q U;JI\!S S! p;JMOlll1 dIM WnW!Xl1W ;J4.L UO!1111S f.q UO!1111S PUl1 qof f.q qof S;JWII fiulss;J:>oJd IU;JJ;JJJ!P ;J1\114 01 SMOlll1 sqof 11 jO p;Jsodwo:> S! 801)j:>l1q ;J4.1 SUO!ll1IS LU 41!M ;l1I!1 dIMNO:) 11 JOj SOI)j:>l1q ;J41 jO liu!:>u;Jnb;ls ;141 S! ;lJ;l4 p;lSS;lJppl1 w;llqoJd ;141 'f.lIl1WJ°:l '( (L6\ }O 1;1 Jl1)jll1MUl1d PUl1 '\ L6\ )j;Jpna pul1l1ldno '1i';J ;J;Js) f.IIUl1:>!J!US!S SISO:> liu!\np;J4:>5 ;J:>np;J,J 01 punoj U;J;Jq s114 UO!ll1S!W!U!W ul1ds;J)jl1W (17) II;JM Sl1 S;JI\!p;Jfqo IUl1!Jodwl ;Jq ,(l1W SS;JUlpJl1l P;J14fil;JM JO SS;JU!pJl1l.1° 1I01111S!W!UIW ;J41 U;J41 'p;JJ!nb;JJ S! qof 1- :J~II:>;lds 11 jO pUl1W;Jp ;J41 JO UO!I:>l1.1S!ll1S ;Jll1lp;JWW! ;J41 j! JO 'pUl1W;Jp J;JWOlsn:> lUOJJ I AI;Jll1lp;JWW! S1InS;JJ fiOI)j:>l1q ;J41 JI 'J;JI\;JMOH p;JJJn:>:>o f.Pl1;JJll1 ;J1\114 11141 SpUl1W;Jp .- 01 puods;JJJo:> SpJl1:> p;JSl1;J\;JJ ;J:>U!S 'P;J!lddl1 ;Jq 14S!W S;J111p ;Jnp jO UO!10U ;J41 M04 JI!:!p lau Sill l11q1 S;JI\J;Jsqo ('661) f.;JI)jJ;J8 'IX;JluO:> SI41 ul !.J01U;JI\UI spoofi P;J4SIU~1 ;1111 IlI0J.I P;lI\J;lS S! pUl1W;Jp SJ;JlUOISro ;J41 'W;Jlsf.s lind 11 \Jul;Jq d\MNOJ 'S;JPIS;J8 IIII!'\;)I;)J Sl1 1011 ;Jq IlIfillll S;J,'I!P;I!qo P;)III;lIJO ;)111P ;lnp '11;111.1 pou;ld lIoll:>npoJd ;1111 1111111'0\ P;J4S!ldulo:>:>11 ;Jq 14fillll sqof 1111 111111 l;JI\;l1 l:>npoJd I11U~1 11 UO f.1;J111WIXOJddl1 1~11:!1 111 'P;}'I:>;JII:> f.lsnO!I\;JJd 1I;);}q sl111 11 11141 SlIl1;Jlll SIII.1 pou;Jd uoll:>npoJd ;)111 ,(q p;JSOdllll S! nol)j:>l1q ;1111 111 sqof III! Jql ,11111PI1;JP 11 'SdW 1111 Äq p;JII1J;JII;J\J 1I;J4M (f) ..-, '.- ..~ illlermcdiale butrers) and the zero or no-wait sequencing problem In the two lalter Ihe iJllermediate butTers are zero, but the no-wait sequence problem is even more restriclive in the sense thaI the staning time of a job on the first machine has to be chosen such thaI the job does not have to wait für its processing on any machine The unconstrained sequencing problem has been studied extensively, and a good reference für zero and no-wait problems is pro\ided by Hall and Sriskandarajah (1996) Ht1we\'er, the intermediate case in which butrers are different from zero and not infinite - has been addressed by relatively few researchers für very specific purposes (Dutta and }Cunningham 1975, Reddi 1976, Papadimitriou and Kanellakis 1980, Leisten 1990, .' Logendran and Sriskandarajah J 993, and Sharadapriyadarshini and Rajendran 1997), despite it is considered the most realistic situation in many manufacturing environments (Wismer 1972, and Reddi and Ramamoonhy 1972) Besides, this type of problems is considered in principle (o be more difficult than the extreme cases (Mon on and Pentico 1993) With the exception of Dutta and Cunningham, who develop a dynamic programming procedure to generate optimal solutions with the objective of minimising the maximum completion limes for the two-station problem with limited butTers, the rest ofthe papers are mainly devoted to the development ofheuristics für the problems Maybe the most complete work in this direction is done by Leisten, who compares several heuristics für the m-station flow-shop sequencing problem with different intermediate buffer sizes The tested heuristics include buffer-constrained specific (including Dutta and Cunningham, Reddi, and Papadimitriou and Kanellakis and two new heuristics suggested in the paper) as weil as F .,LormuIC""" heuristics It turns out thaI the NEH heuristic (Nawaz ef GI. 1983), employed foT the unconstrained buffeT problem. performs weil according to the objective of minimising makespan. These results suggest thaI same well-known F..lvrmIIIC , heuristics may be suitable also für the CONWIP sequencing problem. which is connected to the buffer-constrained problem with respect to regarding .;;; buffer capacities within the system However, in contrast to fixed buffer sizes between each two machines, the CONWIP problem supposes a fixed number of jobs within the entire system being either processed on a machine or waiting for their next operation 3. The structure of the problem To obtain a first insight info the CONWIP-problem, the empirical distributions of all possible makespans obtained by complete enumeration of I 000 instantes of seven machines 6 'Ci, .i:"c '+"iCC,.,:;;j h --, '. L p;J1U;)lUWO:> A,Sno!I\;)Jd ;);)J41 ;)41 jO OMI U;);)MI;)q SUO!I!SUI!JI lu;)s;)Jd;)J 01 lU;);)S S;)I\Jro ;)41jO IS;)J ;)41 {wnw!ldo ;)41 ;Jl\oql! %1 ISOW II! ;)JI! SUl!ds;»)(l!w ;)41 Jo %vZO) UJ;)lll!d snoll\;)Jd ;)41 U! UI!41 uo!lnlos pooiJ I! pug 01 J;)!SI!;) S! I! pUl! ';)SI!:> d04S-MOU UO!ll!lnUJJ;)d ;)41 Aq U;)I\!~ S! UJ;)lll!d pJ!41 ;)41 'AIlI!UI:l ;)SI!:> J;)410 AUI! U! UI!41 J;)MO\ ;)JI! ;)\np;)4:>s pooä ~A!II!I;)J I! AIWOPUI!J Ull!lqo 01 S;):>uI!4:> pUl! lu!od IS~"I!U SI! S;)4:>I!;)J UO!lnq!JIS!P Ul!ds~)(l!w ;)41 ';)J;)H wnw!ldo ;)41 ;).\oql! %1 ISOW II! ;)JI! suo!lnlos ~41Jo %800 AluO Ilro~!P S;)wo:>;)q uo!lnlos wnw!ldo-JI!;)u I! äu!pug ;)SI!:> S!41 uI "{;)ldwl!x;) ;)4! U! ;)1\!!I!!u;)s;)Jd;)J ;)4! S! SpJI!:> JnoJ) SpJI!:> ,; Jo J;)qwnu ;)II!IP;)WJ;)!U! UI! JoJ P;)4:>I!;)J S! w;)!!l!d puo:>;)S ;)41 Ul!ds;»)(l!w !S;)q ;)4! ;)I\oql! %Z I UI!41 SS;)I !SOW !I! äu!;)q Jo A!!I!ql!qoJd SO I! SI!4 uo!!nlos WOPUI!J I! pUl! 'wnw!!do ;)41 . ;).\oql! % I !SOW !I! ;)JI! suo!!nlos ;)41 Jo % I ASI!;) J;)4!I!J S! uo!!n\os pooä I! äu!pu!:l Ul!ds;I)(l!w ;141 Jo uo!sJ;lds!p IlI!WS I! SM04s pUl! '- SpJI!:> OM! -!uno:> pJI!:> MOIAJ;lA I! JoJ P;lU!I!!qo S! ISJg ;141 S;lAJro Jo SUJ;I!!l!d ;I;IJ4! AIlI!:>!Sl!q ;lJI! ;lJ;l4! !1!4! U;I;lS ;lq UI!:> !! 'I ;lJnäg WOJ:l SpJI!:> Jo J;lqwnu ;lq! uo äu!pu;ld;lp '~U!!!;lS qof-u;lI\;lS ';lU!4:>I!W-U;lA;lS I! U! SUl!ds;I)(l!w ;)4!Jo suo!!nq!J!s!p JI!:>!J!dW3 1 ;I.ln~!.!I (oo~ = "Idol uedsa~ew al\!lelalj 06~ 09~ OL'~ 09~ 0 ~O'O I I I ZO'O ~ I ~ spJe:>g-dIMNO:)- I 1:0'0 ~ I :: spJe:> S -dIMNO:) ~ spJe:> V -dIMNO:)- I ~'O ~ I n spJe:>E-dIMNO:)- I '< spJe:> ldIMNO:)- --/ ~'O dO4S-MOII WJOO -\ I \..,1 9()'O r - ; I ; ;lW!! UO!ll!lndwo:> .- ;llqlluOSI!;lJ I! U!4!!M s!lns;lJ ;141 UllIlqo O! J;lpJO UI S! SI! u;ls04:> u;I;lq SI!4 sqof pUl! S;lU!4:>l!w jO J;lqwnu ;141 """.)VIIU./(fIr,1 01 11I:>!!U;lPI S! w;llqoJd ;141 SpJlI:> U;lI\;lS JoJ ;I\!4"" II!W!!do SI ;I:>u;lnb;ls 4:>11;1 'pJlI:> ;lUO JOj 11I41;110N U;lI\;lS 01 OMI WOJj fiUlfiulIJ Iuno:> pJI!:> I! JoJ p;lUll!lqo U;);lq ;I.\\!4 su\!ds;I)(\!w ;llq!ssod Il\! PU\! (66 PU\! ;lUO U;I;lMI;lq SJ;I~;lIUI) S;lWI! fiul~s;I:>oJd IUOPU\!J nulsn P;lI\!J;lU;ln u;I;lq S\!4 ;I:>U\!ISUI 4:>\!3 S;I:>U\!ISUI ;ls;l41 UIO.U P;lI\!IOd\!J1X;I ;Jq 14fil1ll suolsnpuo:> ;lI\II\!III\!l1b AluO 4nn04111! 'IU;llqOJd "".,)VII/I./(~w:1 ;141 PU\! IU;llqOJd-dIMNOJ ;141 U;J;)MI;)q S;):>U;Jj;),UIP PU\! S;lIIIJ\!I!UIIS 1\!;lI\;lj A\!llI SI41 P;lI\!lrol\!:> u;laq ;)I\\!4 sqof U;lI\;lS PUl! 'i'" ..~ patterll~ For instance, the CONWIP six cards curve nearly lits the Ilow-shop makespan di~t ribution However, from a practical out look it seems there should be a focus primarily onto the second pattern thaI is when the card count is neither very low nor close to the number of jobs The first problem is easy to salve and even a 'bad' sequence does not have as much impact on the system performance For the laffer case, we can use numerous techniques . , developed für the F;'!fJrmIIICmn., problem Besides of discussing the second pattern itselt: an 1 additional problem therefore arises from determining the borderline between the second li . pattern. ie the 'real' CONWIP-problem, and the third pattern, ie the ordinary permutation tlow shop case 150 1\ I -pefm ftow-shop \\ CONWIP -2 cards \CONWIP -3 cards ~ ,', ~ 100 f,' ' ---CONWIP-4cards E ~ " ; , ' -CONWIP.5cards '!! \...' '., ,'.:, -CONWIP.6cards 0 .' ':', ..'\ \ :', ~ I " E 50 ' \ ' ".' ", g \ : :' ", \ "'.. ; " I :, ;,'. " """ \..' , ., '. 0500 700 900 1100 1300 1500 makespan Figure 2: Empirical distributions ofthe optimal makespans In figure 2, the distributions of the optimal makespan für the I 000 problem instances are shown The distributions are almost symmetric While für six cards instances, the optimal values of the makespan coincide with those obtained für the permutation flow-shop, , the situation is different when the number of cards is lower A more exhaustive analysis by inspection of the vectors of the optimal job sequences confirms thaI these vectors, within this small numerical study, are identical für the six cards problem and für the flow-shop problem, and almost the same in most of the instances of the five cards problem as compared with the flow-shop problem However, the analysis reveals thaI, in general, the vl:ctor of the optimal solutions für two, three and four cards are different as compared with thosc obtained für the ordinary permutation flowshop case 8 ~I " s~ SI41 w:llqoJd fiu!:>u:lnb:ls dIM~O') :141 01 P;\PU:lIX:I :lq IOUU\!:I w:I\qoJd ""',)I"'I/.I(~'.:I :141 JO,I p:lsn AII"JsS:l:>:>ns s:>!ls!Jn:l4 u"ou'I-II:lM 1\!41 le:ll\:lJ Slu:lWIJ:ldx:I :141 jO sllns:lJ :141 suo!snpu°.:J .S (p:lI:J:lI:lS :lJe IU pue 11 U:I,'!1I \! JOj.lN Is:lMol :lljlljl!M s:I:JueISu! AIUO) s:J!ls!Jn:l4 :lljl JOj uO!1nlos 1s:lq :lljljO UO!le!l\:lp :lS1I1u:I:JJ:ld U\!:lW ~ :llqll.l 59t08l 19L05l t'JOOtl 081°LI 8LiLl 8t81l 6L51l :u"w '" 6Z81l 8(5LI LI_LI ZL9fl 98661 85('111 'J(IL91 OI/ollO( , L918t 896 fv ~O Zt (8t"f( (1985v L6,l~ 66116( OI/olml 9lllLl 11It"(l IMMrvl (5,91 (1I,8l ()()(,Il l06LI UI/OI/lI": IIS~6l 610"Ll 1955Z 9610l 099Ll ILSIII 19L81 Olmlml LIII~l 09tOl R_LLI lL~11 911ll 06L91 6S('ll ~1J/i)I/~1 Zl('61 ffil"Zl I-(,tLI ((/tL 09861 ~Ll(1 6t8H sO/Olm I aMIs oLdl "'ciS "JII"'.) ~-cll!t\NO') "Idn!) ~Iuled J.Nf\1Ij\1 S:I:JU1I1SU! dIMNOJ :lJnd 1S0W :lq1 U! 'S! 1eq1 'J:lMOI S! SpJe:J jO J:lqwnu :lq1 U:l4M :llqel!nS AIJlI(n:J!~lId S! :I(ru Su!q:J111ds!p (1IJ1U:!:J :lq1 ~eq1 s~s:I&'Sns SI41 S,J:lW(lId SU!pnl:JU! 'S:J!~S!Jn~4 J~ljIO ~ql SWJOjJ:ld1no sqO[ ~q~)O UO!1nq!J~S!P leJlu~:> :141 's:lse:J :IS~41 UI SUOllelS pue sqof jO J~qwnu U~I\Ijj' e JOj IS~MOi ~4~ S~ SpJ1I:> jO J~qwnu ;141 4:>!4M U! S~:JUlIISU! :lS041 01 nulpUOdS;1JJO:J UMOqS S! sw:llqoJd 09 jO l:lSqns e 'Ir :llqel U( SpJ1I:> jO J:lqwnu J~MOI 41!M sw:llqOJd :lS041 JOj s~Su1I4:> UO!~lIm!s S!q~ '~(ru Su!q:>llIds!p 11IJlu:I:> ;1ql ueq1 J~1~~q s:ll\eq:lq :JIIS!Jn:lq J:lW(lId :lql 'IleJ~I\O ~q~ uo qSnoqllV J:l11111 ~41 ueq1 J:lISlIj q:Jnw SU!:lq 'J~wled 01 f.IJe(!w!s pue '~-dIMNOJ ueljl J:lII:lq s~l\elj:!q 1\ ~(ru O~\S ~q~ PUlI (~JIU~J '1dl '1dS) S;lW!1 SU!ss:I:JOJd :lq1 uo p:lseq AI;I!OS s:llru 1Iu!Ij:J1eds!p JnOj ;lq1jO 1U:I!:J!lI~ ~sow :lq1 S! sqof S;lWII fiu!ss:I:JOJd J~q1l!q ;l1(ljO UO!lnq!J1S!P leJlu:I:J :lq1leql J1I;I(:J S! I! '( :llqe1 WOJ.,! SJ:lqlo :lql JOj ueql J:lq~!q f.llq~!IS :lJlI S:J!IS!Jn~q J;lw(ed 0'1 pue eldna f.q P:lp!I\OJd :lsoql 4nl1oql(1I ':llqlll:J;JI~:lU :lJlI S;J:>U;JJ~lJ!P ~:JUIS ;lJ:l4 p;l~od;JJ 1 10U ;lJe S;JW!I f1dJ le41 :lION f :llq\!1 U! UM04S :lJ\! IU:lWIJ;ldX:l S!ql jO SIII1S;lJ :141 - S:>IISIJI1:14 S,J:lWllId PUlI s,eldna 'V~ ~ 1 'W;JllJOJd 1Iul:>u:ll1b~s d04S-MOLJ ~41 JOj s:J!lslJn;\4 II'JIS\1.1 J41 JOj P:lU!\!lqo ;lS041 4111\' ~llnS:lJ :141 p:lJedwo:J osle;lM :llru (J~pJO wopue~ I11 J.1I,'IJ;\S) O~IS :141 Pli\! '~II1J (S;lIUlolo nuISS;\:JOJc/ Is~fiuOl) 1dl :141 ':I(ru (S;lWI1 1IuISS;I:JOJd 1~."l1J04S) 1dS :141 P;)I:I~I;)S ~1\\!4 ,"11\, UO~IJ\!dwo:J Jo.,! s~(nJ nU!4:JI\!dSlp UOIUWO:> J:lI(IO 1(11," nuOI\! SIU:lIQOJd .10 I:lS P;\l]IJ:>$Jp AI~11011\;lJd :11(1 Uo :Jlls!Jn~4 SI41 p:lIS:l1 :l1\\!1( :IM ::)" might bc seen as a contirmation thaI 1'..,VJrmlll( '..." and 1';'It.'/J/lwipl( '...:, are, in general, dillcrent problems, as it is derived from the results obtained in section 3 As lar as simple heuristics are concerned, CONWIP-RA heuristic, which is considered to ofter very good results with short computation limes in the I'~,v)rmlll( '..." problem, is clearly outperformed by the other heuristics For more elaborate heuristics, it appears thaI the behaviour of the NEH heuristic, which otTers the best results among the tested heuristics, is partly due to the numerous partial evaluations of sequences, and partly due to the fact that same problem instances are not WIP-constrained .. Finally. a simple dispatching rule is devised for the CONWIP sequencing problem This I rule has proven to be panicularly suitable for those instances with lower card count In -t these situations, the rule also clearly outperforms the more common fast heuristics used for the F;'VJrmIIIC""" problem The study presented here can be extended detinitely: As rar as the relation of n, m and NT as weil as the structure of the processing limes are concemed, the border li ne between simple flow shop behaviour of a problem or a problem instance respectively and the relevance of the CONWIP constraints can be explored Additionally, heuristics and dispatching rules exploiting the CONWIP problem structure in more detail might be developed We plan work on these aspects However, the study presented here gives a first insight into the structure ofthe sequencing problem ofCONWIP problem settings References Berkley, B. J., 1992, A review of the Kanban production control research literature Prcldllction and Operations Management, I, 393-411 Bonvik, A M, Couch, C, and Gershwin, S, B, 1997, A comparison of production-line control mechanisms /11/ernational Jolln/al (1 Prod/lction Research, 35, 789-804 Campbell, H G, Dudek, R A, and Smith, M, L, 1970, A heuristic algorithm for the n-job, m-machine sequencing problem Management oS'cience, 16, B630-B637 . Chang, T M, and Yih, Y" 1994, Generic kanban system for dynamic environment Intemalional.fo/lrnal 0/ Prod/lction Research, 32, 889-902 Dannenbring, D G" 1977, An evaluation of flow-shop sequence heuristics ManaXl!nlel/1 ~; St.'il!nt.'e,23,1174-1182 Dar-EI, E M, Herer, Y T, and Masin, M, 1992, CONWIP-based production lines with multiple bottlenecks performance and design implications Technical report, Israel Institute ofTechnology, Haifa, Israel, Duenyas, 1,1994, A simple release policy for networks ofqueues with controllable input O,Jeralic)/l,\" '~e,\"l!arch, 42, 1162-1171 Dudek, R A, and Teuton, 0 F, 1964, Development of m stage decision rule for scheduling n jobs through m machines (J,Jl!rat;c)/l,\" l?e\"l!arch, 12, (3) 16 -::' L~ LI' -91, 'u ',}>II,}!,J,\, /11,}/U,};J'/J//IJrv ;Jn\!JOIS ;J1\!!p;JIlIJ',}IU! 41!M nuIJu',}l1b~S '9L61 's S '!PP;J~I (II\!H ;JJIIU;lJd ~rN 's.lIllJ pooM',}lnu3) ,IIU,J/I,;{I Pi/V ,IIUIf/!,I/h'i/IJ ',{JIi,JIf/ :,il/!//lp,JIf,7,\, 'S661 '~ 'oP',}uld 6~~-ff~ 'L'l ',{JiJll!If,JIJrv ;J'11!/lldIIJ'},) ,/lJjllli!/V!,7/}I,;I'V ,JIf/ ji} //J//.I/lIi[ ;ln\!IS ,\J\!JOdUI',}1 P;lIIWII 41!M fiuIII1pa4JS d04S-MOI:l '0861 'd 'S!)j\!llaul!)t pUl! ':) '110IJIIWIP\!dl!d 8f-6Z dd ',!JO). MaN 'SUOIIl!Jllddl! SI! pUl! nUllnpa4JS jO AJOa41 uo wn!SOdWAS a41 uo sfiu!pa',}JOJd w',})qOJd fiu!)npa4JS II!IJISnpU! a41 pUl! 4JJI!asaJ fiu!Juanb',}s 'fL61 '. ~ '411WS pUl! 'y ~ ',!apno 's S 'J\!)j)I!MUl!d LOI-IOI '91 "{f.liJ/JVI/() 1f.7JViJ,I'iJ~//vllli!/v./iJdO wnw!ldo-Jl!au I! äu!u!l!}qo jO p041aw ,!J!nb I! aw!} 11!101 wnWIUIW a4} U! ssaJoJd a31!}S!llnW I! 43nOJ4} sqor 3u!Juanbas '~96\ 's 0 'JaW(l!d ~6-\6 'lI 'V[):J}'VO wa\qoJd 3U!Ju',}nb'.}s d04s-MOLJ qor -u 'auI4Jl!w-W a41 JOj w41!l°ä)1! J!ls!Jna4 Y 'f86\ 'I 'wI!H pUl! "3 3 'aJOJSU3 '~'J 'ZI!MI!N (a:>ua!JSJa}ul Aall!1I\ :).N) \"IUiJ/'\",\) ZU!/np"If:JS :J!/.\"!Jn"H '[661 "11\ '0 'OJ!}u',}d pUl! "3 ..1 'uo}Jo~ 9f6-~Z6 'Lr '1f,7JViJ.\"iJ"lj .\"uli!/vJiJdO aw!} apAJ az!w!u!W 01 ~ul,!JOlq 4}!M ',}ulI Alqw',}sSI! UI! U! ~ulJuanbas .6861 '8 'JIOII\ pUl! 's 'Ja)jua4S '. ~ 'Opau!d '.1 S .)jJ!WJo:)J~ I8~ -L9~ '69 'If:JJDiJSiJ"lj /vuo!/DJiJdO ja /VI/JI/O{ uviJdoJn.,? sdn-}as AJo}l!d!JI}ul! pUl! ~U!,!JO(q 411M w',}(qoJd 3u!(npa4Js dnOJ3 au!4JI!W-OM.1 '[661 ':) '4I!fI!Jl!pul!,!S!JS pUl! '~ 'ul!Jpua301 00 1 Z-~80Z '8'l 'If:JJDiJ.\.iJ"lj uo!/:JnpoJd Jo /DUJnO{ /VUO!/DUJiJ/U/ a~I!JOIS Jal}nq pal!w!( 4}!M swalqoJd ~u!Juanb'.}s d04S-MOI:l '066\ '~ 'uals!al I9-L~ '01 ,UiJ/UiJ;i'DUV}'V uo!/.7npoJd I/I} /DIIJI/O{ /DI/{}!/DUJiJ/U/ sau!l uOI}JnpoJdjo adA.1 A)qwassy pUl! (I!!Jas UI UOIII!JOIIV '!JO}S Jal}n8 '0661 'v '}Ja3I1aS pUl! W'!4JaJqw1!1 6L -I L 'S'l '\"UIJ!/:JDSUDJj:/I/ SW',}}SAS 3U!JmJl!jnul!w lind JOj SI!}onö uOIPnpOJd J!wouo:J3 '[661 " 'SI!AUano pUl! '. ~ 'ul!wll!',}dS 'r 11\ 'ddoH iU!MJI :YSn '03I!J!4:) s:J!S'{lfd ,VO/:JD:1 '~661 '. .W 'ul!wJlladS pUl! r 11\ 'ddoH ZOZ-~61 "lS 'If:JJDiJ.\'iJ~//D//{}!/DJiJdO Jo /D/lJnO{ uv"doJn:3 wa(qoJd d04S-MOLJ auI4:Jl!w-W 'qof-u ',}4} JOj J!}S!Jna4 Mau Y '\661 '. ). 'äul!!j:) pUl! :) r 'oH 9LO(-L901 'sr '1f,7.!DiJliJ~/ //I}!pn/JI}JJ ji} /PII.ml}[ /VI/{}!//J//.I,J/I// d~~ 01 sdl4Suo!ll!laJ pUl! sau!) UO!l:JnpoJd p',}S\!q ((JMNO:) jO UOlll1lnwJOj nUllUlUI!JnoJd 11!:Jlll!wa411!~ 'L661 '~ 'UISI!~ pUl! .1 A 'JaJaH SZ~-O 1 S '~~ '/{7JP,J.',}~/ '1/I}!/IJ./,Jd{) ssaJoJd UI III!M-OU pUl! nul)j:Jo(q 1111..1 SIII:1I(jwd fiIIIII1P:1I1:JS :1Il1I1JI?lIljO A:1"JllS V '9661 ':) 'lI\!r\!Jl1plll1)jSIJS PUI1 a N '111111 ~OZ-66( 'r 'SI/{}!/.7LX1/V.(/ .-mv fiu!lnp;J4JS dO4S-MOLl JO.lI!IJaIIJJ AI!(I!WlldO 'IL61 'V ~ ')japno pUl! '0 N r '1!ldn!) L~-6[ 'u 'f/J,J/.IVI/() 1f.7JV;JI'iJ~//DI/I}!/I}J,")d{) lualqoJd fiIlIII1P;l4:JS dO4SMOll a41 JOj 11I41!JOn)11 JIISIJI1;J4 Il!uOII:Jun.l V 'IL61 '0 N r .l!ldn!) fLZf-~-S,f '~r 'lf")JP,J.',")~/I/I}//,")!/pc}.',/li} /P/lJI/Ii[ /PI/I}!/PI/.I;J//I/ ,II,\\NO'> Pli\! 1I1!(j1l\!)j Slll;JISAS 1I0lPI1pOJd jO SISAII!IIV '9661 'H '1I411)t PU\! S .JaUllaIS!) 9Z[-L8Z 's ",7!//J/U;JIf/v}'V ;J/,JJ,7,'!(/ ji} l/pmlV A:1'1JI1S 11 nlllll1pa4:J~ PU\! nlllJII;ll1bas J!ISIUllIlJalap UI UO!II!WIXOJddl! pUl! 1I011l!SIlIlIIdO 'hL(, I ") 11 V "lm)l AO()IIIII~1 Pli\! ')I r '\!JlslIa1 '1 3 'JalM\!l '1 ~I "lIII1I(I1.1~) 966-686 'I 'l ';J}I/;J/7S 111;J//I;J,iPI/Vrv ;lnI!JOIS ;lII!IP;lIlIJ;l11I1 :11111~1 1(11'11 sdol(s-'IIOll ;l1I1I1:J11111-0'l11 nlll:JII;)l1h:1S 'SL61 .\1 "l1I\!l(nllllllll1,) PII\!.)I S .\!III1(1 ~."'f", I{.:ddi. S S. and I{amamoorthy. C V, 1972. On the flow-shop sequencing problem with no wail in process ()IJt!ratilJllal'~ex('ar('h <!'Iar/erl>', 23, 323-331 I{ccves, (' I{, 1995. A genetic algorithm for tlowshop sequencing ('vmIJllter' ()per(l/itlll(11 1<"""11"', 22, )-1 '; Schonberg.:r, I~ J, 1984, ~I/vrhl .Ia.'" m(l/IlljiIL'/llril"l,': /he le.\:'lIlIX llr ,impliL'I/) , appl;,'J (NY, Thc Free Press) Sharadapriyadarshini, B, and Rajendran, C. 1997, Scheduling in akanban controlted Ilowshop wilh dual blocking mechanism and missing operations for part-types Illtema/iV/lal ,!clllmal llf PrlJd/lc/io/l/~e.~em'ch, 35, 3133-3156 Spearman, M L, Hopp, W J. and Woodrufl: 0 L., 1990, A hierarchical control .. architecture for Constant Work-ln-Process (CONWIP) production system~, :JlI//mal llf ""al/1!fact//rillga/ldOperatio/l.~Ma/lageme/lt, 2,147-171 Spearman. M L., Woodruff. 0 L., and Hopp, W J, 1989, CONWIP a pult alternative to kanban fII/ema/io/lal Jollrnal 01 Prodllctio/l Research, 28, 879-894 Spearman. M L, and Zazanis, M A, 1992, rush and pult production syste~s issues and comparisons OperatiO/l.5 Research, 40, 521-532 Tailtard, E, 1990, Same efficient heuristic methods for the flow-shop sequencing problem l~lIrlllJt!a/l,!ll/lr/lall?f Operatio/lal Research, 47, 65-74 Tailtard, E, 1993, Benchmark for basic scheduling problems, El/ropea/l Jol/r/lal lI/ ()peratilmal Re.~earch, 64, 278-285 Tardiff, V, 1995, Detecting scheduling infeasibilities in multi-stage, finite capacity production environments, PhD Thesis, Northwestern University, USA Wismer, 0 A, 1972, Solution of the flow-shop sequencing problem with no intermediate queue ()peratiO/l.5 Research, 20, 689-697 WoodrutT, 0 L., and Spearman, M L., 1992, Sequencing and batching for two classes of jobs with due dates and set-up limes Jo//r/lal l?f Prodl/c/io/l a/ld Operativ/ls Ma/lageme/l/, 1, 87-102 Zegordi, S.H, Itoh, K, and Enkawa, T, 1995, Minimizing makespan for flow-shop scheduling by combining simulated annealing with sequencing knowledge E//ropea/l Jo/trllal llf Operatio/lal Research, 85, 515-531 (,: , '\1'5" ~:;;; I3IJf)9l ,~\i~1 /-: t ,:)1),,)\ \\:: 18 -'~{:ii.:;il~~ ':.'i Il.cddi, S S, and I~amamoorthy, C V, 1972, On the flow-shop sequencing problem with 1111 wail in process ()/lerOli(llloll?exeor(..h (j1(O/"lerf}', 23, 323-331 Il.ccves, C' I~, 1995, A genetic algorithm tor tlowshop sequencing ('(Inllllller, ()p,'mli(l/kll I(""'"r,"', 22, 5-11 Schonbergcr, I~ J, 1984, UI(lrl,/ L'I"" 1//001/(/LI("(llril,x Ihe 1",",'(111,' (Ir ,il//pli('II)" ,'ppli,',} (NY, The Free Press) Sharadapriyadarshini, B, and Rajendran, C, 1997, Scheduling in akanban controlled tlowshop \vith dual blocking mechanism and missing operations für part-\ypes /l11"/"IIOli(l/Iol ,IVIIrIIOI v( Pr(idIIClioll/?e,\"earch, 35, 3133-3156 Spearman. M L, Hopp, W J, and Woodrutl: D L., 1990, A hierarchical control -- architecture für Constant Work-ln-Process (CONWIP) production systems, .J(mmol v( Nlolll!(aClllrillg alld OperaliO/I.\" Mallagemelll, 2,147-171 ' Spearman, M L, Woodrutf, D L., and Hopp, W J, 1989, CONWIP a pull alternative to kanban IIIlenlaliol/al Jollrl/al 01 ProdllCliol/ Research, 28, 879-894 Spearman, M L., and Zazanis, M A, 1992, rush and pull production systelrls: issues and comparisons Operaliol/,\" Research, 40, 521-532 Taillard, E, 1990, Some efficient heuristic methods für the flow-shop sequencing problem 1;;,lr(I/iL'OI/ .!ollrl/al C?( Operaliol/al Re~'earch, 47, 65-74 Taillard, E, 1993, Benchmark für basic scheduling problems, E/lropeal/ Jo/lrl/al (if Operoliol/al Re,\"earch, 64, 278-285 Tarditf, V, 1995, Detecting scheduling infeasibilities in multi-stage, finite capacity production environments, PhD Thesis, Northwestern University, USA Wismer, D A, ] 972, Solution of the flow-shop sequencing problem with no intermediate queue ()peraliol/,~ Research, 20, 689-697 Woodrutf, D L., and Spearman, M L., 1992, Sequencing and batching für two classes of jobs with due dates and set-up times Jo/lmal 01 Prod/lcliol/ al/d Opera!iul/,~ Mallaxemel/l, 1,87-102 Zegordi, S.H, Itoh, K, and Enkawa, T, 1995, Minimizing makespan für flow-shop scheduling by combining simulated annealing with sequencing knowledge Ellropeal/ Jvllrllal o( Operaliol/al Re~'earch, 85, 5] 5-531 "::: ", ...t:iJ\" i ,\14," :JO:"{', ,. , ~~ .~\\~j "t '~)II..))\ \It 18 "nl!;)/I -IUSI;)Jd run ;)gU;)WPI;)D 'S;)PI;)D S;)P 1!;)JjgIPuIM4:>s;)gSjnI!IWO U;)4:>S!MZ SUI!4 -u;)wwl!snz U;)P jnl! U;)SJQqPI;)D J;)4:>SIUOJIJj;)I;) gnuuI3" :;)P40~ UIWJYfU;)SSUl!f ;)10 86/6 "U;)W4;)W;)IUO J;)P JnJJjruls -sguru;)!ZUI!U!~ ;)IP jnl! guru;)!UO!II!JI!P;)J)! J;)P gunJjJ!Msny ;)~a" :Jj:>oq4;)~ SI!!q°.L 86/8 "gU!11;)s-f.Jluno:) -OM.L I! U! 1;)l11!:) gU!XI~-f.I!IUl!nö I! uo S1!10nö 1JodWJ ;)41 uo" :;)Jj4:>SII!W I!!U;)X 861L "lJodS-wl!;).L U;)(I;)UOlss;)joJd W;)P snl! ;)punj;)g ;)4:>s!J!dw;) run u;)gung -;)IJ;)qo ;)4:>S!I;)JO;)4.L :gIOjJ;)SU;)W4;)UJ;)IUO run gU!(IOJIUO:)-(I!UOSJ;)d" :Jj:>!J~ PW;)g 86/9 "Zll!suy -pns-pJON U!3 :ljI!4:>SIJ!MII;)/\\ J;)P gunIJj:>!MIU3 ;)g!I(1!44:>I!N" :J;)g4:>S1;)Jg S1!:>~ 86/~ "U;)J4nq;)gU;)!PnJS U;)g;)g UO!11!1U;)WngJY ;)4:>S!wouoJjQ ;)U!3" :J;)gl!G J;)PUI!X;)IY 86/t "l;)gpng ;)41 pUl! 1q;)Q :>I(qnd uo ;)gUl!4:) :>!ljdI!Jgow;)Q jO s1:>;)jj3 uru-guO'] pUl! s:>!Wl!uf.G uru-lJoljS" :pUI!(sqJ3 P;)JjUI!W/4:>!J(O J;)Jj(°1\. 86/E ..gunlj;)!Z;)g-1U;)!1I!d-1ZJY ;)!P jnl! ;)!JO;)4.L -1U;)gy -(l!d!:>U!Jd J;)P gunpU;)Muy ;)U13 -U~1U;)l1l!d S;)P 1U;)gy s(1! 1ZJY J;)Q" :J;)P!;)ulj:>S °PO 86fl ; ..OOO'l Jlf1!f wnz ;)1(;)Mlj:>S J;)P UI! U;)S;)MSI!;)ljpuns;)D S1!a" :lj:>IJIO J;)Jj(°1\. 86/1 i ..S(;)Ul!d-YdIN S;)P ;)jl!H 1!W gun4:>nSJ;)1UO ;)U!3 1 U;)1~Jsq;)!J1~g UO/l u;)gunJjJ!MsgI!J1J3" :J;)g[!G J;)pUl!X;)(Y L6/t ..l!g!ls;)pung-[[l!q1;)JjS1!g (;)!ds!;)g S1!G :1JodSS1jl!lj:>SUUl!W U;)I(;)UO!ss;)joJd W! U;)UO!1JjunjSUO!1)[npoJd" :W(;)41!A\ ;)JjnI!J~ L6/E ..1(l!q -gn~ U;)1IljI!Z~ W! gunIJj:>!MIU;)J;)nl!lj:>snz run ..PI!Jgsgunuul!ds.. :1JodS-wl!;).L U;)II;)UOlss;)joJd W! ;)1Jj;)jj3 ;)UJ;)IX;) run Jj!1I!W;)lqOJdmg/l!1Jj;)(10)!" 'Jj:>!J~ PW;)g L6fl ..;)UUIM;)gsgunjdQlj:>sPI;)D ;)4:>1111!1!1S lj:>Jnp U;)SJQqp(;)D J;)lj:>S!UOJ1Jj;)I;) gunJ;)IUO!1U;)/lqns" :;)gul!'"] U;)1SJI!:)/U;)SSUl!f ;)10 L6/1 :u;Jua!qJS.I;J .I;JqS!H ;J.I;J!dcdsuo!ssn)fS!O aqJ!lJjcq;JSU;JSS!M51jcqJSJ.I!M J~Jln)fc~ Jq;J!luelJJSU;JSS!A\51ccJS pun -SJlI;JJ}) t PICMSj!a.lD }~J!~.laA!uf1-JPU.lV-ZJ!.l°W-JSU.l3 9,lItU:i:II}U. 10/98 Stefan Degenhardt: "The Social Costs of Climate Change -A Critical Examination" 11/98 Ulrich Hampicke: "Remunerating Conservation: The Faustmann-Hartmann Approach and its Limits" 12/98 Bretschger, Lucas: "Dynamik der realwirtschaftlichen Integration am Beispiel der t EU-Osterweiterung" 13/98' Burchert, Heiko: "Ökonomische Evaluation von Telematik-Anwendungen im Gesundheitswesen und Schlußfolgerungen für ihre Implementierung" .. 14/98 Dilger, Alexander: The Absent-Minded Prisoner i I I .~' . i i 1. t '."i; ii!5 'i~}::"(it,.;':; 'Cl: :,J',,!:: .~..,n.~!d,. : :>;jC!%-.tI1,('} ,,:01,:.'11') \c'~::;c"",~~"'~~il,,r,rn!..IrI: ,;