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