Zero-Inventory Conditions For a Two-Part-Type Make-to-Stock Production System

We consider the dynamic scheduling of a two-part-type make-tostock production system using the model of Wein [12]. Exogenous demand for each part type is met from finished goods inventory; unmet demand is backordered. The control policy determines which pa

Zero-InventoryConditionsForaTwo-Part-TypeMake-to-Stock

ProductionSystem

MichaelH.Veatch FrancisdeV´ericourt

October9,2002

Abstract

Weconsiderthedynamicschedulingofatwo-part-typemake-to-stockproductionsystemusingthemodelofWein[12].Exogenousdemandforeachparttypeismetfrom nishedgoodsinventory;un-metdemandisbackordered.Thecontrolpolicydetermineswhichparttype,ifany,toproduceateachmoment;complete exibilityisassumed.Theobjectiveistominimizeaverageholdingandbackordercosts.Forexponentiallydistributedinterarrivalandproductiontimes,necessaryandsu cientconditionsarefoundforazero-inventorypol-icytobeoptimal.Thisresultindicatestheeconomicandproduc-tionconditionsunderwhichasimplemake-to-ordercontrolisoptimal.Weakerresultsaregivenforthecaseofgeneralproductiontimes.KeyWords:Make-to-StockQueue;HedgingPoints;Just-in-Time1Introduction

Safetystockservesavitalroleinbu eringagainstsupplyanddemandun-certaintyinproductionsystems.EveninaleanmanufacturingenvironmentDepartmentofMathematics,GordonCollege,Wenham,MA01984,veatch@gordon.edu FuquaSchoolofBusiness,DukeUniversity,Durham,NC27708,fdv1@duke.edu

1

We consider the dynamic scheduling of a two-part-type make-tostock production system using the model of Wein [12]. Exogenous demand for each part type is met from finished goods inventory; unmet demand is backordered. The control policy determines which pa

withshortcycletimes,amake-to-stockenvironmentmayberequiredtorapidlyandreliably llorders.Assumingthatbuildingstockinadvanceisfeasible,operationalandeconomicparametersdeterminewhetheritshouldbebuiltinadvanceorwhetheramake-to-orderpolicyispreferable.

Forasimplemodelwithoneproductionstage,asingleparttype,andbackorderingcoststhetradeo isknown:Zeroinventoryisoptimaliftheprobabilityofbackorderingademandislessthanacertaincostratio.Inmulti-part-typesystems,thedecisionismademorecomplexbythevarietyofsequencingcontrolsthatarepossible.Wegivenecessaryandsu cientconditionsontheparametersofatwopart-typesystemforazero-inventorypolicytobeoptimal.ThemodelweconsideristhatofWein[12].Asingleproductionfacilityproducesstockinordertosatisfyarrivingdemands.Fortractability,theproductionsystemismodeledbyanexponentialserverandthedemandsarriveaccordingtoindependentPoissonprocesses.However,partialresultsforgeneralproductiontimesarepresentedinthelastsection.Thismodelisthemake-to-stockversionofamulti-classqueue.Weconsideranymake-to-stockpolicy;i.e.,productioncapacitycanbedynam-icallyallocatedbetweenparttypes.Theobjectiveistominimizeaverageholdingandbackordercosts.

Thestructureoftheoptimalpolicyisonlypartiallyknownforthisprob-lem.Wein[12]providesinsightsintothestructureoftheoptimalpolicyusingaBrownianapproximationforthismulti-classmake-to-stockqueuingcontrolproblem.Ha[3]showsthattheoptimalpolicyisahedgingpointpolicyinthecaseofin nitehorizondiscountedcost.Ahedgingpointpolicyischaracterizedbyswitchingandidlingcurveswhichsplitthestatespaceinthreeregions:onewherethemachineisidleandthetwoothersthatdeter-minetheparttypetoproduce.Theintersectionofthesetwocurvesiscalledthehedgingpoint.Thehedgingpointandaswitchingcurvearesu cienttodescribethestationarybehaviorofthepolicy.deV´ericourtetal.[10]showthattheoptimalswitchingcurveisastraightlineinaparticularsubsetofthestatespace.Numericalstudiesindicatethattheremainderofthecurvehasnosimplestructure.HeuristicshavebeenproposedbyWein[12].VeatchandWein[9]andPe na-PerezandZipkin[4]proposee ectiveheuristicstoapproximatethiscurvealongwiththeoptimalhedgingpoint.

However,ifzeroinventory(produceonlywhendemandsarewaitinginthesystem)isoptimal,Ha[3]impliesthattheproductioncapacityisallocatedamongtheparttypesaccordingtoa“cµ”rule.Thiscompletelyspeci esthecontrolofthesystem.Inthispaper,wederivenecessaryandsu cientcon-

2

We consider the dynamic scheduling of a two-part-type make-tostock production system using the model of Wein [12]. Exogenous demand for each part type is met from finished goods inventory; unmet demand is backordered. The control policy determines which pa

ditionsunderwhichnoon-handinventoryisheld.Theseconditionsprovideafullcharacterizationoftheoptimalpolicyforsomespeci cvaluesoftheparameters.Theyareofpracticalinterest,fortheyindicatewhenthesystemshouldbecontrolledinasimplemake-to-ordermode.

Similarconditionsforzeroinventoryhavebeenderivedforthecontin-uous owcontrolproblem(BielekiandKumar[1],PerkinsandSrikant[5],Presmanetal.[6],VeatchandCaramanis[8],YeeandVeatch[13]).Inthismodel,the owofdiscretepartsisapproximatedbyacontinuous” uid”.Therandomnessinthesystemisonlyduetomachinefailures,whicharecapturedbyaMarkovprocess.InthispaperwepartlyfollowtheapproachofVeatchandCaramanis[8],evaluatingdi erentcoupledtrajectoriesgener-atedbypolicyperturbations.

Therestofthepaperisorganizedasfollows.ThedynamicschedulingproblemispresentedinSection2withtheoptimalityequations.InSection3,wedescribethegeneralstructureoftheoptimalpolicyandwede nethezero-inventorypolicy.NecessaryconditionsforzeroinventoryarederivedinSection4andshowntobesu cientinSection5.AnextensiontogeneralproductiontimeisdiscussedinSection6.Finally,theconditionsofSections4and5arestudiednumericallyinSection7.

2TheDynamicSchedulingProblem

Consideraproductionsystemwithasingle exiblemachinethatproducestwoparttypesinamake-to-stockmode.Weassumethatrawmaterialsarealwaysavailableinfrontofthemachine.Each nisheditemisplacedinitsrespectiveinventory.Whenademandarrivestothesystem,itissatis edwiththeon-handinventoryoftherequiredparttype,ifitisnotempty.Thedemandisbackorderedotherwise.TypeidemandarrivesaccordingtoanindependentPoissonprocesswithrateλi,i=1,2.Theproductiontimesoftheproductsareexponentiallydistributedwithratesµifori∈{1,2}.

Atanytime,acontrolpolicyspeci eswhethertoproduceparttype1or2,ortoidlethemachine.Theproductionofapartcanbeinterruptedandresumed,sothatapreemptivedisciplineispermitted.Sincethesystemismemoryless,forthecontrolofthesystemwecanconsideronlyMarkovpolicies,whichonlydependonthecurrentstate.

Wedenotebyx(t)=(x1(t),x2(t))thestateofthesystemwherexi(t)isthesurplus,(ornegativeofthebacklogifdemandsarebackordered)oftype

3

We consider the dynamic scheduling of a two-part-type make-tostock production system using the model of Wein [12]. Exogenous demand for each part type is met from finished goods inventory; unmet demand is backordered. The control policy determines which pa

i.WealsodenotebyX(t)=(X1(t),X2(t))theassociatedrandomvariable.LetCπbethecontrolassociatedwithaMarkovpolicyπ.

Cπ(x)=

0whentheactionistoidle1whentheactionistoproducetype1

2whentheactionistoproducetype2

Weconsideraunitholdingcosthiandanon-zerounitbackordercostbiperunitoftimefortypei.Intherestofthepaperwealsoassumewithoutlossofgeneralitythatµ1b1>µ2b2.Inthestatex,thesystemincursacost + +rateofc(x)=2i=1ci(xi)withci(xi)=hixi+bixi(wherexi=max(xi,0)andx+i= min(xi,0)).Theobjectiveisthento ndthepolicywhichminimizesthelongrunaveragecost

1π tlimsupEx0[c(X(t))dt].0t→∞t(1)

πwhereExdenotestheexpectationgiventhecontrolpolicyπandinitialstate0x0.

Theoptimalaveragecostrateg andtherelativevaluefunctionv(x)satisfythefollowingdynamicprogrammingoptimalityequations(seeVeatchandWein[9]):

1g =c(x)+λ1v(x e1)+λ2v(x e2)+µv(x)v(x)+ΛΛ

+min(0,µ1 1v(x),µ2 2v(x)),[](2)

wheree1istheunitvectoralongx1,e2istheunitvectoralongx2, iv(x)=v(x+ei) v(x),µ=max(µ1,µ2)andΛ=λ1+λ2+µ.

Wedenotebyλ=λ1+λ2,thetotalarrivalrate.ρi=λi/µiistheutilizationratefortypei,andρ=ρ1+ρ2isthetotalutilizationrate.Intherestofthepaper,weassumethatρislessthanone.

Anoptimalpolicysatisfying(2)existsifastablepolicyincurringa nitecostexists(seeforinstanceWeberandStidham[11]).Notethenthataprioritypolicywhichstatestoproduceifandonlyifademandiswaitingisequivalenttoamulti-classpriorityqueue.Sinceρ<1thissystemisstableandanoptimalpolicyexists.

4

We consider the dynamic scheduling of a two-part-type make-tostock production system using the model of Wein [12]. Exogenous demand for each part type is met from finished goods inventory; unmet demand is backordered. The control policy determines which pa

Figure1:GeneralStructureofanOptimalPolicy

3StructureoftheOptimalPolicy

Inthissectionwepresentsomepropertiesfortheoptimalpoliciesthatwillbeneededtoestablishzero-inventoryconditions.Theyarebasedontheconjecturethattheoptimalpolicyhasahedgingpointform.ThisformhasbeenshownbyHa[3]whenµ1=µ2,andhasbeenextensivelynumericallyveri edwhenµ1=µ2.

Ahedgingpointpolicyischaracterizedbyahedgingpointandaswitchingcurve(Figure1).Thehedgingpointz=(z1,z2)≥0determinestheon-handinventorylevelsfromwhichthemachinedoesnotproduce.Theswitchingcurvesplitsthestatespaceintworegions,accordingtowhichtypeisprefered.Moreprecisely,followingVeatchandWein[9],wedenotebyIthesetofstates¯ibethesetofstatesininwhichthecontrolpolicyidlesthemachine.LetB

5

We consider the dynamic scheduling of a two-part-type make-tostock production system using the model of Wein [12]. Exogenous demand for each part type is met from finished goods inventory; unmet demand is backordered. The control policy determines which pa

whichthepreferredparttypeforproductionispartiregardlessoftheidling¯i={x:minj=1,2µj jv(x)=µi iv(x)}.Thenahedgingpointdecision:B¯1={x:x1<sB(x2)}foranincreasingcurvesB(x2)policyissuchthatBwhere ∞≤sB(x2)≤∞andI={x:x1<sI(x2)}forsomedecreasingcurve,sI(x2),where0≤sI(x2)≤∞.Thehedgingpointzistheunique¯2includesthestatesonthestatesuchthatsB(z2)=sI(z2)=z1.Thus,BswitchingcurveandregionIincludestheidlingcurveandthehedgingpoint.Becausestateswithx1>z1orx1>z2aretransient,thestationarybehaviorofahedgingpointpolicyisentirelycharacterizedbyitshedgingpointandtheportionofitsswitchingcurvesB(x2)withx2≤z2.

WewillusethefollowingresulttocomparetheexpectationofW=X1/µ1+X2/µ2,theaggregatedworkloadofthesystem,fordi erentpolicies.Property1followsfromtheunderlyingnatureofhedgingpointpolicies;seeLemma2ofdeV´ericourtetal.[10].

Property1Considertwohedgingpointpoliciesπ1andπ2andtheirrespec-tivehedgingpointszπ1,zπ2.Then,

π1π1π2π2z1z2z1z2E[W] E[W]=+ µ1µ2µ1µ2π1π2

whereEπiisthethesteady-stateexpectationgiventhehedgingpointpolicyπi,i∈{1,2}.

Wewillalsousethefactthat,givenµ1b1>µ2b2,theoptimalswitchingcurveintheregionx2<0isaverticallinewhosepositionisexpressedbyasimpleequation(seeFigure1).ApplyingTheorem1ofdeV´ericourtandal.

[10],theoptimalhedgingpointpolicysatis es

C(x)=π 1

2mifx1<z1,x2<0

m,x2<0,ifx1≥z1

m=z1 µh1+b2µ2 1 ln() h1+b1 lnρ1(3)

and x denotesthegreatestintegerlessthanorequaltox.

6

We consider the dynamic scheduling of a two-part-type make-tostock production system using the model of Wein [12]. Exogenous demand for each part type is met from finished goods inventory; unmet demand is backordered. The control policy determines which pa

4Zero-inventoryConditions

Whenx2≥0,nogeneralequationfortheswitchingcurveisknown.Nev-ertheless,iftheoptimalhedgingpointisat0,theoptimalswitchingcurveisfullycharacterizedbythestraightlinex1=0.Thesystemistheninamake-to-ordermode.Wedenotebypolicyζ,thiszero-inventorypolicywhosehedgingpointisat0.Theassociatedcontrolisde nedby

0ifx=0

Cζ(x)= 1ifx1<0 2ifx1=0,x2<0 (4)

Wepresentfourconditionsthatmustholdforζtobeoptimal.

The rstconditioncomesfromthepartialcharacterizationoftheoptimal

mswitchingcurve.Ifpolicyζisoptimalthenz1mustbeequaltozero,and

weobtainfrom(3),

Condition1

h1µ1+b2µ2>(h1+b1)λ1

Toderivetheotherconditions,weevaluatethee ectofthreepolicyperturbationsdepictedinFigure2.Ifpolicyζisoptimal,theseperturbationsincreasetheaveragecost.

4.1RightShift

Weconsiderthepolicyπde nedbyarightshiftofpolicyζ.Thehedgingpointofpolicyπis(1,0)andtheswitchingcurveisthelinex1=1.Itisclear ]=Eζ[b2X2];theonlydi erenceinaveragecostisduetoX1.thatEπ[b2X2Thecontrolofthe rstparttypecorrespondstoahedgingpointpolicyinasinglepart-typesystem,wherethehedgingpointisoneforpolicyπandzeroforpolicyζ,soPπ(X1=x1)=Pζ(X1=x1+1)forx1≤0.Theincrementalaveragecostis

gπ gζ=h1Pπ(X1=1) b1Pπ(X1≤0)

=h1(1 ρ1) b1ρ1.(5)

Ifpolicyζisoptimal,then(5)mustbenonnegative,whichisthesecondcondition:

7

We consider the dynamic scheduling of a two-part-type make-tostock production system using the model of Wein [12]. Exogenous demand for each part type is met from finished goods inventory; unmet demand is backordered. The control policy determines which pa

Figure2:TheHedgingPointPerturbations

Condition2

ρ1≤h1

h1+b1

4.2UpShift

Herepolicyπisde nedbyashiftupofpolicyζ.Thehedgingpointofpolicyπis(0,1)andtheswitchingcurveisthelinex1=0.Forthisperturbationtheonlydi erenceinaveragecostisduetoX2.Letγ2=Pπ(X2=1).Then

gπ gζ=h2γ2 b2(1 γ2)(6)

π X2hasthesameprobabilitylawasthenumberoflowpriorityNow,z2customersinapriorityqueue.Hence,γ2isthestationaryprobabilityofno

8

We consider the dynamic scheduling of a two-part-type make-tostock production system using the model of Wein [12]. Exogenous demand for each part type is met from finished goods inventory; unmet demand is backordered. The control policy determines which pa

lowprioritycustomerinanM/M/1priorityqueue(withourparameters).Expression(36)forγ2isobtainedintheAppendix.Again,ifpolicyζisoptimal,then(6)isnonnegative:

Condition3

1 γ2≤h2

h2+b2

4.3RightExtension

Finally,weassumethatpolicyπisde nedbyarightextensionofpolicyζ.Thehedgingpointofpolicyπisstatee1andtheswitchingcurveisthestraightlinex1=0extendedbythesegment[0,e1].Theassociatedcontrolisthengivenby

0ifx=e1Cπ(x)=1ifx1<0 2if0≤x1≤1

Let

c (x1)=(h1+ orandx=0x2<0(7)µ2µ2b2)x++(b b2)x 111µ1µ1(8)

andrecallthatw=x1/µ1+x2/µ2.Then,forx2≤0,

c(x)=h1x+1+b1x1 b2x2µ2µ2µ2 =(h1+b2)x++(b b)x b2x1 b2x21211µ1µ1µ1

=c (x1) µ2b2w(9)

(10)

(11)andgπ gζ=Eπ[ c(X1)] Eζ[ c(X1)] µ2b2(Eπ[W] Eζ[W]).Eπ[W] Eζ[W]=1.µ1FromProperty1,

Now,weonlyneedthemarginaldistributionofX1underpoliciesπandζ.Observethat,underπ,theX1transitionintensitiesareindependentofX2exceptthosebetweenX1=0andX1=1.Thus,themarginaldistribution

9

We consider the dynamic scheduling of a two-part-type make-tostock production system using the model of Wein [12]. Exogenous demand for each part type is met from finished goods inventory; unmet demand is backordered. The control policy determines which pa

ofX1obeysthesamebalanceequationsunderπandζin{X1≤0}andtheprobabilitiesarethesameuptonormalization:

Pπ(X1=x1|X1≤0)=Pζ(X1=x1),x1≤0.(12)

Using(8)and(12),andtheexponentialassumptions,

µ2c(X1)] Eζ[ c(X1)]=(h1+b2)Pπ(X1=1)Eπ[ µ1µ2 ](Pπ(X1<1) 1)+(b1 b2)Eζ[X1µ1 2bρ1b1 µµ12Pπ(X1=1).(13)=h1 1 ρ1

Letγ2=Pπ(X1=1).Nextweshowthatγ2isequaltotheprobabilityofhavingnoclass1customerinapriorityqueuewherethehighpriorityisgiventoclass2.ConsiderXπ,atrajectorygeneratedbypolicyπ.Observethate1 Xπisthetrajectoryofaqueuewithclass2havinghighpriorityexceptthatclass1isserved rstinstateswherex1≤0andx2≤ 1.Aqueuethatgivesprioritytoclass2canbeconstructedbychangingtheorderofservicesothatclass2isserved rstinthesestates.Thisresequencingdoesnotchangethetimesatwhichthee1 Xπtrajectoryreaches0;hence,itdoesnotchangethetimesatwhichtheXπtrajectoryreachesandleavesstateswithx1=1.Onceagain,ifpolicyζisoptimalthen (10)ing(11),(13)and(37)intheAppendixforγ2,thelastconditionis

Condition4 2bρ1b1 µµ2 µ12h1 γ2 b2≥01 ρ1µ1

YeeandVeatch[13]suggestthatcondition3willbethesamefornparttypesbuttherewillbeadditionalcomplexconditionsintheplaceofCondition4.

5Su cientConditions

Intheprevioussection,wederivedfournecessaryzero-inventoryconditions.Here,weoutlineanargumentthatconditions3and4arealsosu cient.We rstshowthatconditions1and2areredundant:

10

We consider the dynamic scheduling of a two-part-type make-tostock production system using the model of Wein [12]. Exogenous demand for each part type is met from finished goods inventory; unmet demand is backordered. The control policy determines which pa

Property2Condition4 Condition2 Condition1

Proof:Thestationaryprobabilityofnolowprioritycustomerinapriorityqueueislessthantheprobabilityofthesameeventwhenthehighpriority classhasbeenwithdrawn.Inparticular,γ2≤1 ρbiningthisboundwithCondition4

h1 1ρ1b1µ21≥b2 1 ρ1µ1γ21 ρ1 ≥0

andCondition2isveri ed.Furthermore,Condition2canbewrittenh1µ1≥(h1+b1)λ1,whichimpliesCondition1.2

Supposeconditions3and4aresatis ed.FromProperty2,Condition1isalsosatis edandtheoptimalswitchingcurveisgivenbyx1=0,intheregionx2<0.Furthermore,Condition3and4implythatanuporrightextensionoftheswitchingcurveincreasestheaveragecost.FollowingVeatchandCaramanis[8],weconsidertheclassofpoliciesπusingtheoptimalswitchingcurvebutvarioushedgingpointsalongthiscurve.Itcanbeshownthatgπdecreasesmonotonicallyasthehedgingpointmovestowardtheoptimalhedgingpoint.Hence,Condition3and4implythatthezero-inventorypolicyisoptimalinthisclassofpolicies,andinfactoptimalamongallpolicies.6GeneralSymmetricProductionTimes

Untilnow,wehaveconsideredanexponentialproductiontime.However,someofthepreviousconditionscanbeextendedwhenanarbitrarydistri-butionisassumed.Weconsiderherethesamesystemasde nedinSection2exceptthattheproductiontimedoesnotdependontheparttypeandweonlyspecifyitsmean1/µ.Wealsoassumethatthetypeofapartischosenattheendofitsproduction.Inthiscase,theoptimalcontrolisnotMarkoviananymore,andcandependonthetime.Werestrictourstudytotheclassofhedgingpointpolicies(whichmaynotbeoptimal).

Property1stillholdsforthissystem.Toseethis,notethat,fori∈{1,2},πiπiz1+z2 X1 X2correspondstothenumberofcustomersinanM/G/1queue.

Ifwecomputeγ2forapriorityM/G/1queue,conditions2and3stillhold.However,Equation(12)ofSection4.3isnottrueingeneral,andthederivationofCondition4cannotbeextendeddirectly.Inthefollowingweproposetoderivethislastconditionusingcoupledtrajectories.

11

We consider the dynamic scheduling of a two-part-type make-tostock production system using the model of Wein [12]. Exogenous demand for each part type is met from finished goods inventory; unmet demand is backordered. The control policy determines which pa

WeconsidertwotrajectoriesXπandXζgeneratedbypolicyπofSection

4.3andpolicyζ.Thestartingpointsofthetrajectoriesaretheirrespectivehedgingpoints.Weconsiderthensequencesofrealizationsofthearrivaltime

11222oftype1and2demands,t11,t2,...,tk,...,andt1,t2,...,tk,...respectively,ppπandofrealizationsoftheproductiontimetp1,t2,...,tk,....WecoupleX

andXζbyassumingthattheyaregeneratedbythesecommonrealizationsoftheunderlyingrandomvariables.

Figure3:Di erentSegmentsoftheCoupledTrajectoriesfortheRightEx-tension

Thecoupledtrajectoriescanbedividedinto4segments(seeFigure3): Segment1:

ζπInthissegment,X1=0,Xπ Xζ=e1(sothatX1=1).Bothpolicies

ππ<0,andidlewhenX2=0.Asaresult,theproducetype2whenX2

12

We consider the dynamic scheduling of a two-part-type make-tostock production system using the model of Wein [12]. Exogenous demand for each part type is met from finished goods inventory; unmet demand is backordered. The control policy determines which pa

coupledtrajectoriesremaininthissegmentwhentype1demandsarriveorproductiontimesarecompleted.However,whenatype2demandarrivestothesystem,thecoupledtrajectoriesmoveintoSegment2. Segment2:

ζπInthissegment,X1<0,andXπ Xζ=e1.IfX1<0,thenboth

policiesproducetype1andthetrajectoriesstayinSegment2.IfππX1=0andX2=0bothpoliciesstillproducetype1,butwhenaproductiontimeiscomplete,thetrajectoriesmoveintoSegment1.IfζπππX1=0andX2<0,thenC1=1andC1=2,andwhenaproductiontimeiscompleted,thetrajectoriesmoveintoSegment3.

ζ Segment3:Inthissegment,X1=0,Xπ Xζ=e2(sothatwealso

πππhaveX1=0).Bothpoliciesproducetype2ifX2<0.IfX2=0,ζπ=1,andwhenaproductiontimeiscompleted,theC1=2andC1trajectoriesmoveintoSegment1,attheirhedgingpoints.Whena

type1demandarrivestothesystem,thecoupledtrajectoriesmoveintoSegment4.Otherwise,theystayinSegment3.

Segment4:

ζInthissegment,X1<0,Xπ Xζ=e2.Bothpoliciesstatetopro-

ducetype1,sothatbothtrajectoriesstayinSegment4untilaservicecompletionmakesthementerSegment3.

Fromthepreviousde nitionofthefoursegments,wehave

Xπ Xζ=

e1inSegment1and2e2inSegment3and4(14)(15)h1inSegment1

b1inSegment2c(Xπ) c(Xζ)= b2inSegment3and4

Ifwedenotebyp1,p2,p3andp4thestationaryprobabilitiesofbeinginSegment1,2,3and4respectively,weobtainfrom(15)

gπ gζ=h1p1 b1p2 b2(p3+p4).

Itremainsthentoderiveexpressionsforp1,p2,p3andp4.

13(16)

We consider the dynamic scheduling of a two-part-type make-tostock production system using the model of Wein [12]. Exogenous demand for each part type is met from finished goods inventory; unmet demand is backordered. The control policy determines which pa

First,itcanbeshownthatp1istheprobabilityofhavingnoclass1customerinapriorityqueuewherethehighpriorityisgiventoclass2(seeSection4.3).Itfollowsthat p1=γ2,(17)whereγ2isgivenby(37)oftheAppendix.

Furthermore,Segments1and3arethesegmentsoftrajectoryXζwhereζζ=0.Hencewehavep1+p3=P(X1=0)=1 ρ1andweobtainX1

p3=1 ρ1 γ2.

Wethenevaluatep2andp4usingthefollowingtwoequations

p1+p2+p3+p4=1p4p3=.p1p2(19)(20) (18)

The rstequationisstraightforward.Toshowthesecondone,wefollowVeatchandCaramanis[8].LetNi(t)bethenumberoftype1demandarrivalsin(0,t]occuringwhiletrajectoriesareinSegment1,2,3and4respectively.LetTi(t)bethetimein(0,t]ingaweaklawoflargenumbers,onecanshowthattheproportionN3(t)/N1(t)approachesT3(t)/T1(t)whent→∞withprobability1.Furthermore,eacharrivaloftype1demandmakesthetrajectoriesmovefromSegment1intoSegment2,orfromSegment3intoSegment4.ItfollowsthatT4(t)/T2(t)andN3(t)/N1(t)approachthesamelimitwhent→∞.SinceT3(t)/T1(t)andT4(t)/T2(t)alsoapproachp3/p1andp4/p2respectively,weobtainEquation(20).Itfollowsfrom(17),(18),(19)and(20)that

p2=

p4ρ1 γ21 ρ1ρ1 =ρ1 γ21 ρ1(21)(22)

Combining(17),(21),(18)and(22)with(16)wecanderivethedi erenceofaveragecosts

ρ1γ2 γ2 b2(1 ).gπ gζ=h1γ2 b11 ρ11 ρ1 (23)

14

We consider the dynamic scheduling of a two-part-type make-tostock production system using the model of Wein [12]. Exogenous demand for each part type is met from finished goods inventory; unmet demand is backordered. The control policy determines which pa

ThisleadstoadirectextensionofCondition4tothesymmetricalnon-exponentialcase.Hence,using(33)and(34)oftheAppendixtocomputeγ2 andγ2,Conditions2-4forthezero-inventorypolicytobeoptimal,become:

h1

h1+b1h21[ρλ λ1+(1 ρ)λ1σBP1(λ2)]≤λ2h2+b2ρ1b1 b21 ρ(h1 )[λ λ2σBP2(λ1)]≥b2λ11 ρ1ρ1≤(24)(25)(26)

withσBPi,theLaplacetransformofthehighprioritybusyperiodinaM/G/1queue,whereclassihasthehighpriority.FollowingtheproofofProperty2,onecanalsoshowthat(26)implies(24).

Asmentionedearlier,theoptimalpolicyisnotMarkovian,andsince(25)and(26)considerhedgingpointpolicyperturbations,theseconditionsarenotsu cient.Itmaybepossibletoprovethesu ciencyifwerestrictthestudytotheclassofhedgingpointpolicies.

7Numericalresultsandinsights

Inthissectionweexplorethezero-inventoryconditionsnumericallyanddrawsomeinsights.Ourresultssuggestadditionalconditionsunderwhichmake-to-order(MTO)isattractive.Forasinglepart-type,itiswellknownthatwhenutilizationisloworholdingcostsarelargerelativetobackordercosts,noinventoryshouldbeheld(Condition2).Condition3issimilar,butusescostsforthelowpriorityparttypeandreplacesthecombinedutilization(whichthelowprioritypartsees)withthesmaller1 γ2.Condition4capturestheinteractionbetweenparttypes.ToexaminewhenCondition4applies,we rstnotethatitholdsasymptoticallyash1/b2→∞.Evenforh1 ofcomparablesizetoh2,itmayholdif1 γ2issmall(suggestingthattheutilizationislow),andeitherthediscrepancybetweenparttypepriorities(b1µ1 b2µ2)issmallorthehighpriorityparttypehaslowutilization(ρ1

1).

Furtherinsightisgainedbyconsideringthecasewhereparttypesdi eronlyincost.Settingµ1=µ2,Condition4canbewritten

γ2≥ b2

h1+b1

15b1 b21 ρ1(27)

We consider the dynamic scheduling of a two-part-type make-tostock production system using the model of Wein [12]. Exogenous demand for each part type is met from finished goods inventory; unmet demand is backordered. The control policy determines which pa

Figure4:OptimalityoftheZero-InventoryPolicy

Typicallyρ1 1whentheseconditionsaremet,sowewillweaken(27)slightlybyreplacingρ1by0,giving

1 γ2≤ h1

h1+b2

(28)Alsosettingλ1=λ2,wehaveγ2=γ2.Thus,Condition4issimilarto

Condition3butcomparesparttypes:thehighpriorityholdingcostmustbelargerelativetothelowprioritybackordercost.

Speci cparametervalueswhereMTOisoptimalareshowninFigure4.Inthisexample,thetotalutilizationrateofthesystemisequalto0.4.Parttypesaresymmetricalindemandandproductionrates.Weseth2=1andb1/h1=b2/h2=b/handvaryb/handh1/h2.Increasingb/hmakesthesystemswitchesfromMTOtomake-to-stock(MTS).Whenparttypesaresimilar(h1/h2closeto1),thesystemswitchtoMTSonlywhenCondition

16

We consider the dynamic scheduling of a two-part-type make-tostock production system using the model of Wein [12]. Exogenous demand for each part type is met from finished goods inventory; unmet demand is backordered. The control policy determines which pa

4fails.Thisresultsinproducingsomestockinadvanceforparttypeonewhentherearenobacklogsinthesystem,whilemaintainingazero-inventorypolicyforparttype2.Ontheotherhand,whenh1/h2islargerthan4.1theswitchtoMTSoccurswhenCondition3fails,andresultsinbuildingasafetystockforparttype

two.

Figure5:OptimalityoftheZero-InventoryPolicyforDi erentUtilizationRates

Figure5presentssimilarresultsfordi erentvaluesoftheutilizationrate.Asρincreases,theregionwhereazero-inventorypolicyisoptimalgetssmaller.Themaximumvalueofh1/h2forwhichaswitchinproductionmoderesultsinholdingpartsoftypeone(thatis,whenCondition4fails)alsodecreases.Inotherwords,formake-to-ordersystemswithmoderatetohighutilizationincreasingb/hprecipitatesholdingsafetystockforthelessimportantparttypeintermsofbackordercost.

Inpractice,backordercostsareverydi culttomeasureanddemandmay

17

We consider the dynamic scheduling of a two-part-type make-tostock production system using the model of Wein [12]. Exogenous demand for each part type is met from finished goods inventory; unmet demand is backordered. The control policy determines which pa

bedi culttopredict.ItmaybehelpfultocheckConditions3and4forarangeofvaluesoftheseparameterstodetermineifaproductisinorneartheMTOregime.

8Conclusion

Wehavepresentednecessaryandsu cientconditionsforasimplemake-to-orderpolicytobeoptimalinatwoparttypeproductionsystem.Undertheseconditions,theoptimalcontrolpolicyisfullycharacterized.

Furtherresearchneedtobecarriedouttoaddressthecaseofmorethantwoparttypes.Anotherrelevantproblemforpracticalapplicationsistoknowwhenoneoftheparttypesismadetoorder,whilesomestockoftheothertypeisbuiltinadvance.Ournumericalstudyprovidessomeinitialinsightsintothisquestion.Conditionssimilartooursforthisproblemwouldhelpunderstandhowtochooseparttypesrequiringsafetystockswhentheproductioncapacityisshared.

18

We consider the dynamic scheduling of a two-part-type make-tostock production system using the model of Wein [12]. Exogenous demand for each part type is met from finished goods inventory; unmet demand is backordered. The control policy determines which pa

Appendix

AProbabilityofNoLowPriorityCustomerInthissection,wederivethestationaryprobabilityofhavingnolowprioritycustomersinapriorityM/G/1queuewithtwoclassesofcustomersandpreemptiveresume.Customersofclass1and2arriveaccordingtoPoissonprocesseswithparametersλ1andλ2,respectively.Class1hasthehighestpriority.Theservicetimeshavearbitrarydistributionswithmean1/µ1and1/µ2.Letγ2=P(X2=0),λ=λ1+λ2andρ=λ1/µ1+λ2/µ2.

FromCorollary1ofKeilsonandServi[7]thepgfofthenumberofclass2customersinthesystemis:

πS2(u)=

where

isthepgfofthenumberofclass2customersinthesystem

giventhatnoclass2customerisinservice

αT2istheLaplacetransformofT2,theservicetimeofclass2σBP1istheLaplacetransformoftheclass1busyperiod 2,thetimefromthebeginningofserviceofclass2istheLaplacetransformofTαT 2=αT2(s+λ1 λ1σBP1(s))untilthecustomerleavesthesystem,αT 2 2]=λ2E[Tρ 2 2]).(s)=(1 αT(λ2))/(sE[TαT 22πB2

Wewillusethefactthat

γ2(λ2)αT 2πB2(0).=πS2(0)=(1 ρ 2) 1 ρ 2αT(λ)2 2(30)(λ2 λ2u)(1 ρ 2)αT 2πB2(u), 1 ρ 2αT(λ λu)22 2(29)

ButfromKeilsonandServi[7],wealsohave,

πB2(0)=

ρ 21 ρ1[λ λ1σBP1(λ2)]λ2ρ2=.1 ρ1

19(31)(32)

We consider the dynamic scheduling of a two-part-type make-tostock production system using the model of Wein [12]. Exogenous demand for each part type is met from finished goods inventory; unmet demand is backordered. The control policy determines which pa

Assembling(30),(31)and(32),we nallyobtain

γ2=1 ρ[λ λ1σBP1(λ2)].λ2

(33)Foraqueuewhereclass2hasthehighpriority,theprobabilityγ2ofhaving

noclass1customerinthesystemcanthendirectlybeobtainedfrom(33):

γ2= 1 ρ[λ λ2σBP2(λ1)]λ1(34)

whereσBP2istheLaplacetransformoftheclass2busyperiod,whenclass2hasthehighpriority.

BCaseoftheM/M/1

Iftheservicetimeisexponentiallydistributed,wehavefromGrossandHarris

[2],2µ1 σBP1(s)=.(35)2λ1+µ1+s+(λ1+µ1+s) 4λ1µ1

From(33),(34)and(35),weobtainthefollowingexpressionsforγ2andγ2

γ2=

γ2= 1 ρ 2λ1µ1 λ λ2λ+µ1+(λ+µ1)2 4λ1µ11 ρ 2λ2µ2 . λ λ1λ+µ2+(λ+µ2)2 4λ2µ2 (36)(37)

References

[1]T.Bielecki,andP.RKumar,OptimalityofZero-inventoryPoliciesfor

UnreliableManufacturingSystems,OperationsResearch36(1988)532-546.

[2]D.GrossandC.M.Harris,FundamentalsofQueueingTheory,John

WileyandSons(1985).

[3]A.Ha,OptimalDynamicSchedulingPolicyforaMake-to-StockPro-

ductionSystem,OperationsResearch45(1997)42-53.

20

We consider the dynamic scheduling of a two-part-type make-tostock production system using the model of Wein [12]. Exogenous demand for each part type is met from finished goods inventory; unmet demand is backordered. The control policy determines which pa

[4]A.Pe na-PerezandP.Zipkin,DynamicSchedulingRulesForaMulti-

productMake-to-StockQueue,OperationsResearch45(1997)919-930.

[5]J.R.PerkinsandR.Srikant,HedgingPoliciesforFailure-ProneMan-

ufacturingSystems:OptimalityofJITPoliciesandBoundsonBu erLevels,IEEETransactionsonAutomaticControl(1998)953-958.

[6]E.Presman,S.P.Sethi,H.ZhangandQ.Zhang,OptimalityofZero-

InventoryPoliciesforanUnreliableManufacturingSystemProducingTwoPartTypes,DynamicsofContinuous,DiscreteandImpulsiveSys-tems4(1998)485-496.

[7]J.KeilsonandL.D.Servi,theDistributionalFormofLittle’sLawand

theFurhmann-CooperDecomposition,OperationsResearchLetters9(1990)239-247.

[8]M.H.VeatchandM.C.Caramanis,OptimalManufacturingFlowCon-

trollers:Zero-InventoryPoliciesandControlSwitchingSets”,IEEETransactionsonAutomaticControl44(1999)914-921.

[9]M.H.VeatchandL.M.Wein,SchedulingaMake-to-StockQueue:Index

PoliciesandHedgingPoints,OperationsResearch44(1996)634-647.

[10]F.deV´ericourt,F.Karaesmen,andY.Dallery,DynamicSchedulingina

Make-to-StockSystem:APartialCharacterizationofOptimalPolicies,OperationsResearch48(2000)811-819.

[11]R.R.WeberandS.Stidham,OptimalControlofServiceRatesinNet-

worksofQueues,AdvancesinAppliedProbability19(1987)202-218.

[12]L.M.Wein,DynamicSchedulingofaMulti-classMake-to-StockQueue,

OperationsResearch40(1992)724-735.

[13]M.J.YeeandM.H.Veatch,Just-in-TimePoliciesforManufacturing

FlowControllers,IEEETransactionsonAutomaticControl45(2000)336-339.

21

本文来源：https://www.bwwdw.com/article/6pi1.html