Improving Production Planning and Scheduling at AC

Informa Ltd Registered in England and Wales Registered Number: 10729 Registeredoffice: Mortimer House, 37-41 Mortimer Street, London W1T 3JH, UK

International Journal of ProductionResearch

Publication details, including instructions for authors andsubscription information:

http://www.tandfonline.com/loi/tprs20A gradient search and column

generation approach for the build–packplanning problem with approved

vendor matrices and stochastic demand

G. Sun , L.H. Lee , E.P. Chew & J. Shao

a

a

a

a

a

Department of Industrial and Systems Engineering , NationalUniversity of Singapore , Singapore, 119260Published online: 03 Sep 2009.

To cite this article: G. Sun , L.H. Lee , E.P. Chew & J. Shao (2010) A gradient search and columngeneration approach for the build–pack planning problem with approved vendor matricesand stochastic demand, International Journal of Production Research, 48:19, 5783-5807, DOI:10.1080/002070903049381To link to this article: http://dx.doi.org/10.1080/002070903049381PLEASE SCROLL DOWN FOR ARTICLE

Taylor & Francis makes every effort to ensure the accuracy of all the information (the“Content”) contained in the publications on our platform. However, Taylor & Francis,our agents, and our licensors make no representations or warranties whatsoever as tothe accuracy, completeness, or suitability for any purpose of the Content. Any opinionsand views expressed in this publication are the opinions and views of the authors,

and are not the views of or endorsed by Taylor & Francis. The accuracy of the Contentshould not be relied upon and should be independently verified with primary sourcesof information. Taylor and Francis shall not be liable for any losses, actions, claims,proceedings, demands, costs, expenses, damages, and other liabilities whatsoever orhowsoever caused arising directly or indirectly in connection with, in relation to or arisingout of the use of the Content.

This article may be used for research, teaching, and private study purposes. Anysubstantial or systematic reproduction, redistribution, reselling, loan, sub-licensing,

systematic supply, or distribution in any form to anyone is expressly forbidden. Terms &

Conditions of access and use can be found at http://www.tandfonline.com/page/terms-and-conditionsDownloaded by [Loughborough University] at 15:47 05 January 2015 InternationalJournalofProductionResearchVol.48,No.19,1October2010,5783–5807

RESEARCHARTICLE

Agradientsearchandcolumngenerationapproachforthebuild–packplanningproblemwithapprovedvendormatricesandstochasticdemand

G.Sun*,L.H.Lee,E.P.ChewandJ.Shao

DepartmentofIndustrialandSystemsEngineering,NationalUniversityofSingapore,

Singapore,119260

Downloaded by [Loughborough University] at 15:47 05 January 2015 (Received1August2008;finalversionreceived22February2009)

Westudyaproductionplanningproblemofproductassemblywithrandomdemand,wherethecustomerschoosetheirpreferredsuppliersforpairsofinter-dependentcomponentsthroughtheapprovedvendormatrix.Theproblemistodevelopproductionplansthatminimisetheexpectedtotalshortageandholdingcostswhileobservingthematrixrestrictionsandlimitedcomponentsupplies.Weprovideamathematicalprogrammingformulationoftheproblemwithalargenumberofdecisionvariables,whosecostfunctionisthesolutionofaparametricstochastictransportationproblem.Wepresentagradient-basedinterior-pointapproachtosolvethisproblemwherethegradientisestimatedbytheshadowpricefromthesolutionofsuchatransportationproblem.Acolumngenerationschemeisintegratedintotheapproachtohandlethelargeproblemissue.Computationalresultsshowthatouralgorithmsignificantlyimprovesthecomputationaltimewhencomparedwiththeapproachwithoutcolumngeneration.Inaddition,wealsodiscusssomeextensionsofthebasicproblemtothemulti-periodrollinghorizoncase.

Keywords:geneticalgorithms;inventorycontrol;simulationtheory;simulation;cycletimereduction;dispatchingrules;evolutionaryalgorithms;logistics

1.Introduction

Manufacturerstodaycompeteinathin-margin,commoditisedmarket.Ontheonehand,theyneedtorespondtocustomerdemandasquicklyaspossible,sousuallytheproductionplanneedstobemadewithoutfullknowledgeoffuturedemand.Ontheotherhand,theyoftenoffertheircustomersproductflexibilityoptionsasacompetitiveadvantage.Theseincentives,however,usuallyaddcomplicationstotheproductionplanningprocess.Inthispaperwestudyaclassofproductionplanningproblemsofemergingimportanceincurrentmanufacturingpractices.Theend-productofconcernisanassemblyofanumberofcomponentsandeachcomponentisusuallyprovidedbymultiplevendorsonalong-termcontractbasis.Themanufacturerthentests,assemblesandpackstheproductsforitscustomers.Tomaintaincompetitiveadvantage,themanufacturerlooksintoprovidingitscustomersproductflexibilitybygivingthemthefreedomtospecifytheirpreferredcomponentvendorsthroughanapprovedvendormatrix(AVM)(seeexampleinLeeetal.(2005a)).Thebuild-typeisdefinedfromthemanufacturer’spointofviewasthesetof

*Correspondingauthor.Email:sun.gang@gmail.com

ISSN0020–73print/ISSN1366–588Xonlineß2010Taylor&Francis

DOI:10.1080/002070903049381http://www.informaworld.com

5784G.Sunetal.

end-productsusingthesamecombinationofvendors,whiletheorder-typeisdefinedfromthecustomers’sideasthesetofend-productssatisfyingthecorrespondingAVMrequire-ment.Themappingrelationshipbetweenbuild-typesandorder-typesismany-to-many,thatis,oneorder-typemightbesatisfiedbyseveralbuild-types,andonebuild-typemightbeassignedtoseveralorder-types.

Theproblemscenarioisdescribedasfollows.Theplanningprocesscanbedividedintotwomainphases.Thefirstiscalledthebuild-planningphase,inwhichthetargetlevelforeachbuild-typetobebuiltisdetermined,subjecttotheconstraintsofcomponentsupplies.Thesecondphaseiscalledthepack-planningphase,inwhichbuild-typesaresimplyassignedasorder-typestomeetcustomerdemand,observingtheAVMrequirements.Duetothevolatilityofthemarket,thefirstphasemustbedonebeforefullknowledgeofthecustomerdemands.Oncethebuildplanisissued,themanufacturerstartstoassembletheproductsaccordingtothebuildplan.Althoughthecustomerdemandsareunknowninthefirstphase,weassumethedistributionsareavailableeitherfromestimationorprediction.Whencustomerdemandsarerealised,themanufacturerthenpacksthebuild-typesintoorder-types(secondphase).Thetotalcostofinterestcontainstheshortagecostforunfulfilleddemandsandtheholdingcostforexcessproduction.Thesecondphasecanbemodeledasatransportationproblem,whichdetermineshowtoassignbuild-typesasorder-typeswithminimalcost.Theoptimisationofthefirstphasecanbemodeledasabuild–packplanningproblem,thatis,giventhedistributionsofthefuturecustomerdemands,determinethetargetlevelsforallbuild-typessoastominimisethetotalcostonexpectation,subjecttocomponentavailability.Ourmainconcernintherestofthispaperfocusesonsolvingthebuild–packplanningproblem.

Thekeycharacteristicsofourbuild–packproblemarethehighproliferationofbuild-typesandthecomplexityofproductionplanningimposedbyAVMs.Theproduction-planningliteratureaddressingtheimpactofapprovedvendormatricesisratherlimited.Muchoftheearlyworkisfocusedonthemodelingandsolutionofhierarchicalplanningandschedulingproblems.Sincethesetofcustomerdemandsservedbyeachbuild-typeoverlapseachother,ahierarchicalproductionplanning(HPP)approach(HaxandMeal1975,Graves1982)doesnotapply.Chu(1995)consideredthecasewherecustomerscanspecifytheirpreferredsuppliersforindividualcomponents,butdoesnotexplicitlyaddresstheproblemofhighbuild-typeproliferation.Leeetal.(2005a)firstintroducedthedeterministicversionofthemulti-periodbuild–packproblemforshort-termproductionplanningwithamoregeneralformoftheapproved-vendorlist,i.e.theAVM.Theyformulatedtheproblemasatotaltardinessproblem(Wang1995),andthecolumngenerationtechnique(GilmoreandGomory1961,NemhauserandWidhelm1971)isthenusedtosolvethelinearmodelforanoptimalbuildandpackschedule.Further,Leeetal.(2005b)thenshowedthatthisbuild–packproblemhasanequivalentmulti-commoditynetworkflowrepresentation,andasolutionprocedureusingmulti-stagebenderdecompositionwasthendeveloped.

Todealwiththeuncertaintyofcustomerdemands,ageneralapproachcommonlyusedformodelingstochasticplanningproblemsisthescenario-basedstochasticlinear-programming(SLP).ApplicationsofSLPinproductionplanningincludestochasticproductmixplanning(Dantzig1963,RockafellaandWets1985),stochasticHPP(Kiraetal.1997),delayedproductdifferentiation(SwaminathanandTayur1998),multi-periodproductionplanning(Petersetal.1977)andmanpowerplanning(KaoandQueyranne1986).InSLP,futureuncertaintyismodeledasafinitesetofpossibleoutcomesorscenarios,eachwithanassociatedprobabilityofoccurrence.Theobjectiveistominimise

Downloaded by [Loughborough University] at 15:47 05 January 2015 InternationalJournalofProductionResearch5785

Downloaded by [Loughborough University] at 15:47 05 January 2015 thetotalcostsofproductiononexpectationoverallthepossibleoutcomes.Inthismannertheproblemcanbeformulatedasalarge-scalelinearprogramordeterministicequivalentprogram(Wets1974),andsolutionapproachessuchastheL-shapedmethod(SlykeandWets1969)havebeendevelopedtosolvesuchformulations.Suchanapproach,however,isknowntobecomputationallyefficientonlywhenthenumberofpossibleoutcomes(thesamplespace)isoflimitedsize.Therefore,theapplicationoftheSLPmodelingapproachpresentsanadditionaldifficultyinourcaseduetothehighbuild-typeproliferationinourproblem.Ontheotherhand,worksuchasthatofMetters(1997),whichconsidersproductionplanningwithstochasticseasonaldemand,andthatofHodgesandMoore(1970),whichconsidersstochasticproduct-mixplanning,usesthenews-vendormodelinclassicalinventorytheoryasthebasicapproachforconsideringstochasticdemand.Alongthisline,Ngetal.(2006)developedarealisticmedium-termplanningmodelwhichaccountsforbothAVMsandstochasticcustomerdemand.Theyprovidedamixed-integerformulationoftheproblem,whoselinearapproximationandrelaxationissolvedusingthecolumngenerationmethod,andabranch-and-priceframeworkisthensetuptogeneratefeasiblesolutionstotheproblem.

Inthispaperweproposeaninterior-pointapproachwhichsolvesthebuild–packplanningproblemusingagradientsearchmethod.Theproblemisformulatedasanonlinearprogrammingproblemwhoseobjectivefunction,whichhasnoexplicitform,ismodeledasaparametricstochastictransportationproblem.Thegradientofinterestisestimatedfromaveragingthesolutionsofanumberofsuchtransportationproblemswithrandomlygenerateddemands.Thecolumngenerationtechniqueisappliedtohandlethelargeproblemsize.Thewholeproblem-solvingprocedurecontainstwonestedloopswheretheouteroneisthecolumngenerationloopandtheinneroneisthegradientsearchloop.Moreover,weextendourapproachfromthesingle-periodcasetothemulti-periodrollinghorizoncase.

Therestofthepaperisorganisedasfollows.InSection2weformulatethebuild–packplanningproblemasanestednonlinearprogrammingproblem.InSection3wefirstdevelopagradientsearchsolutionforafixedsizedproblem,andthenshowhowthecolumngenerationtechniquecanbeappliedtoit.Nextwesummarisethealgorithmsandpresentsomenumericalresults.InSection4wedemonstratetheextensionofourapproachtothemulti-periodrollinghorizoncase.Section5concludes.2.Problemformulation

2.1Notation

Wedefinethefollowingparametersforthesingle-periodbuild–packplanningproblem.

KÂPk󰀂pVpVkpvpmvpsetofallorder-typessetofallbuild-typessetofallcomponentsindexoforder-typeindexofbuild-type

indexofproductcomponent

setofallvendorsofcomponentp

setofallvendorsofpthatisacceptableintheAVMoforder-typekindexofcomponentvendorforcomponentpsupplyfromcomponentvendorvp5786G.Sunetal.

dku󰀂gkh󰀂demandfororder-typekbuildlevelforbuild-type󰀂

costofperunitofdemandunfulfilledfororder-typekcostofperunitofproductsoverproducedforbuild-type󰀂

2.2Masterproblemformulation

Nowweformulatethemasterproblemwhosedecisionvariablesarethetargetproductionlevelsofthebuild-types,u󰀂,󰀂2Â.ProblemMP:

Downloaded by [Loughborough University] at 15:47 05 January 2015 minimiseFðuÞ,

subjectto

GvpðuÞ¼mvpÀ

ÂX󰀂¼1

ð1Þ

󰀃󰀂pu󰀂!0,8󰀂2Â,

v

8vp2Vp,8p2P,ð2Þð3Þ

G󰀂ðuÞ¼u󰀂!0,

where

v

󰀃󰀂p¼

8

><1,>:0,

ifbuild-type󰀂isbuiltusingvendorvpforcomponentp,

vp2Vp,p2P,otherwise.

ThecostfunctionF(u)representstheexpectedcostassociatedwiththeprocessofpackingbuild-typesasorder-types.Equations(2)arecomponentavailabilityconstraintsand(3)excludesthepossibilityofnegativebuild-typelevels.Fornotationalconvenience,wecombineGvp(u)andG󰀂(u)togetherandre-indexasGl(u),l¼1,...,L,whereListhetotalnumberofconstraints.Observefrom(2)and(3)thatallconstraintsarenotonlyconvexbutalsolinear,sothefeasibleregionisinfactapolyhedra.

NextwediscusshowtoevaluatetheexpectedcostF(u)whenthebuildplanuisgiven.ThedifficultyisthatthereisnoclosedformforF(u).HenceweproposetogeneraterandomsamplesofcustomerdemandsbasedonthegivendemanddistributiontoestimateF(u).Oncethecustomerdemandd(!)isrealised,howtosatisfythecustomerdemandscanbemodeledasatransportationproblemwhichwillbediscussedlaterinSection2.3.Denotef(u,d(!))theoptimalcostofthetransportationproblem,soF(u)istheexpectationoff(u,d(!))overallpossible!,thatis

FðuÞ¼E!½fðu,dð!ÞÞ󰀄:

ð4Þ

SupposewehaverunatotalofNdemandrealisations,!1,!2,...,!N,thenanestimateofF(u)isgivenby

N1X

FNðuÞ¼fðu,dð!nÞÞ:

Nn¼1

ð5Þ

InternationalJournalofProductionResearch5787

Ifthedemandrealisationsareindependentofeachotherandyieldani.i.d.sequence{f(u,d(!1)),...,f(u,d(!N))},then,bythestronglawoflargenumbers,wehave

\"#

NX1

FðuÞ¼limfðu,dð!nÞÞ¼limFNðuÞ:ð6Þ

N!1NN!1

n¼1AlthoughEquation(6)statesthat,whenNgoestoinfinity,thesampleaveragewillbethetrueexpectedvalue,inpracticewewillchooseafiniteNsuchthattheconfidenceintervaloftheestimateissmall.

2.3Transportationproblemformulation

Downloaded by [Loughborough University] at 15:47 05 January 2015 AsmentionedinSection2.2,oncetheproductionplanuandcustomerdemandd(!)areknown,theprocessofassigningbuild-typestocustomerorderscanbemodeledasatransportationproblemwhichisadeterministicproblemdefinedastransportinggoodsfromsupplyingnodes(build-types)todestinationnodes(order-types)atminimalcost(penaltycostofunfulfilleddemandplusholdingcostofoverproducedbuild-types).Thelinksconnectingbuild-typenodesandorder-typenodesareassociatedwithaunitcostofeither0orMaccordingtotheAVMsoftheorder-types.Whenapairofbuild-typeandorder-typeiscompliantwiththeAVM,thenthecostis0,otherwisethecostisM,whereMisaverylargepositivevalue.Denotex󰀂,ktheamountofproductandc󰀂,ktheunitcostassociatedwithshippingfrombuild-typenode󰀂toorder-typenodek,where󰀂2Â,k2K.Ingeneralthedemandsandsuppliesareunbalanced,thereforetomaketheproblemfeasible,twodummynodes,oneforthebuild-typesideandonefortheorder-typeside,areintroducedintothetransportationnetwork.Indexthedummybuild-typebyjÂjþ1andthedummyorder-typebyjKjþ1,wherejÂjandjKjarethesizesofsetsÂandK,respectively.xjÂjþ1,k,k2K,istheunfulfilledamountofdemandk,andthelinkbetweendummybuild-typejÂjþ1andorder-typek2Kisassociatedwithaunitpenaltycostgk.Symmetrically,x󰀂,jKjþ1,󰀂2Â,istheamountofoverproducedbuild-type󰀂,andthelinkbetweenbuild-type󰀂2Âanddummyorder-typejKjþ1isassociatedwithaunitholdingcosth󰀂.Obviously,itisnecessarytodisabletheshippingbetweentwodummynodes,soweletcjÂjþ1,jKjþ1¼M.Figure1showsanexampleofatransportationnetworkwherejÂj¼4andjKj¼3.Build-typeNo.5andorder-typeNo.4aredummynodeswhichareshownasdashed-lines.Notethatdummynodeshavelinkswithallnon-dummynodesontheotherside.

Theparametrictransportationproblemcanbeformulatedasfollows.ProblemTP:

fðu,dð!ÞÞ¼minimise

þ

subjectto

jÂjþ1X󰀂¼1jÂj,jKjX󰀂¼1,k¼1

jKjXk¼1

gkxjÂjþ1,kþ

jÂjX󰀂¼1

h󰀂x󰀂,jKjþ1

ð7Þ

c󰀂,kx󰀂,kþcjÂjþ1,jKjþ1xjÂjþ1,jKjþ1,

x󰀂,k¼dk,8k2K,ð8Þ

5788

Build-type1G.Sunetal.

Order-type122343Downloaded by [Loughborough University] at 15:47 05 January 2015 5Dummy build-type4Dummy order-typeFigure1.Transportationnetwork.

jXKjþ1k¼1jKjXk¼1

x󰀂,k¼u󰀂,8󰀂2Â,x󰀂,jKjþ1¼

jKjXk¼1

ð9Þ

dkÀ

jÂjX󰀂¼1

xjÂjþ1,kÀ

jÂjX󰀂¼1

u󰀂,ð10Þð11Þ

x󰀂,k!0,

8󰀂¼1,...,jÂjþ1,k¼1,...,jKjþ1,

whereu¼(u1,...,ujÂj)(thebuild-typelevelvector)andd(!)¼(d1(!),...,djKj(!))(the

realisedcustomerdemandvector)areparameters,andcostcoefficientsc󰀂,k2{0,M},󰀂2Â,k2K,aredeterminedbyAVMs.

Thefirstitemof(7)isthesumofpenaltycostsforunfulfilleddemands,theseconditemisthesumofholdingcostsforoverproducedproducts,thethirditemiswheretheAVMskickin,andthefourthitemistoprohibitthetransportationbetweentwodummynodes.Constraints(8)areforthedemandbalancerequirementandconstraints(9)areforthesupplybalancerequirement.Constraint(10)isintroducedtobalancethetotalsupplyandtotaldemand.Constraints(11)arejustforthestandardnon-negativerequirement.Observethatconstraint(10)canbederivedfromconstraints(8)and(9),soitisactuallyredundantandcanberemoved.Thistransportationproblemcanbesolvedefficiently.

3.Solution

Ourproposedsolutiontothebuildpackplanningproblemisagradient-basedinterior-pointapproachwhichisdrivenbyestimatesofthegradientofthecostfunctionwithrespecttotheparametersofinterests.Thegradientsearchisdoneinaniterativemannerwheretheiterationofthemasterproblemstartsfromaninitialfeasibleplanu0.

InternationalJournalofProductionResearch57

Foriterationn,theexpectedcostaswellasitsgradientwithrespecttouareestimatedfromthesolutionsofasetoftransportationproblems.Thegradientestimatoristhenusedtodeterminethefeasiblesearchingdirectionsnforthenextstep.Theproductionplanisupdatedasunþ1¼unþ󰀄nsn,where󰀄nisthestepsize.Werepeatthisprocedureuntilacertainstoppingcriterionismet,sowehaveasequenceofimprovingplanswithinthefeasibleregionandachievethefinalsolutionintheend.Fromtheabovedescriptionwecanseethatthisapproachisactuallyagradient-basedinterior-pointmethod.3.1Convexity

Tomakethegradientsearchalgorithmasuitablestrategy,wefirstneedtoshowthatF(u)isaconvexfunctionofu.

Downloaded by [Loughborough University] at 15:47 05 January 2015 Lemma3.1:F(u)isaconvexfunctionofu,whichmeansthat,foranydifferentu1,u2isinthefeasiblesetand,for05󰀅51,F(󰀅u1þ(1À󰀅)u2)existsandwehave

Fð󰀅u1þð1À󰀅Þu2Þ 󰀅Fðu1Þþð1À󰀅ÞFðu2Þ:

ð12Þ

Proof:Becauseof(6),ifwecanshowthatf(u,d(!))isaconvexfunctionofu,F(u)mustbeconvexsinceitisaconvexcombinationoff(u,d(!)).Nextweprovethatf(u,d(!))isindeedaconvexfunctionofu.ForconveniencewerewritetransportationproblemTPinanabstractformasfollows:

fðu,dð!ÞÞ¼minimisecx,

subjectto

Ax¼dð!Þ,Bx¼u,x!0:

Byconsideringitsdualproblem,wehave

fðu,dð!ÞÞ¼maxdð!Þyþuz,

subjectto

yAþzB!c:

Weomittheparameterd(!)inthisprooffornotationalsimplicity,soourgoalistoshowthat

fð󰀅u1þð1À󰀅Þu2Þ 󰀅fðu1Þþð1À󰀅Þfðu2Þ:

Let

󰀅u1þð1À󰀅Þu2¼u3,

then

fðu1Þ¼maxdyþu1z,fðu2Þ¼maxdyþu2z,fðu3Þ¼maxdyþu3z,

ð20Þð21Þð22Þð19Þð18Þð17Þð14Þð15Þð16Þð13Þ

5790G.Sunetal.

andallaresubjecttothesameconstraints:

yAþzB!c:

Suppose(y1,z1),(y2,z2)and(y3,z3)areoptimalsolutionsof(20),(21)and(22),respectively,thenwehave

fðu1Þ¼dy1þu1z1!dy3þu1z3,fðu2Þ¼dy2þu2z2!dy3þu2z3,

thus

󰀅fðu1Þþð1À󰀅Þfðu2Þ!󰀅ðdy3þu1z3Þþð1À󰀅Þðdy3þu2z3Þ

¼dy3þ󰀅u1z3þð1À󰀅Þu2z3:

Alternatively,wehave

fð󰀅u1þð1À󰀅Þu2Þ¼fðu3Þ¼dy3þu3z3¼dy3þ½󰀅u1þð1À󰀅Þu2󰀄z3

¼dy3þ󰀅u1z3þð1À󰀅Þu2z3:

ð24Þð23Þ

Downloaded by [Loughborough University] at 15:47 05 January 2015 Bycombining(23)and(24)weprove(18)istrue,andthen(12)istrueandtheproofiscompleted.hThemasterproblemisactuallyaconvexprogrammingproblem,hencethegradientsearchwillgiveustheglobaloptimalsolution.

3.2Gradientestimator

InSection2.3weformulatedthepackingprocessasatransportationproblem.Whenitissolved,atoptimalpointx*(!),theshadowpriceofthebuild-type,i.e.thedualvariableassociatedwithconstraint(9),isapartialderivativeoff(u,d(!))withrespecttou.Denotetheshadowpriceofbuild-type󰀂by󰀆Ã󰀂,thenwehave

@fðu,dð!ÞÞ

jx¼xÃð!Þ¼󰀆Ã󰀂,@u󰀂

󰀂2Â:

Wefurtherdefinethegradientoff(u,d(!))withrespecttouas󰀂󰀃@fðu,dð!ÞÞ@fðu,dð!ÞÞ

jx¼xÃð!Þ,...,jx¼xÃð!Þ:rfðu,dð!ÞÞjx¼xÃð!Þ¼󰀆ü

@u1@ujÂj

ThenafterNi.i.d.simulationrunsweobtainasequenceofgradientsrf(u,d(!1)),

rf(u,d(!2)),...,rf(u,d(!N)),andtheestimateofgradientrF(u)isgivenasPð1=NÞNn¼1rfðu,dð!nÞÞ.3.3Searchingdirection

Inthissectionweshowhowtodecideonafeasiblesearchingdirectionsnbasedonthegradientestimatorobtained,whichcanbeusedtoupdatebuildplanuinthefollowingway:

unþ1¼unþ󰀄nsn,

ð25Þ

InternationalJournalofProductionResearch5791

where󰀄nisthestepsizechosenforiterationn.SupposethegradientrF(un)isknown,thentofindanimprovingdirection,whichisadescentdirectioninourcase,theanglebetweenrF(un)andsnshouldbegreaterthan90󰀇,thatis

rFðunÞÁsn 0:

Buttoremainfeasibleforafinitemove,snmustatleastbetangenttoallactiveconstraintsofproblemMP,thatis

rGlðunÞÁsn!0,

l2IA,

Downloaded by [Loughborough University] at 15:47 05 January 2015 whereIAdenotesthesetofactiveconstraints.Fortheinterior-pointmethod,keepingawayfromtheboundaryusuallyacceleratesthesearchandalsoreducesthezig-zageffects.Therefore,weintroduceapush-offfactor󰀇forthoseactiveconstraints,

rGlðunÞÁsnÀ󰀇!0,

l2IA,

where󰀇isanon-negativeconstant.Inpractice,wecanaffordalargerpush-offwhenthegainintheobjectivefunctionislarge(smallabsolutevalueofrF(un)Ásnsinceitisnegative),therefore

rGlðunÞÁsnþ½rFðunÞÁsn󰀄󰀇!0:

MinimisingrF(un)Ásn 0isequivalenttomaximising󰀈inrF(un)Ásnþ󰀈 0,withthefeasiblerequirementrGl(un)ÁsnÀ󰀈󰀇!0.Therefore,tofindtheoptimalsn,weneedtosolvethefollowingdirection-findingproblem.ProblemDF:

maximise󰀈,

subjectto

rFðunÞÁsnþ󰀈 0,rGlðunÞÁsnÀ󰀈󰀇!0,sn:bounded.

Strictlyspeaking,activeconstraintsarethosewheretheequalitysignholds.However,ignoringthosenearlyactiveconstraintsmaycauseazig-zagsearchpath.Toavoidthis,wefurtherintroduceapositivethreshold\"andtreatalltheconstraintssatisfyingGl(un) \"asactive.Intheend,weneedtochooseboundsforsn,sayÀ1 ksnk1 1.Uptonowthedirection-findingproblemhasbeenformulatedasalinearprogrammingproblemthatcanbeeasilysolved.

l2IA,

ð26Þð27Þ

3.4Columngeneration

DenotejVpjthesizeofVp,thenthetotalnumberofbuild-typesisÅp2PjVpj.RecallthatjKjisthetotalnumberoforder-types,sointhetransportationproblem,thetotalnumberofdecisionvariablesisjKjÁÅp2PjVpj.Whentheproblemsizeislarge,itrenderssolutionbygeneral-purposeLP-solversimpractical,ifnotimpossible.Insomerealisticinstances,simplygeneratingallthecoefficientsofthedecisionvariableswillusuallyprohibitthe

5792G.Sunetal.

Downloaded by [Loughborough University] at 15:47 05 January 2015 direct-solvingapproach.Inthissituation,tomakethelarge-sizeproblemmanageable,weproposethecolumngenerationtechnique.

Theoriginalcolumngenerationtechniqueisaspecialisationofthesimplexmethodforlinearprogrammingwhichproceedsbysolvingarestrictedformoftheoriginalproblem(calledthemasterproblem)byconsideringonlyasubsetofallpossiblecolumns(variables).Non-basiccolumnswhichhavethepotentialtocontributetoimprovetheobjectivefunctionaregeneratedatthepricingstagebysolvingaseparatepricingproblem.Thepotentialofanon-basiccolumnisdeterminedbysomecriterion,usuallythereducedcostofthecolumn.Thenewcolumnsfoundarethenaugmentedtothemasterproblemandthemasterproblemisre-solved.Thisprocedureiteratesbetweensolvingthemasterproblemandthepricingproblemuntilnomorecolumnswithpotentialcontributionscanbefound.

Althoughthebuild–packplanningproblemisanonlinearconvexprogrammingproblem,thecolumngenerationideacanstillbeused.DefineproblemRMPastherestrictedversionofproblemMP,whereRMPcontainsonlyasubsetofbuild-types(columns)inMP.DenotethesubsetasÈ,sowehavejÈj jÂj.Thesolutionprocedureisasfollows.FirstwesolvetherestrictedproblemRMPusingourgradientsearchalgorithmanddenotethesolutionasuopt.Next,wecheckthecolumns(build-types)thatarenotinthecurrentRMPforfurtherpossibleimprovementstothissolution.Iftherearenosuchcolumns,thecurrentsolutionisfinalandtheprocedureends.Otherwise,newcolumnsareintroducedintoRMPandthesolvingprocedurerepeats.Inlinearprogramming,findingnewcolumnscorrespondstoscanningfornon-basiccolumnswithnegativereducedcosts.However,sincetheproblemconsideredhereisnonlinear,weneedtodevelopthepricingproblemforit.

FirstweconsiderthecomponentconstraintsinRMP.Thereisatrade-offtobemetifweproduceanewbuild-typeattheexpenseofotherbuild-typescompetingforthesamecomponents.Sohereweexaminethepartofthereducedcostduetothelimitedcomponentavailability.Atuopt,thecurrentoptimalsolutionofRMP,let󰀅vp,vp2Vp,p2P,betheshadowpriceofcomponentpfromvendorvp(thedualvariableassociatedwithconstraint(2)).ThusbytheKKTconditionwehave

XX

󰀅vprGvpðuoptÞ¼0,ð28ÞrFðuoptÞÀ

p2Pvp2Vp

󰀅vpGvpðuoptÞ¼0:

ð29Þ

Thenall󰀅vp,vp2Vp,p2P,canbecalculatedfromtheaboveequationset.Observingfrom

(29),forinactiveconstraintswhereGvp(uopt)40,wehave󰀅vp¼0,andonlyforactiveconstraintswhereGvp(uopt)¼0itispossiblefor󰀅vp40.Therefore,iftherearenoactiveconstraints,or,inotherwords,uoptisaninteriorpoint,weimmediatelyhave󰀅vp¼0forallvp2Vp,p2P.Inthiscase,nocomponentiscritical,sothemarginalcostforintroducinganewbuild-typeis0becauseexistingbuild-typesneednotsacrificetheirconsumptionofcomponentsforthenewbuild-types.Ontheotherhand,ifuoptisontheboundary,oneormoreconstraintsisactiveandthecorresponding󰀅vpcanbesolvedfrom(28)andPthePmarginalvpcomponentcostforintroducinganewbuild-type󰀂2ÂÀÈisp2Pvp2Vp󰀅vpÁ󰀃󰀂,whichisalwaysnon-negative.

Nextwemoveourattentiontothepartofreducedcostinthepackingprocess.Forthetransportationproblem,thesupplyingnodesarenowonlythosebuild-typesbelongingtosubsetÈ.WedenotetherestrictedtransportationproblembyRTP.

InternationalJournalofProductionResearch5793

However,forpurposesofanalysis,thisRTPcanbeseenasaspecialformofthefull-sizetransportationproblem(TP)whereu󰀂areartificiallysetto0forall󰀂2ÂÀÈ.Thenwedenotetheshadowpriceofbuild-type󰀂2ÂÀÈby󰀆󰀂,soÀ󰀆󰀂reflectsthecorrespondingbuild-type’spromiseofimprovingthecurrentplan.Notethat󰀆󰀂,󰀂2ÂÀÈ,cannotbeobtainedfromsolvingproblemRTPsincethosebuild-typesarenotincludedintherestrictedproblem.

Combiningtheabovetwopartsofthereducedcost,thedecisionofwhetherabuild-typeisavalidcandidatetobeintroducedishencedeterminedbythebestoverallpromiseinplanimprovement.Therefore,thepricingproblemcanthenbestatedasfollows.ProblemRP:

XX

p2Pvp2Vp

v

Downloaded by [Loughborough University] at 15:47 05 January 2015 Zr¼minvp

󰀃󰀂

󰀅vpÁ󰀃󰀂pþ󰀆󰀂,

ð30Þ

subjectto

X

󰀃󰀂p¼1,

v

8p2P,8vp2Vp,8p2P,

ð31Þð32Þ

vp2Vpv

󰀃󰀂p2f0,1g,

whereZrin(30)isthereducedcostexpressionforbuild-type󰀂2ÂÀÈ.Solvingthis

v

pricingproblemyieldsafeasiblesetofparametervariables󰀃󰀂p,8vp2Vp,8p2P,indicatingabuild-typewithminimalreducedcost.

TheproblemofsolvingproblemRPdirectlyisthatitneedstoexplicitlyenumer-ateallthecolumns(build-types).Thisiswhatwewanttoavoidbecauseofthelargenumberofcolumns.Furthermore,asmentionedbefore,󰀆󰀂in(30)areavailabletousbysolvingRTP.Therefore,weusethefollowingdecompositionmethodtosolveitindirectly.

Sinceonlywithnegativereducedcostareofinterest,basedontheobser-PPbuild-typesv

vationthatp2Pvp2Vp󰀅vpÁ󰀃󰀂p!0in(30),weonlyneedtoexaminethosebuild-typeswhere󰀆󰀂50.Nextweseehowtojudgethesignof󰀆󰀂.Recallthat,intheformulationofthetransportationproblem,ifabuild-typecanbeassignedtoanorder-type(whichmeansthebuild-typedoesnotviolatetheAVMofthatorder-type),thelinkbetweenthemhasacost0,otherwisethecostisalargeM.InthefollowingdiscussionweremovefromthetransportationnetworkthoselinkswhosecostisM.Theninthenewnetwork,foreachbuild-typethereisagroupoflinkedorder-types,andsymmetricallyforeachorder-typethereisagroupoflinkedbuild-types.Denotetheshadowpriceoforder-typekby󰀆k,whichcanbeobtainedfromsolvingRTP.Forbuild-type󰀂0where󰀆󰀂050,amongitslinkedorder-typestheremustbeatleastonewithpositiveshadowprice.Supposeorder-typek󰀂0istheonewiththelargestpositiveshadowprice,thenwehave󰀆󰀂0¼À󰀆k󰀂0.Ontheotherhand,fororder-typek0where󰀆k040,allitslinkedbuild-typesmusthavenegativeshadowprices.Supposebuild-type󰀂k0istheonewiththesmallestnegativeshadowprice,sowehave󰀆󰀂k0 À󰀆k0.Basedontheaboveanalysiswecanseethattheunknown󰀆󰀂isboundedbyÀ󰀆kforsomek.ThisobservationgivesustheideatodecomposetheproblemRP.Westartbyscanningalltheorder-types.Thisispossiblesincethenumberoforder-typesismoderatecomparedwiththenumberofbuild-types.Ifall󰀆k 0,thisimpliesthatallbuild-typeshaveapositivereducedcost,thenthepricingprocedureterminates.Otherwise,foreachorder-typewithapositiveshadowprice,sayk,weformulate

5794G.Sunetal.

aminimisationsub-problemtodetermineamongitslinkedbuild-typestheonewiththeminimalcomponentcost:

XXv

Zs¼󰀅vpÁ󰀃󰀂p,minvpð33Þ󰀃k

󰀂

p2Pvp2Vp

subjectto(31)and(32).

Ã

,anditscorrespondingSolvingthissub-problemyieldsabuild-type,say󰀂k

Ã󰀂k

optimalcomponentprice,Zs.Theninthesecondstepwesolvetheminimisationproblem

Ã󰀂k

minZrÃ󰀂k

¼

Ã

󰀂kZs

À󰀆k,

ð34Þ

Downloaded by [Loughborough University] at 15:47 05 January 2015 andthesolutionisthenthesolutionofproblemRP.Inthisway,wecansolvethepricingproblembysolvingaseriesofsub-problemsofsmallsize.Notethat,intheabovediscussion,󰀆󰀂and󰀆kareactuallyintheformofaveragesofallreplicationswithdifferentdemandrealisations.

Nextwediscusshowtosolvetheminimisationproblem(33).Thisproblemistofindafeasiblebuild-typethatisincompliancewiththeAVM,tobeassignedtoachosenorder-typekatminimumcost.Thismeansadoptinganetworkrepresentationwherethevendorsarerepresentedbynetworknodes,thenodesforthesamecomponentbeinggroupedintoanetworklayer,andwithanarclinkingtwonodesindifferentlayersonlyiftheydonotviolatetheAVMrequirements.The‘length’ofanarcfeedingintoanodeassociatedwith

v

componentvendorvpisthenthecostcoefficientof󰀃󰀂pinexpression(33),󰀅vp.Anyfeasiblewalkthroughallthecomponentlayersconstitutesafeasiblebuild-type.ForacertaintypeofAVM,thecomponentlayerscanbeputintandemformasshowninFigure2,wheretherearethreelayers,A,BandC,and,withineachlayer,anoderepresentsacomponentvendor,i.e.therearethreevendorsforcomponentA,twoforB,andfourforC.

Inthisnetworkrepresentation,problem(33)isequivalenttofindingtheshortestdirectpathfromthesourcenodetothesinknodethroughthelayersofcomponentnodes.However,thisnetworkrepresentationhassomerestrictions.Itonlyappliestothecasewherethecomponentlayerscanbeputintandemform.Butthisrestrictiondoesnotplaceasignificantlimitationonreal-worldapplicationssince,inmostpracticalcases,thecustomerrequirementsarebetweentwocomponentsonly,whichiscoveredbyournetworkrepresentation.

Component AComponent BComponent CSource nodeSink nodeFigure2.Shortestpathnetwork.

InternationalJournalofProductionResearch5795

Inthefollowingwedefinethecomponentsoftheshortestpathnetwork.LetthenetworkofconcernbeG(N,A),whereNisthesetofnodesandAisthesetofarcsinthenetworkconnectingthecomponentnodesinthespecial‘layered’structure,A&NÂN.Letyi,jdenotetheflowleavingnodeiandenteringnodej,wherearc(i,j)2A.Definethesourcenodeaandthesinknodeb.Furthermore,foreachvendorvp2Vkpofeachcomponentp2P,definethecomponentnodenvp.ThestructureofGissuchthatthenodesnvp,8vp2Vkp,foreachcomponentpformalayerofnodes,andthelayersarearrangedintandeminthenetwork.Inordertoobtainacompletebuild-type,theremustbeflowfromatobthroughoneandonlyonenodeperlayerthroughtheseriesoflayersofcomponentnodes.Anarcðnvp,nvp0Þexistsonlyifthepairofcomponentspandp0constituteadjacentlayersinthenetwork,andsuchthatvpandvp0donotviolateAVMrestrictionsfororder-typek.Theshortestpathproblemassociatedwithorder-typekisstatedasfollows.

Downloaded by [Loughborough University] at 15:47 05 January 2015 ProblemLPk:

minimise

subjectto

XX

p2P

vp2Vkp

24󰀅vpÁ

X

i:ði,nvpÞ2A

3yi,nvp5,

ð35Þ

X

j:ða,jÞ2A

ya,j¼1,yi,b¼1,ynvp,j¼

X

i:ði,nvpÞ2A

ð36Þð37Þ

yi,nvp,

8vp2Vkp,8p2P,

ð38Þð39Þ

X

X

i:ði,bÞ2A

j:ðnvp,jÞ2A

yi,j2f0,1g,

8ði,jÞ2A:

Equations(36–38)arenetworkflowbalanceequationsforthesourcenodea,sinknodeb

andeachofthecomponentnodes,respectively.Equation(39)imposesyi,jtobediscrete,butduetothenetworkstructureoftheproblem,totalunimodularityguaranteesyi,jtobeanintegerintheoptimalsolution.Thisnetworkproblemiseasilysolved.

Insummary,ourproceduretosolveRPstartsfromscanningtheorder-types.Anorder-typeisofinterestonlyifitsshadowpriceinRTPispositive.Foreachofthoseorder-typeswesearchforacorrespondingbuild-typethatminimisesthevalueofZsin(33).Fororder-typek,thisisaccomplishedbysolvingtheshortestpathproblemLPk.Theresultingbuild-typeisavalidcandidateforthefinalsolutionifZsÀ󰀆k50.Thebuild-typewiththegreatestoverallpromise(smallestreducedcost)isthenintroducedintothesetofÈ.Ifwesettheinitiallevelofthenewbuild-typeto0,theprevioussolutionuoptisstillfeasibleinthenewproblem,butnotoptimal.Startingfromthispointthenewproblemisresolved.Thealgorithmstopswhenthereisnobuild-typeinÂÀÈhavinganegativereducedcost.Thenthesolutionisthefinalsolution.

3.5Thealgorithm

Inthissectionwesummarisethealgorithmdevelopedabove.ProcedureMPperformsthegradientsearchtofindtheoptimalsolutionforagivenrestrictedproblemRMP.

5796G.Sunetal.

ProcedureMP:(1)(2)(3)(4)(5)(6)(7)

Initialisethebuild-typelevelu,step-size󰀄.Generateademandrealisationd(!).

FormulatethetransportationproblemTPandsolveit,obtainf(u)andrf(u).Ifnomoredemandsampleisneeded,proceedtoStep(5).Otherwise,gobacktoStep(2).

AverageoverthetotalnumberofdemandrealisationstoobtainthecostandgradientestimatorFðuÞandrFðuÞ.

Ifthestoppingcriterionismet,theprocedureMPterminatesanduandFðuÞarereturned.Otherwise,proceedtoStep(7).

FormulatethedirectionfindingproblemDFandsolveit,obtainthesearchdirections.

Updatebuild-typelevelbyuþ󰀄Ás,thengobacktoStep(2).

Downloaded by [Loughborough University] at 15:47 05 January 2015 (8)

WhenimplementingprocedureMP,thereisatrade-offbetweenthestoppingcriteriaandthecomputationaleffort.Itisnotnecessarytohaveatoostrictstoppingcriteriabecausethemasterproblemwillbere-solvedwhennewcolumnsaregenerated.Thestepsize󰀄isarbitrarilychosenforeachiterationandifitmakesthenextpointgobeyondthefeasibleregion,ithastobereduced.

Attheoptimalsolution,procedurePricebelowisusedtofindthenewcolumn(build-type)tobeintroducedintosetÈ.ProcedurePrice

(1)InitialisethecurrentbestsolutionvalueZÃr¼0.

(2)Selectanorder-typek2Kasacandidate.IfitsshadowpriceinRTP󰀆k 0,then

eliminatethecandidateofkandproceedtoStep(3).Otherwise,gotoStep(5).(3)IftherearestillunselectedkfromK,gotoStep(2).Otherwise,proceedtoStep(4).(4)IfZÃr¼0,thennoenteringnon-basicbuild-types󰀂2ÂÀÈcanbelocated.

Otherwise,thecurrentsolutiontoRPisusedtoformthenewcolumntoenterthesetÈ.ProcedurePriceterminates.

(5)SolvethefollowingshortestpathproblemLPkassociatedwiththecandidatekand

obtaintheminimumcostZs.

Ã

(6)ComputeZr(k)¼ZsÀ󰀆k.IfZrðkÞ5ZÃr,thenupdateZr¼ZrðkÞ.GotoStep(3).OncethesetÈisupdated,themasterproblemMPisthenre-solvedandthestepsofsolvingRParerepeated.Therefore,thecolumngenerationiterationismostlyouteriteration.Theprocedureofcolumngenerationcanbesummarisedasfollows.ProcedureCG:

(1)Initialisetherestrictedcolumn(build-type)setÈ.

(2)SolvetherestrictedmasterproblemRMPtooptimalityusingprocedureMP.(3)UsetheKKTconditionofRMPtocalculatetheshadowprice󰀅vpofcomponentp

fromvendorvp,thendefinethecorrespondingpricingproblemRPandsolveitusingprocedurePrice.

(4)IfthesolutiontoRPgivesnonon-basicvariableswithnegativereducedcost,then

thecurrentsolutionofRMPisoptimalinMP,andtheprocedureends.Otherwise,proceedtoStep(5).

(5)UpdatethecolumnsetÈwiththenewlygeneratedcolumn.GobacktoStep(2).

InternationalJournalofProductionResearch5797

3.6Numericalresults

Inthissectionwetestourgradient-basedoptimisationalgorithmbysimulation.Notethatthegoalofthesecomputationalexperimentsistoverifythecorrectnessofouralgorithminsteadofsolvingareal-worldproblem.

3.6.1Experiment1:threecomponents,10suppliersforeachcomponentand10customer

ordertypeswithrestrictiveAVMconstraintsWeassumethattheproductconsistsofthreecomponents,denotedA,BandC.Foreachofthesecomponents,thereare10vendorsavailable,indexedfrom0to9.Wetestedthreescenarioswithdifferentcomponentavailabilityandpenaltycostsforshortages.ThecomponentavailabilityisgiveninTable1.

Weuseathree-digitnumberfrom000to999todenoteaspecificbuild-type,forexamplebuild-type‘308’hascomponentAsuppliedbyvendorA3,componentBsuppliedbyvendorB0,andcomponentCsuppliedbyvendorC8.Thereare20customerswithdifferentAVMs,i.e.thereare20differentorder-types,indexed0,...,19.Thecorrespon-dencebetweenbuild-typesandorder-typesisrandomlysetandisshowninTable2.Forexample,customerorder-type6allowsthecomponentvendorcombinationA6,B5andC3,andcomponentvendorcombinationA1,B7andC0.

Table1.Componentavailability.ComponentAScenario1Scenario2Scenario3ComponentBScenario1Scenario2Scenario3ComponentCScenario1Scenario2Scenario3

A0850850850B0500500500C0120012001200

A1450450450B1800800800C1300300300

A2100010001000B2800800800C2700700700

A3600600600B3140014001400C3450450450

A4450450450B4500500500C4145014501450

A5300300300B5900900900C55005000

A6350350350B6300300300C6350350350

A7700700700B7650650650C7500500500

A8700700700B8600600600C8100010001000

A9130013001300B9400400400C9700700700

Downloaded by [Loughborough University] at 15:47 05 January 2015 Table2.Correspondencebetweenbuild-typeandorder-type.Order-typeBuild-typeOrder-typeBuild-typeOrder-typeBuild-typeOrder-typeBuild-type

0

985/740/26750741052515

334/310

18006

653/17011

334/72916

008/578

2239798012

823/17917746

30841393218

920/720/582

4

7/371/61699171429819138

5798

Table3.Demandprofile.Order-type󰀉󰀊2Order-type󰀉󰀊20446771027834

1371501130141

2322311227828

G.Sunetal.

3468661349921

4306921436827

52156616996

6214481620339

7470461733484

8452351821966

9253481945245

Table4.Unitpenaltycostforshortage.Order-typeScenario1Scenario2Scenario3Order-typeScenario1Scenario2Scenario3

07191910777

111111111112020

2197712888

312121213121212

4610101481919

512121215121212

61088161066

720202017191010

888818888

966619201111

Downloaded by [Loughborough University] at 15:47 05 January 2015 Therandomdemandofeachorder-typeisassumedtobenormallydistributedwithgivenmean󰀉andvariance󰀊2,withtheassumptionofnon-negativity.󰀉and󰀊2aregeneratedusingauniformrandomnumbergeneratorandthevaluesusedinourexperimentareshowninTable3.

Assumeallbuild-typeshavethesameunitholdingcostof1,whilethepenaltycostforunmetdemandforeachcustomerisarbitrarilysetasinTable4.

Tosummarise,scenarios1and2aredifferentwithrespecttotheunitshortagepenalty;scenario3isanextremecasecomparabletoscenario2,asscenario3hasonesupplierunabletosupplyoneofthecomponents,i.e.thecomponentavailabilityforcomponentC5inscenario3is0.

ForeachiterationoftheprocedureMPweran20customerdemandrealisationsandtheaverageof20simulationreplicationsisusedtoestimatethecostandgradientestimators.Wefoundthat20isareasonablenumberinourexperimentstobalancethetrade-offbetweencomputationalburdenandaccuracyofestimation(thestandarddeviationislessthan20%oftheresults).Thestep-sizeforthegradient-searchisre-setto10atthebeginningofeachiterationandismultipliedby0.618eachtimeifthecurrentstep-sizeistoolargetokeepthenextpointinsidethefeasibleregion.AllthesimulationsweretestedonanIntel(R)Core(TM)2Duo2.66GHzPCwith4GBRAMandWindowsVistaEnterpriseEdition.TheprogramsarecodedinCþþandILOGCPLEX11.0LPandnetworksolverlibrariesareusedtosolvethesub-problems.

Figure3demonstratesthesimulationresultsandshowsthatthetrendofthecostcurvesinthethreescenariosisquitesimilar,andallofthemtookabout20minutestoobtainananswer.

Forcomparisonpurposes,were-solvedtheabovethreescenariosusingthealgorithmwithoutthecolumngenerationscheme.Itwasassumedtohavereachedtheglobaloptimalsolution.PairedcomparisonsbetweensimulationswithandwithoutcolumngenerationareshowninFigure4.

Downloaded by [Loughborough University] at 15:47 05 January 2015 Figure3.Experiment1.

InternationalJournalofProductionResearch

5799

5800G.Sunetal.

Downloaded by [Loughborough University] at 15:47 05 January 2015 Figure4.Comparisonofusingandnotusingcolumngeneration.

InternationalJournalofProductionResearch5801

Wecanseefromthefiguresthatthecolumngenerationalgorithmsuccessfullyreducesthecosttothesamelevelasthatfoundbytheglobalsearchinallthreescenarios.Ifcolumngenerationisnotused,thecomputationaltimeincreasessubstantially,fromabout20minutestoabout10hours.Therefore,thesetestsdemonstratethatthecolumngenerationmethodgreatlyreducesthecomputationalburdenwithoutcompromisingthequalityoftheresults.

3.6.2Experiment2:threecomponents,10suppliersforeachcomponentand10customer

order-typeswithmorerelaxedAVMconstraints

Tobettertestthecapabilitiesofouralgorithm,wefurtherformulatedthreemuchlargerproblems.ThesettingsaresimilartoExperiment1,exceptthatthenumberofcombi-nationsofvendorsthateachcustomercanacceptislarger(rangingfrom10to30).Forthiscase,asthenumberofcolumnsisverylarge,itisimpossibletoloadallthepossiblecolumnsintotheCPLEXsolver.Hence,weranonlythecolumngenerationalgorithmforthosethreescenariosandtheresultsareshowninFigure5.Itcanbeseenthatouralgorithmstillperformedquitewellforlarge-sizedproblems.Theobjectivevaluedecreasesquicklyandconvergestoaminimumlevel.

3.6.3Experiment3:threecomponents,10suppliersforcomponentA,15suppliersfor

componentB,12suppliersforcomponentCand80customerorder-typeswithlargeAVMsTounderstandhowouralgorithmperformsunderalarge-scaleproblem,wedesignedatestscenariowithalargeproblemsize.Inthisscenario,thereare10suppliersforcomponentA,15suppliersforcomponentB,and12suppliersforcomponentC.Thematerialavailabilityforeachsupplierisrandomlygeneratedintherange1000to3500.Thenumberofcustomersincreasesfrom20to80.Furthermore,theunitshortagecostisalsogeneratedrandomlyintherange1–20.

Thecomputationaltimeneededtoperformthetest,asshowninFigure6,wasroughly20hours.Weseeaverysimilartrendforthecostcurveasinpreviouscases,whichconvergestoanear-optimalsolution.

Theproblemsizeconsideredhereisreasonablylargeforareal-worldsetting.Althoughthecomputationaltimeislong,wefeelthatitisstillreasonable,asproductionplanningisusuallydoneonaweeklybasis.Moreover,wefeelthatthiscomputationaltimecanbeshortenedifwecodeourprogrammoreefficiently.Currently,themajorcomputationaltimecomesfromloadingthemodelsintothesolver.

Downloaded by [Loughborough University] at 15:47 05 January 2015 4.Extensiontothemulti-periodandrollinghorizoncase

Inprevioussectionswehavedevelopedasolutionforthebuild–packplanningproblemforthecaseofasingleperiod.Inthissection,wetrytoextendourapproachtothemulti-periodcase.SupposewehaveaplanninghorizonofTperiodsandindexthembyt2{1,...,T}.Whenperformingplanningatthebeginningofthehorizon,thecustomerdemandsfortheentirehorizonareunknowntotheplanner,butweassumethecustomerprofilesforeachperiodareknown.Thedemandunfulfilledwithinitsownperiodisbackloggedandmaybefulfilledinfutureperiod(s)withatardinesspenalty,suchasgkfordemandkforeachperiodofdelay.Anydemandthatisunfulfilledattheendofthe

5802G.Sunetal.

Downloaded by [Loughborough University] at 15:47 05 January 2015 Figure5.Experiment2,withrelaxedAVM.

horizonischargedwithaone-timeshortagepenalty,suchasGkfordemandk.Symmetrically,abuild-typethatisnotusedupinitsownproductionperiodwillexperienceaholdingcost,suchash󰀂forbuild-type󰀂foreachperiodofholding.Theleftoverofthebuild-typeattheendofthehorizonischargedwithaone-timesalvagecost,suchasH󰀂forbuild-type󰀂.Theschedulesofcomponentsupplyfromthevendorsfor

InternationalJournalofProductionResearch5803

Downloaded by [Loughborough University] at 15:47 05 January 2015 Figure6.Experiment3.

thewholehorizonarefixedinadvanceandknowntotheplanner.Theunusedcomponentsinoneperiodarerolledovertothenextperiod.NotethattheprofileandAVMofacertaincustomeraswellastheavailabilityofacertaincomponentarenotnecessarythesamefromperiodtoperiod.

Themulti-periodbuild–packplanningproblemisdescribedasdeterminingwhichbuild-typetobuildandhowmuchtobuildineachproductionperiodandhowtopackthemfordifferentcustomerordersindifferentperiods.Superscripttisintroducedtodenotedifferentperiods,andtheproblemformulationiswrittenasfollows.ProblemMP:

minimiseFðu1,...,uTÞ,

subjectto

GvpðuÞ¼

ut󰀂

t

tXt0¼1

0

mtvp

ð40Þ

À

tXÂXt0¼1

󰀂¼1

󰀃󰀂put󰀂!0,

v

8vp2Vp,8p2P,t¼1,...,T,ð41Þð42Þ

!0,8󰀂2Â,t¼1,...,T:

Fortheformulationofthetransportationproblem,thesupplyingnodesarea

collectionofbuild-typesinallperiods,u1,...,uT,andthedestinationnodesareacollectionoforder-typesinallperiods,d1(!),...,dT(!).Therealisationsofcustomerdemandaregeneratedfromthecustomerprofileineachperiod.Similartothesingle-periodcase,thelinkbetweenasupplyingnodeandadestinationnodewhichisprohibitedbythecorrespondingAVMtakesaunitcostM.ForotherlinkswhichareallowedbytheAVMs,however,weassociateeachlinkwithacostinthefollowingway.Consideranallowedlinkbetweenbuild-type󰀂inperiodt(denoted(󰀂,t))andorder-typekinperiodt0(denoted(k,t0)),where󰀂2Â,k2K,t,t02{1,...,T}.Ift¼t0,thecostassociatedwiththislinkissetto0.Otherwise,ift5t0,thecostissetto(t0Àt)h󰀂,andift4t0thecostissetto(tÀt0)gk.Therearealsotwodummynodes,oneforeachside.Denotethedummybuild-typeby(jÂjþ1,Tþ1)andthedummyorder-typeby(jKjþ1,Tþ1),thenthecostassociatedwith

5804G.Sunetal.

thelinkbetween(jÂjþ1,Tþ1)and(k,t0)issettoGkandthecostassociatedwiththelinkbetween(󰀂,t)and(jKjþ1,Tþ1)issettoH󰀂.Asforthesingle-periodcase,thelinkbetweentwodummynodesissetacostM.Denotexð󰀂,tÞ,ðk,t0Þtheamountshippedfrombuild-typenode(󰀂,t)toorder-typenode(k,t0),where󰀂2Â,k2K,t,t0¼1,...,Tandc(󰀂,t),(k,t0)istheunitshippingcost.Thetransportationproblemthenbecomesasfollows.ProblemTP:

fðu,...,u,dð!Þ,...,dð!ÞÞ¼minimise

þ

jÂjTXXt¼1󰀂¼1

1

T

1

T

jKjTXXt0¼1k¼1

GkxðjÂjþ1,Tþ1Þ,ðk,t0Þ

H󰀂xð󰀂,tÞ,ðjKjþ1,Tþ1Þ

cð󰀂,tÞ,ðk,t0Þxð󰀂,tÞ,ðk,t0Þ

ð43Þ

Downloaded by [Loughborough University] at 15:47 05 January 2015 þ

jÂj,jKjTXXt,t0¼1󰀂¼1,k¼1

þcðjÂjþ1,Tþ1Þ,ðjKjþ1,Tþ1ÞxðjÂjþ1,Tþ1Þ,ðjKjþ1,Tþ1Þ,

subjectto

jÂjTXXt¼1󰀂¼1jKjTXXt0¼1

k¼1

xð󰀂,tÞ,ðk,t0ÞþxðjÂjþ1,Tþ1Þ,ðk,t0Þ¼dtk,xð󰀂,tÞ,ðk,t0Þþxð󰀂,tÞ,ðjKjþ1,Tþ1Þ¼ut󰀂,xðjÂjþ1,Tþ1Þ,ðk,t0ÞÀ

jÂjTXXt¼1󰀂¼1

0

8t0¼1,...,T,8k2K,8t¼1,...,T,8󰀂2Â,

jKjTXXt0¼1k¼1

t0

dk

ð44Þð45Þ

ut󰀂,

ð46Þð47Þ

jKjTXXt0¼1k¼1

xð󰀂,tÞ,ðjKjþ1,Tþ1Þ¼À

jÂjTXXt¼1󰀂¼1

xð󰀂,tÞ,ðk,t0Þ!0,

8t,t0¼1,...,T,8󰀂¼1,...,jÂjþ1,8k¼1,...,jKjþ1:

Thismulti-periodproblemformulationcanbeseenasanexpandedsingle-period

problem.Therefore,ourgradientsearchapproachforsolvingthesingle-periodproblemandthecolumngenerationschemecanbeappliedtothemulti-periodcasewithafewminormodifications.

Onefactweobservedisthattwotermsin(41)arenowtheaccumulationsoverperiodsfrom1tot.Thisonlyaffectsthemeaningofthedualvariablesassociatedwiththem.WedenotethedualvariableassociatedwithGvp(ut)in(41)by󰀋vp,t,sotheKKTconditions(28)and(29)stillholdifwereplace󰀅vpby󰀋vp,t.Asforthesingle-periodcase,󰀋vp,t,8vp2Vp,8p2P,t¼1,...,T,canbesolvedfromtheaboveKKTequations.Ifwefurtherdenotetheshadowpriceofcomponentpfromvendorvpinperiodtby󰀅vp,t,itcanbeexpressedasfollows:

󰀅vp,t¼

TXt0¼t

󰀋vp,t0,

ð48Þ

wherevp2Vp,p2P,t¼1,...,T.Therefore,if󰀋vp,tisknown,󰀅vp,tcanbecomputed

from(48).

Denotethesubsetofchosenbuild-typesinperiodtbyÈPt,thenPthemarginalvp

componentcostforintroducinganewbuild-type󰀂2ÂÀÈtisp2Pvp2Vp󰀅vp,tÁ󰀃󰀂.

InternationalJournalofProductionResearch5805

IntherestrictedtransportationproblemRTP,ifwedenotetheshadowpriceofbuild-type󰀂2ÂÀÈtby󰀆(󰀂,t),thenthepricingproblemcanbestatedasfollows.ProblemRP:

minZr¼vp

t,󰀃󰀂

XX

p2Pvp2Vp

󰀅vp,tÁ󰀃󰀂pþ󰀆ð󰀂,tÞ,

v

ð49Þ

subjectto

X

vp2Vp

󰀃󰀂p¼1,

v

v

8p2P,ð50Þð51Þ

ð52Þ

Downloaded by [Loughborough University] at 15:47 05 January 2015 󰀃󰀂p2f0,1g,8vp2Vp,8p2P,t2f1,...,Tg,

whereZrin(49)isthereducedcostexpressionforbuild-type󰀂2ÂÀÈt.Solvingthis

v

pricingproblemyieldsaperiodtandafeasiblesetofparametervariables󰀃󰀂p,8vp2Vp,8p2P,indicatingabuild-typeinacertainperiodtobeselected.

Since󰀆(󰀂,t)arenotavailable,theprocedureforsolvingproblemRPfollowsthesameideaasforthesingle-periodcase,butnotethat󰀆(󰀂,t)nowhastheholding/tardinesscostinvolved.Theshadowpriceoftheorder-typenodecanbeobtainedbysolvingRTP,sowestartbyscanningtheorder-typenodeslookingforthosewithapositiveshadowprice.Wethenfocusononeofthoseorder-typenodes,say(k,t0),soshadowprice󰀆(k,t0)indicatesanimprovementofthecurrentplanifincreasingthesupplyofthisnode.Differentfromthesingle-periodcase,thecostofintroducingoneofitslinkedbuild-typenodes,say(󰀂,t),containsnotonlythecomponentcost,butalsotheholding/tardinesscostift¼t0.Thusweformulateaminimisationsub-problemtodeterminefromamongitslinkedbuild-typestheonewiththeminimalcost:

XXv

Zs¼󰀅vp,tÁ󰀃󰀂pþ1½t5t0󰀄Áðt0ÀtÞh󰀂þ1½t4t0󰀄ÁðtÀt0Þgk,minvpð53Þt,󰀃k

󰀂

p2Pvp2Vp

subjectto(50–52),where1[Á]isthestandardindicatorfunction.Solvingthissub-problemt

󰀂ðk,t0Þt

yieldsabuild-typenode,󰀂ðk,t0Þ,anditscorrespondingoptimalcost,Zs.Thenbysolvingtheminimisationproblem

t󰀂ðk,t0ÞZminrt

󰀂ðk,t0Þ

¼

t󰀂ð0Zsk,tÞ

À󰀆ðk,t0Þ,

ðÞ

weobtainthesolutionofproblemRP.

Nextwediscusshowtosolvetheminimisationproblem(53).Wecanmakeuseofthenetworkrepresentationforthesingle-periodcase,butsincethecomponentcostvariesindifferentperiods,weneedtobuildanetworkforeachperiodandsolveitscorrespondingshortpathproblem.Forthenetworkofperiodt,thesolutionoftheshortpathproblemgivesabuild-typewithlowestcomponentcostinthisperiod.Thislowestcomponentcostplusthecorrespondingholding/tardinesscostisthenthecostZsforperiodt.ComparingZsforallperiods,theonewiththeminimalcostindicatesthesolutionof(53).

Otherthantheaboveissues,themulti-periodproblemisthesameasthesingle-periodproblem,soweomitthedetailshere.

5806G.Sunetal.

Downloaded by [Loughborough University] at 15:47 05 January 2015 Inpractice,multi-periodproductionplanningisusuallycarriedoutinarollinghorizonfashion,thatis,whenaplanisissuedonlythefirstfewperiodsoftheplanareexecuted,thentheplanninghorizonrollsandtheproductionplanningisredoneforthenewhorizon.Forinstance,afirmmightplanforthenext24weeks,butthenrevisetheplanonceamonth.Rollinghorizonplanningisexpectedtoyieldabetterperformancebecauseitincorporatesnewinformationfromtherealiseddemandsandupdatestheplanaccord-ingly.Inarollinghorizonscenario,whenperformingtheplanningtherearecertaininitialconditions,suchascomponentshavingleftoversfrompastperiods,previousordersmaybebackloggedandneedtobefulfilled,andoverproducedbuild-typesmaybeassignedtofuturedemandinthenewhorizon.Henceinthemasterproblem(40),wehaveanextratermofthecomponentleftovertobeaddedtotheavailablecomponentin(41).Inthetransportationproblem,wehaveadditionalconstantvectorsu0andd0toindicatetheinitialvaluesofthebuild-typesanddemandsandthecorrespondingnodesareaddedtothetransportationnetwork.Everythingelseisthesameasforthemulti-periodcase,sosolvingthisproblemisquitestraightforwardandwedonotgointodetailhere.

5.Conclusion

Inthisstudywehavesolvedaproductionplanningproblemthataccountsforapprovedvendormatrixrequirementsandtheuncertaintyofcustomerdemand.Wehavetermedourproblemthebuild–packplanningproblemsincetherearetwotypesofplanningdecisions,i.e.whattobuild,andwhotopackfor.Theformerdecisionwasmodeledasanonlinearprogrammingproblemwhosedecisionvariablesaretargetbuild-typelevels,whilethelatterdecisionwasmodeledasastochastictransportationproblem.Theobjectivefunctionofthefirstproblemisthesolutionofthetransportationproblemwiththetargetbuild-typelevelsasparameters.Bygeneratingabunchofsimulatedcustomerdemands,theaveragedshadowpriceofthebuild-typelevelgivesanestimateofitsgradient.Thenweusedagradient-basedinterior-pointmethodtosearchfortheoptimalsolution.Tohandlelargeproblemsizes,weintegratedthecolumngenerationschemeintoourapproach.Numericalresultsshowthatourproposedalgorithmperformssignificantlybetterthanthenon-columngenerationmethodintermsofcomputationtimewithoutsacrificingthequalityofthesolutions.Furthermore,weextendedoursingle-periodapproachtothemulti-periodrollinghorizoncase.

Thereisatrade-offbetweensimulationefficiencyandaccuracyofestimationwhendealingwithrandomdemands.Themoresamplesused,themoreaccuratethegradientsobtainedandthebetterthechanceofselectingagoodnewcolumn,but,concurrently,thecomputationtimeincreasesaccordingly.Ifthereareinsufficientsamples,thereisariskthatthegradientestimatesmightnotbeaccurateenoughfortheoptimalsearchandthecolumngeneratedmightnotbeagoodone.Inourexperimentswechosetorun20samplesforeachstep,butthereisnoguaranteethatthisisauniversalgoodchoice.Thus,oneareaoffuturestudycouldbetodevelopasystematicwayofdeterminingtheoptimalnumberofsimulationreplications.Moreover,thereisatrade-offbetweenhowmuchtimeweneedtospendinfindingagoodcolumnandhowmanycolumnswecangenerate.Ifwehavenotgeneratedenoughcolumns,wemaynothaveexploredthewholedesignspacesufficientlyandhencetheapproachwouldnotgiveusagoodsolution.Thiscouldbeanotherfutureresearchtopic.

InternationalJournalofProductionResearch5807

Acknowledgement

ThisworkissponsoredbyNUSRPR-266-000-026-490.

References

Chu,S.C.K.,1995.Amathematicalprogrammingapproachtowardsoptimizedmasterproduction

scheduling.ProductionEconomics,38(2/3),269–279.

Dantzig,D.,1963.Linearprogrammingandextensions.Princeton:PrincetonUniversityPress.

Gilmore,P.C.andGomory,R.E.,1961.Alinearprogrammingapproachtothecuttingstock

problem.OperationsResearch,9(6),849–859.

Graves,S.C.,1982.Usinglagrangeantechniquestosolvehierarchicalproductionplanning

problems.ManagementScience,28(3),260–275.

Hax,A.C.andMeal,H.C.,1975.Hierarchicalintegrationofproductionplanningandscheduling,

Studiesinmanagementsciences.Vol.1,Logistics,Amsterdam:Elsevier,6–25.

Hodges,S.D.andMoore,P.G.,1970.Theproduct-mixproblemunderstochasticseasonaldemand.

ManagementScience,17(2),107–114.

Kao,E.P.C.andQueyranne,M.,1986.Aggregationinatwo-stagestochasticprogramfor

manpowerplanningintheservicesector.In:A.J.SwerseyandE.J.Ignall,eds.Deliveryofurbanservices(TIMSstudiesinthemanagementsciences.Vol.22,Amsterdam:North-Holland.

Kira,D.,Kusy,M.,andRakita,I.,1997.Astochasticlinearprogrammingapproachtohierarchical

productionplanning.TheJournaloftheOperationalResearchSociety,48(2),207–211.

Lee,L.H.,Chew,E.P.,andNg,T.S.,2005a.Productionplanningwithapprovedvendormatricesfor

ahard-diskdrivemanufacturer.EuropeanJournalofOperationalResearch,162(2),310–324.Lee,L.H.,Chew,E.P.,andNg,T.S.,2005b.Amulti-stagebendersdecompositionmethodfora

hard-diskdriveproductionplanningproblem.JournalofManufacturingSystems,24(4),315–327.

Metters,R.,1997.Productionplanningwithstochasticseasonaldemandandcapacitated

production.IIETransactions,29(11),1017–1029.

Nemhauser,G.L.andWidhelm,W.B.,1971.Amodifiedlinearprogramforcolumnarmethodsin

mathematicalprogramming.OperationsResearch,19(4),1051–1060.

Ng,T.S.,Lee,L.H.,andChew,E.P.,2006.Build–packplanningforharddiskdriveassemblywith

approvedvendormatricesandstochasticdemands.EuropeanJournalofOperationalResearch,175(2),1117–1140.

Peters,R.J.,Boskma,K.,andKuper,H.A.E.,1977.Stochasticprogramminginproduction

planning:Acasewithnon-simplerecourse.StatisticaNeerlandica,31(1),113–126.

Rockafella,R.T.andWets,R.J.B.,1985.ALagrangeanfinitegenerationtechniqueforsolving

linear-quadraticproblemsinstochasticprogramming.In:A.PrekopaandR.J.B.Wets,eds.Stochasticprogramming(Mathematicalprogrammingstudy).Amsterdam:North-Holland.Swaminathan,J.M.andTayur,S.R.,1998.Managingbroaderproductlinesthroughdelayed

differentiationusingvanillaboxes.ManagementScience,44(12),161–172.

VanSlyke,R.M.andWets,J.B.,1969.L-shapedlinearprogramswithapplicationstooptimal

controlandstochasticprogramming.SIAMJournalonAppliedMathematics,17(4),638–663.Wang,D.W.,1995.Earliness–tardinessproduction-planningapproachesformanufacturingsystems.

ComputersandIndustrialEngineering,28(3),425–436.

Wets,R.J.B.,1974.Stochasticprogramswithfixedrecourse:Theequivalentdeterministicprogram.

SIAMReview,16(3),309–339.

Downloaded by [Loughborough University] at 15:47 05 January 2015