资源描述：
《a cutting plane approach for the single-product assembly system design problem》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
ACuttingPlaneApproachfortheSingle-ProductAssemblySystemDesignProblembyRaduGadidovEmeryWorldwideAirlines,Vandalia,Ohio45377and1WilbertWilhelmTexasA&MUniversity,CollegeStation77843-31311CommunicatingAuthor;e-mail:wilhelm@tamu.eduApril24,1999Abstract.Thispaperevaluatesanewbranch-and-cutapproach,establishingacomputationalbenchmarkforthesingle-product,assemblysystemdesign(SPASD)problem.Ourapproach,whichincludesaheuristic,preprocessing,andtwocut-generatingmethods,outperformedOSLinsolvingasetof102instancesoftheSPASDproblem.Theapproachisrobust;testproblemsshowthatitcanbeappliedtovariationsofthegenericSPASDproblemthatweencounteredinindustry.1.IntroductionThetraditional(TypeI)assemblylinebalancing(ALB)problemistoassignasetoftaskstostations,minimizingthenumberofstationsrequiredwhileobservingtaskprecedencerelationshipsandacycletimerequirement.ThispaperdealswithanextensionoftheALBproblem,thesingle-productassemblysystemdesign(SPASD)problem.TheobjectiveofthegenericSPASDproblemistominimizethetotalcostofsystemdesign;ingeneral,thisconsistsofthefixedcostsofactivatingstationsandpurchasingmachinesandthevariablecostofassemblyovertheplanninghorizon.Weassumethatallofthesecostsaredeterministicandknowninadvance.Wealsoassumethatthesetofimmediatepredecessorsforeachtaskisknown.Therequirementsarethateachtaskmustbeassignedtosomestationandthatassignmentsobservetaskprecedences.Eachtaskcanbeperformedonanyoneofasetofalternativemachines,andweassumethattheprocessingtimeoneachalternativemachineisdeterministicandalsoknowninadvance.Finally,weassumethatallstationshavethesamecycletimec,whichisalsodeterministicandknown.Inaddition,thispaperdealswithtwoactualSPASDproblemsweencounteredinindustry.Thefirstallowsparallel,identicalmachinestobelocatedateachstation.Thisconfigurationallows“long”jobs(i.e.,withprocessingtimeslargerthanthecycletime)tobehandled.Italsoincreases1 stationavailability,helpingtoaccommodateprecedencerelationships.Thesecondimposespositionalrequirementssothattasksthatrequireprocessingfromthefrontsideoftheproductcannotbeassignedtothesamestationthatprocessestasksthatrequireprocessingfromthebackside.Wesoughtouttheseactualvariationstoevaluatetherobustnessofoursolutionapproachinapplicationtoidiosyncrasiesfoundindifferentplants.Thepurposeofthispaperistoevaluateanewbranch-and-cutapproach,establishingacomputationalbenchmarkfortheSPASDproblem.Theapproachconsistsofaheuristic,preprocessingmethodsandtwotypesofcuts,includingthoseidentifiedbytheFacetGenerationProcedure(FGP)(cf.GadidovandWilhelm1997)andsomenewtypesthatarebasedontheparticularstructureofSPASDproblems.EventhoughresearchershavestudiedtheSPASDandrelatedALBproblemsextensivelyandhavedevelopedelegantsolutionmethods,itiswellknownthatthesemethodshavenotbeenwidelyusedinindustry.Weconjecturethatonereasonforthislackoftechnologytransferisthatpriorsolutionmethodsarespecializedtoaparticularmodelandcannotbeadaptedeasilytoaddressvariationsfoundineachdifferentplant.Thispaperdemonstratesthatourapproachissufficientlyrobustthat,withonlyminormodifications,itcanbeappliedsuccessfullytovariationsoftheSPASDproblem.Wehaveorganizedthebodyofthispaperinfivesections.Section2reviewsrelevantliterature,andsection3introducesourmathematicalformulations.Section4presentsthemaincomponentsofoursolutionapproach.Insection5,wediscussourcomputationalevaluation.Finally,weofferconclusionsandrecommendationsforfutureresearch.2.LiteratureReviewTheobjectiveofthe(TypeI)ALBproblemistominimizethenumberofidenticalstationsrequiredtoprocessasetoftasks,subjecttoconstraintsthatimposeafixedcycletimecandprecedencerelationshipsamongtasks(Baybars1986).ALBisanNP-hardproblem(Karp1972),butseveralspecializedbranch-and-boundalgorithmshavebeenshowntosolveselectedtestproblemseffectively;forexample,seeAsscheandHerroelen(1998),Johnson(1988),Hackman,MagazineandWee(1989),Ugurdag,PapachristouandRachmadugu(1997),andSchollandKlein(1997).DeReyckandHerroelen(1995)surveyedmodelformulationsandcomparedtwoeffectivealgorithms,EUREKA(Hoffman1992)andFABLE(Johnson1988).Scholl(1995)overviewedthetopic.2 RapidchangesinmanufacturingaroundtheworldhaveledresearcherstostudyextendedversionsoftheALBproblem.Inparticular,robotsandothertypesof“machines”mustnowbeprescribed,sothatstationsneednotbeidenticalasmanualstationstypicallyareinthetraditionalALBproblem.ExtendingALBtoprescribethetypeofmachineateachstationresultsintheSPASDproblem.ThemostappropriateobjectivefortheSPASDproblemistominimizetotalcost(e.g.,seeGravesandLamar(1983),GravesandRedfield(1988),andGhoshandGagnon(1989))sincetheSPASDdesignwiththeminimumnumberofstationsneednotminimizecost.Wilhelm(1999)devisedacolumn-generationapproachtotheSPASDproblem,specifyingassemblysequencetodealexplicitlywithtoolchanges,forexample,inroboticassembly.Kimms(1997)proposedacolumn-generationmethodtodesignaflowline.Heincorporatedoperationprecedencerelationshipsbutrequiredeachoperationtobeperformedbyaspecifiedtypeofmachineratherthanselectingonefromasetofalternativemachinetypesaswedo.Wefocusourreviewonthemostrelevantliterature,whichcomprisespapersthathaveappliedstrongcuttingplanemethodstoSPASDproblems.PinnoiandWilhelm(1998)devisedabranch-and-cutapproachfortheSPASDproblem,employingpreprocessingattherootnode.Theyshowedthatthenodepacking(NP)polytopeisarelaxationoftheALBpolytopeandgeneratedcutsbasedonthisrelationship.PinnoiandWilhelm(1997b)gaveaformulationoftheworkload-smoothingproblem,avariationoftheALBproblemthatminimizesthemaximumidletimeonanystation,“smoothing”theworkloadsassignedtoapredeterminednumberofstations.Theyproposedarelatedsolutionapproach,whichexploitstherelationshipbetweentheNPandALBpolytopes.KimandPark(1995)studiedtheSPASDproblemassociatedwithroboticlines,whichistoassigntasks,partsandtoolstoroboticcells(i.e.,stations)inordertominimizethetotalnumberofcellsactivated.Theyproposedabranch-and-boundalgorithm,includingpreprocessingandaddingmostviolatedcovercuts(cf.NemhauserandWolsey(1988))attherootnode.Finally,PinnoiandWilhelm(1997a)establishedafamilyofhierarchicalmodelsfortheSPASDProblem,discussingindetailavarietyofmodelsandrelationshipsbetweenthem.ThegenericSPASDmodelwestudyinthispaperisbasedonPinnoiandWilhelm(1997b),butwepresentseveralnewdevicestofacilitatesolution.WenowdetailourSPASDmodels.3.ModelFormulation3 InthissectionwepresentamathematicalformulationofthegenericSPASDproblemaswellastwovariationsthatrepresentactualindustrialcases.First,however,weintroducenotationthatiscommontoallthreemodels.Indices·m=machinetype(mÎM)·s=station(sÎS)·t=task(tÎT)Taskinformation·T=setoftasks(tÎT)·IPt=setofimmediatepredecessorstotaskt(t’ÎIPt)Machineinformation·M=setofmachinetypes(mÎM)·Mt=setofmachinestypesthatcanperformtaskt(mÎMt)·pmt=processingtimeoftasktonmachinetypem(tÎT,mÎMt)·Tm=setoftasksthatcanbeassignedtomachinetypem(mÎM)·vmt=variablecostofassigningtaskttomachinetypem(tÎT,mÎMt)·cm=fixedcostincurredifmachinetypemisprescribed(mÎM)Stationinformation·c=cycletime·S=setofstations·fs=fixedcostincurredifstationsisactivated(sÎS)WenowdescribethegenericSPASDproblem.3.1TheGenericSPASDFormulation.ThedecisionvariablesinthismodelareDecisionvariables·xmst=1iftasktisassignedtomachinetypematstations(sÎS,tÎT,mÎMt)·yms=1ifmachinetypemisassignedtostations(mÎM,sÎS)·zs=1ifstationsisactivated(sÎS).Wenowpresentourgeneric,SPASDmodel.Formulation4 ModelSPASDminz=åfszs+ååcmyms+åååvmtxmstsÎSsÎSmÎMsÎStÎTmÎMtsubjectto:(1)ååxmst=1tÎTmÎMtsÎS(2)ååsxmst'£ååsxmsttÎT,t'ÎIPtmÎMt'sÎSmÎMtsÎS(3)ååpmtxmst£czssÎStÎTmÎMt(4)xmst£ymssÎS,tÎT,mÎMt(5)yms£zsmÎM,sÎS(6)zs+1£zssÎS{|S|}(7)xmst,yms,zsÎ{0,1}sÎS,tÎT,mÎMt.Theobjectivefunctionminimizesthetotalcostofthesystemdesign,includingthefixedcostsofactivatingstationsandprescribingmachinesandthevariablecostofperformingtasks.Equalities(1)requirethateachtaskbeprocessed,andinequalities(2)invoketaskprecedencerelationships.Constraints(3)imposethecycletimelimitation,whileinequalities(4)assurethattasktisassignedtomachinetypematstationsonlyifamachineofthattypeislocatedatstations.Inequalities(5)areredundantfortheintegerprogram,butweincludedtheminordertostrengthenthelinearprogrammingrelaxation.Theyrequirestationstobeactivatedinordertoassignamachinetoit.Inequalities(6)requirestationstobeactivatedbeforestations+1canbeactivated.Weassumethatanunlimitednumberofmachinesofeachtypemmaybeprescribed.ThismodelissimilartotheonestudiedbyPinnoiandWilhelm(1998),butthereareimportantdifferences.Bothmodelsincorporateconstraints(1)and(2).ThePinnoiandWilhelmmodeldidnotincorporatezsdecisionvariablessothattheircycletimeconstraint(3)involvedcymsinsteadofczsandenumerated(3)overmÎMtinsteadofsummingThePinnoiandWilhelmmodelwasdesignedspecificallytoimbedtheALBpolytope(i.e.,thoughconstraints(1)-(3)),andtheylimitedthenumberofmachinesassignedtostationsusinginequality(4),åmyms£1.Incomparison,5 ourmodelincorporatesseveralfeaturestofacilitatesolution.First,westrengtheninequality(3)bysummingovermÎMt.Second,inequalities(4)-(6)aredisaggregatedformsthatareknowntostrengthenthelinearprogrammingrelaxation,makingboundsmorediscerning.Finally,inequality(6)improvestheformulationbyavoidingsymmetry.IfS0stationsareactivatedoutofthe|S|thatareæ|S|öavailable,thereareç÷waystomakeagivenassignmentofmachinetypesandtaskstothe|S|ç÷èS0østations.Ourmodelavoidsthissymmetry,sothatweneednotexploreallalternative-butequivalent-waysofmakingthesameassignmenttodifferentstations.Now,wedescribeavariationofthegenericSPASDproblemthatwasposedbyamanufacturerofassemblyworkstations.3.2ParallelMachines.Theapplicationinvolvedanassemblylineinwhichdeterminingthenumberofmachinesateachstationwasacrucialissueinthesystemdesign.Thus,weconsideravariationofthegenericSPASDprobleminwhichidenticalmachines(i.e.,machinesofthesametype)canbeusedinparallelateachstation.Weneedthefollowingadditionalnotationtodescribeeachstation:Stationinformation·ns=upperboundonthenumberofmachinesthatcanbeassignedtostations·cmns=fixedcostofassigningnmachinesoftypemtostationsThedecisionvariablesinthiscaseareDecisionvariables·xmst=1iftasktisassignedtomachinetypematstations(sÎS,tÎT,mÎMt)·ymns=1ifnmachinesoftypemareassignedtostations(sÎS,mÎM,n=1,…,ns).WenowpresentourSPASDPMmodel.FormulationofSPASDProblemwithParallelMachinesnsSPASDPMminz=åååcmnsymns+åååvmtxmstsÎSn=1mÎMsÎStÎTmÎMtsubjectto:(1),(2)andns(8)åpmtxmst£cånymnssÎS,mÎMtÎTmn=16 ns+1ns(9)ååymn(s+1)£ååymnssÎS{|S|}mÎMn=1mÎMn=1n1(10)ååymn1£1mÎMn=1(11)xmst,ymnsÎ{0,1}sÎS,tÎT,mÎMt.Theobjectiveisagaintominimizethetotalcostofsystemdesign.Newconstraints(8)statethattheavailability(i.e.,timecapacityduringeachcycle)ofastationisincreasedbyassigningmorethanonemachinetothatstation.Parallelmachinesallow“long”jobs(i.e.,thosewithpmt>c)tobehandledandalsoprovidealargercapacity,whichhelpstoaccommodateprecedencerelationships.Inequalities(9)replace(6),assuringthatstationsareactivatedconsecutively.Thenssequence{ååymns}sisnon-increasing,soconstraint(10)ensuresthatatmostonemachinetypemÎMn=1isassignedtoeachactivatedstation.Next,weintroduceavariationofthegenericSPASDproblemthatwasposedbyamanufacturerofassemblysystemsthataredesignedaroundanautomaticconveyortransport.3.3PositionRequirements.Thecompanysuppliestheconveyorandpalletsthatconveyworkpieces.Inaddition,thecompanydesignsworkstations,installsandteststhesystem,andprovidessystemsupport.Theapplicationinvolvedanassemblysysteminwhichtaskscanhavepositionalrequirements.Thatis,itmaybenecessarytoperformsometasksfromthefrontsideoftheproductandothertasksfromthebackside.Weassumethatastationcandoeither“front”or“back”tasksbutnotboth.Furthermore,weassumethatanunrestrictedtaskcanbedoneonanystation,whetheritisassigned“front”or“back”tasksornot.Intheapplicationthatmotivatedthiscase,amechanismcanbeinstalledtoriseautomaticallyfromundertheconveyortorotateaworkpiece,orientingitappropriately,dependingwhetherfrontorbacktasksareperformedatthenextstation.Thisallowsalloperationstobeperformedfromonesideoftheconveyor,facilitatingaccesstomachinesformaintenance.Theapplicationinvolvedprescribingasinglemachineateachstation.Weneedthefollowingadditionalnotationtodescribetasks.Taskinformation·TB=setofbacktasks7 ·TF=setoffronttasks·TU=setofunrestrictedtasks(TU=T(TBUTF)).ThedecisionvariablesinthiscaseareDecisionVariables·xmst=1iftasktisassignedtomachinetypematstationssÎS,tÎT,mÎMt·yms=1ifmachinetypemisassignedtostationssÎS,mÎMWenowpresentourSPASDPRmodel.FormulationoftheAssemblySystemDesignProblemwithPositioningRequirementsModelSPASDPRminz=ååcmsyms+åååvmtxmstsÎSmÎMsÎStÎTmÎMtsubjectto(1),(2)and:(12)åpmtxmst£cymsmÎM,sÎStÎTm(13)xmst+xmst'£1mÎM,sÎS,tÎTF,t'ÎTB(14)åym(s+1)£åymssÎSmÎMmÎM(15)åym1£1mÎM(16)xmst,ymsÎ{0,1}sÎS,tÎT,mÎMt.Inequalities(12)invokecycletimerestrictions,whilethenewconstraints(13)assurethatonecannotassignbothfrontandbacktaskstothesamestation.Constraints(14)and(15)replace(9)and(10),respectively,ensuringthatstationsareactivatedconsecutivelyandthatonlyonetypeofmachineislocatedateachstation.4.SolutionmethodThissectiondescribesourbranch-and-cutapproach.Itconsistsofaheuristicandpre-processingmethodsandtwotypesofcuttingplanes,thosegeneratedbytheFacetgenerationProcedureandothersbasedonmachinecapacities.8 4.1Heuristic.OurheuristicyieldsanupperboundforthevalueoftheoptimalsolutionoftheSPASDproblem.Itschedulesthetaskthatcanfitonastationandwillincurtheleastcost.Assumethat,atageneraliteration,wehavealreadyactivatedsstations.Tasktisacandidateforassignmentifitspredecessorshaveallbeenassigned.Wefindtheminimalcosttoassigneachcandidatetaskttoamachine,mÎMt,atstations.Ifnomoretaskscanbeassignedtostations(i.e.,theremainingcandidatetasksallhaveprocessingtimesgreaterthantheunusedcapacityofstations),weactivateanewstation.Otherwise,weassignthetaskincurringtheminimalcostandcontinue.Bykeepingtrackoftheunusedcapacity(cycletime)atastation,thisheuristicisabletoprescribe“tight”solutions.Forexample,considerthreetaskswithprecedencerelationship1®2®3.Eachtaskhasprocessingtime3,andthecycletimeis5.ThetraditionalmethodforcalculatingtheearlieststationtowhicheachtaskcanbeassignedyieldsE1=1,E2=ë(3+3)/5û=2andE3=ë(3+3+3)/5û=2.Ourheuristicassignstask1tostation1,leavingunusedcapacityof2,sothatitassignstask2tostation2.Similarly,task2leavescapacityof2atstation2,soourheuristicassignstask3tostation3.4.2Preprocessingmethods.Ourpreprocessingmethodsyieldaboundontheoptimalnumberofstationsaswellastheearliestandlateststationstowhicheachtaskmightbeassigned.Theseboundsallowedustofixsomevariablestozerotoreduceproblemsize.Wenowdefinethenotationweintroduceinthissection:zIP=theoptimumsolutionNs=optimalnumberofstations.WederiveourboundontheoptimalnumberofstationsbystartingwiththeobservationNs(17)åfk+Nsmin{cm;mÎM}+åmin{vmt;mÎMt}£zIP.k=1tThefirsttermin(17)representsthecosttoopenNsstations,thesecondtermrepresentsthelowestpossiblecostofpurchasingNsmachinesandthethirdtermrepresentsthelowestpossiblecostofproducingallthetasks.IfzIPHisanyheuristicsolution,thenzIP£zIPH,soNs(18)åfk+Nsmin{cm;mÎM}+åmin{vmt;tÎMt}£zIPH,k=1tor,equivalently,9 Ns(19)åfk+Nsmin{cm;mÎM}£zIPH-åmin{vmt;tÎMt}.k=1tAnupperboundforNscanbeobtainedeasilyfrom(19).GivenNs,wecandefineLt,thelateststationtowhichtasktcanbeassigned:êmin{pmt;mÎMt}+åmin{pm~t;mÎM~t}úê~t=successoroftúL=N-.tsêcúêëúûFinally,theearlieststationtowhichtasktcanbeassigned,Et,isgivenbyémin{pmt;mÎMt}+åmin{pm~t;mÎM~t}ùê~t=predecessoroftúEt=êú.cêúêúTheupperboundNsis,apparently,new,andourdefinitionsofEtandLtextendthoseusedinALBbyconsideringthedifferentprocessingtimesthatalternativemachinesinsetMtrequiretocompletetaskt.Wenowdescribetwotypesofcuttingplanesweusedtofacilitatesolution.4.3TheFacetGenerationProcedure(FGP).WegeneratedonetypeofcutsusingtheFGP.Gadidov,ParijaandWilhelm(1997)reportedfundamentaltechnicaldetailsoftheFGP.Sothatthispaperisself-contained,weaugmentthatearlierwork,providingabriefintuitivedescription.TheFGPdealswiththefollowingseparationproblem:givenafulldimensionalpolytopemÂinRandanm-dimensionalvectorf*suchthatf*ÏÂ,findahyperplaneHthatseparatesf*fromÂandrepresentsafacetofÂ.Underlyingassumptionsarethat0ÎÂandthatitispossibletoidentifyasetofmlinearlyindependentextremepointsofÂ,E1,suchthatf*belongstotheconvexconegeneratedbyE1.ColumnsxÎE1formtheinitialbasisforthelinearprogram(P):*Problem(P):z=min{åxÎextÂax|åxÎextÂaxx=f*,ax³0,xÎextÂ}inwhichextÂisthesetofextremepointsofÂ.Ateachiteration,anoraclesolvesasubproblemmaximizingalinearfunctionoverÂ,togeneratecolumnxÎextÂ.Thissteppricesoutnonbasiccolumnsfor(P).IftheLPoptimalitycriterionissatisfied,thecurrent**basis,B,isoptimal.Bconsistsofmlinearlyindependentvectors,xÎextÂ.WedeterminemT*HasthehyperplanethatsupportsthesempointsbyfindingvectornÎRthatsatisfiesnx=10 **mT1forallxÎB.nisthenormaltoH={xÎR:nx=1},whichseparatesf*fromÂandF=HÇÂrepresentsafacetofÂ.TherelationshipofHandFtoÂandf*iseasytointerpretgeometrically.Sincef*ÏÂandf*liesintheconegeneratedbytheextremepointsofÂ,theray0®f*intersectsoneofthefacetsofÂatthepoint(1/z*)f*,wherez*isthevalueoftheoptimalsolutionto(P).If(P)hasauniqueoptimalbasis,theray0®f*passesthroughexactlyonefacetofÂ;thisisthefacetthattheFGPidentifies.H.f*1f*z*.Â0Figure1Iftheray0®f*passesthroughafaceFofdimensionk(0£kcs1,thereisnotenoughmachinecapacitytoassigntaskt1tos1andtaskt2tos2,sos1(20)xm1s1t1+åxm2kt2£1k=s212 isavalidinequality.Thiscanbeimprovedbyliftingallthevariablesxmkt2,k=s2,…,s1,mÎMt.Theliftedversionof(20)is:2s1(21)åxms1t1+ååxmkt2£1.mÎMtk=s2mÎMt12Toderivecutsofthesecondtype,consideranodeintheBranchandCuttreeatwhichtaskt1isassignedtoamachineoftypem1,m1ÎMt,atstations1(i.e.,xmst=1).1111Moreover,assumethatpredecessort2oft1isassignedtoamachineoftypem2,m2ÎMt,at2stations2£s1(i.e.,xmst=1).Let222rs1=c-åpmtxms1t=1betheunusedcapacityofstations1,rs2=c-åpmtxms2t=1betheunusedcapacityofstations2,and~r=åmin{pmt;mÎMt}t=predecessoroft1t=successoroft2betheminimumtimetoprocessthetasksthataresuccessorsoft2andpredecessorsoft1.If~ìrs1+(s1-s2)rs2ifs2+1£s1r>íîrs1+rs2+(s1-s2)cotherwise,thereisnotenoughtimetoassignthetasksthataresuccessorsoft2andpredecessorsoft1,sowecanprunethenodebyaddingthevalidinequality(22)xmst+xmst£1.111222WenowdescribeourcomputationalexperiencewiththeSPASDproblem.5.ComputationalEvaluation.Toprovidebenchmarkingcomputationalexperience,weranasetoftestsonanIBMRISC6000model550usingthesupernoderoutineofOSLrelease3tomanagethecuttingplanesgeneratedbyourmethods.Weaddedtheviolatedcutsoftype(21)attherootnode,andkepttheothercutsinapoolandaddedthem(ifviolated)atothernodesinthebranch-and-cutsearchtreealongwithinequalitiesoftype(22)andcutsgeneratedbythe13 FGP.TosolvethegenericSPASDinstances,weappliedtheFGPtounderlyingknapsackpolytopes,eachdefinedbyaninequalityoftype(3).Similarly,weappliedittoinequalitiesoftype(8)tosolveSPASDPMinstancesandtoinequalitiesoftypes(12)and(13)tosolveSPASDPRinstances.Wemademinorbutstraightforwardadaptationsinourheuristicandpre-processingmethodstoaddressSPASDPMandSPASDPRproblems.5.1TestInstances.OurtestsoftheSPASDprobleminvolvedfourfactors:(1)numberoftasks(2)taskprecedencerelationships(3)cycletime(4)numberofmachinetypes.Wechosetwolevelsforthefirstfactor-20and30tasks–anddefinedthreelevelsforeachoftheotherfactors.Wegeneratedtaskprecedencerelationshipsbasedonan80-taskinstanceinArcus(1966),randomlydropping60or50tasks,respectively.Wejustifythisapproachbynotingthatotherresearcherscaneasilygeneratesimilarprecedencerelationshipstoconfirmourresults.Inaddition,theresultingnetworkshaveloworderstrengthandare,therefore,quitechallenging.The20-taskinstanceshaveorderstrengthsof12%-14%;and30-taskinstances,8%-9%,sothatprecedencerelationshipstodonotimposetightconstraintsandnumerouscombinationsmustbeevaluatedtoprescribeanoptimalassignmentoftaskstostations.Figures3-5depicttheresultingprecedencerelationshipsfor20-taskinstances;andFigures6-8,for30-taskinstances.Weemployedthesetaskprecedencerelationshipsintestsofallthreemodels(i.e.,SPASDP,SPASDPMandSPASDPR).Weselectedthreecycletimesc1,c2,c3(whichareindexedinincreasingorder)anddefinedthelargest(c3)astheoriginalcycletimeinArcus’80-taskinstance.Togeneratec1andc1and1fromuniformdistributionswithranges[0.6,0.75]2,wedrewrandomnumbersr1r211cand[0.75,0.95],respectively,andcomputedc1=r1c3andc2=r23.Finally,wedefinedthenumberofmachinestypes,|M|,tobe2,4or6.Wespecified2}thesetofalternativemachinesthatcanperformtasktbygeneratingrandomnumbers{rmmÎMfromtheuniformdistributionwithrange[0.0,1]andassigningmachinetypemtosetM2tifrm14 £0.6.IfthisprocessassignednomachinetypetosetMt,machinetypem=1wasassignedtoMtsothattasktcouldbeprocessed.Eachtestinstanceinvolvedonelevelofeachofthesefourfactors.Timeandresourcelimitationsprecludedusfromreplicatingeachtest.However,experimentsofthisdesignarecommonlyusedtoevaluatemathematicalprogrammingalgorithms.WederivedprocessingtimesfromArcus’80-taskinstance.Letpt,tÎT,betheprocessingtimesfortheselectedtasksfromArcus’80-taskinstance.Wedrewasetofrandom3}numbers{rmmÎMfromauniformdistributionwithrange[0.3,1]anddefinedtheprocessing3ptimepmtoftasktÎTmonmachinetypemÎMtaspmt=rmt.Wegeneratedthefixedcostofactivatingstations,fs,bydrawingrandomnumbers{fs}sÎSfromauniformdistributionwithrange[100,300].Wegeneratedthefixedcostof4}prescribingmachinetypem,cm,bydrawingrandomnumbers{rmmÎMfromtheuniformdistributionwithrange[0.3,1.0]andusingc4.Togeneratethevariablecostofm=2000/rm56}operations,vmt,wedrewrandomnumbers{rm}mÎMand{rttÎTfromuniformdistributionswithranges[0.3,1.0]and[800,1200],respectively,anddefinedv5r6.mt=rmtWeusedfactors(1),(2)and(4)ingenerating24SPASDPMtestinstances.Inthiscase,weallowedmorethanonemachine(allofthesametype,however)ateachstation.Sincecycletimeisnotarelevantissueinthiscase,weredefinedfactor(3)tobethemaximumnumberofmachinesallowedateachstationandchosetwolevels:4and6.Wegeneratedcostscmns,usingcmns=ncm+fsinwhichwegeneratedcmandfsasdescribedabove.Weusedfactors(1)-(4)ingenerating24SPASDPRtestinstances.AsinthegenericSPASDinstances,weallowedonlyonetypeofmachineateachstation.InthetaskprecedencediagramsofFigures3-8,Udenotesanunrestrictedtask,andB(F)indicatesthatataskmustbeperformedfromtheback(front)sideoftheassemblyline.ThistaskdesignationisrelevantonlytotheSPASDPRmodelandhasnomeaningfortheSPASDandSPASDPMmodels.Sinceallowingonlytwotypesofalternativemachinesforeachtaskisveryrestrictive,wedefinedonlytwolevelsforthenumberofalternativemachinetypes:4and6,respectively.15 Similarly,wealsochosetwolevelsforthecycletime:c2andc3,respectively.Wegeneratedfixedcosts,cms,usingcms=cm+fsinwhichwegeneratedcmandfsasdescribedabove.5.2TestResults.Tables1-6describeour102testinstances.Column1definesthefactorlevelsusedineachtest;thenotation,forexample,asdp1c1m2_30,representsaSPASDinstance,taskprecedencerelationshipsgivenindiagram1,cycletimec1,twotypesofalternativemachinesand30tasks.Columns2and3givethenumberofconstraintsandnumberofbinaryvariablesforeachinstance.Columns4,5and6givetheoptimalvaluesfortheinitialLPrelaxation,ZLP,theoptimalbinarysolution,ZBP,andthepercentgap[i.e.,100*(ZBP-ZLP)/ZBP],respectively.Themodelsarerelativelytight;80instanceshavegapslessthan10%andtheremaining22havegapslessthan16%.Relativelysmallgapsliketheseareofteninterpretedasreflectinga“good”model,thatis,onethatfacilitatessolutionbymakingboundsdiscerning.Tables7-12givetheresultsofourtests.Column"Cuts"liststhenumberofcutsgeneratedduringourBranch-and-Cutsearch,column"Nodes"givesthenumberofnodesrequiredtofindandverifyanoptimalsolution,andcolumn"CPU"givestheruntime(inseconds)forsolvingtheinstance.ThelasttwocolumnsofTables7-12demonstratetheresultsofusingonlyOSLtosolveeachinstance.Thesecolumnsreport“Nodes,”thenumberofnodesrequiredtofindandverifyanoptimalsolution,and“CPU,”theruntime(inseconds),respectively.TheOSLimplementationdidnotuseourheuristic,pre-processingmethodsorcuts,butitdidemploythesupernoderoutine.WesettimelimitsofonehourforOSLoninstancesthatourapproachsolvedinminutesandfivehoursforharderones.Ourbranch-and-cutapproachwasabletosolveall102instanceswithinthetimelimitsallotted.However,theOSLimplementationwasnotabletosolve54ofthese102testinstances(i.e.,53%)withinallottedlimits.Evenfortheinstancesthatweresolvedwithinthetimelimits,ourbranch-and-cutapproachwassignificantlyfaster.Inaddition,exceptforone30-taskSPASDPMinstance,ourapproachrequiredsubstantiallyfewernodestofindandconfirmanoptimalsolution.6.ConclusionsThispaperevaluatesanewbranch-and-cutapproach,establishingacomputationalbenchmarkforthesingle-productassemblysystemdesign(SPASD)problem.Thepaperstudiesthe16 genericSPASDproblemandtwovariationsthatarebasedonactualindustrialcases.Onevariationallowsparallel,identicalmachinestobelocatedateachstation,andthesecondimposespositionalrequirements,allowingeachstationtoprocesstasksthatmustbeaccomplishedfromthefrontsideorthebacksideoftheproductbutnotboth.Ourapproachconsistsofaheuristic,preprocessingmethodsandcutsthataregeneratedbytheFacetGenerationProcedure(FGP)(cf.GadidovandWilhelm1997)andbyafamilyofvalidinequalitiesthatarebasedontheparticularstructureofSPASDproblems.Thepaperestablishedcomputationalbenchmarksbytestingourapproachonasetof102instances.Thesupernoderoutine,whichallowsOSLtoconductabranch-and-cutsearch,managescutsinamannerthatispoorlydocumented.Forexample,weobservedthatsupernodemaydiscardcutsthatourmethodsidentifyafterleavingthenodeatwhichtheyaregenerated.Thesamecutmaybegeneratedagainatanothernode.Forthisreason,OSLdoesnotprovideareportthatgivesagoodmeasurethatmightbeusedtounderstandthecut-generationprocessatadetailedlevel.Theruntimetosolveaninstanceistheprimarymeasureofefficacy,andthenumberofnodesrequiredtofindandconfirmanoptimalsolutionisasecondarymeasure.Astestresultsindicate,ourmethodperformedparticularlywellincomparisontoOSL.Thelargenumberofcutsgeneratedinsolvingsomeoftheinstancesmaybeattributed–atleastinpart-tothesupernoderoutinediscardingcutsandgeneratingthemagainatothernodes.Thefourfactors((1)numberoftasks,(2)taskprecedencerelationships,(3)cycletime,and(4)numberofalternativemachinetypes)interactinacomplicatedwaytoinfluenceruntime;nosimplepatternofinteractionappearsevident.Testsshowthat,asexpected,run-timeincreasesrapidlywiththenumberoftasks.However,thiswasnottrueinthecaseofSPASDPMinstances.Thus,increasingstationcapacitiesfacilitatedsolution.Themodelswererelativelytight;thegap(i.e.,thepercentdifferencebetweentheoptimalvaluesoftheinitialLPrelaxationandtheoptimalintegersolution)waslessthan10%formostinstancesandlessthan16%forallinstances.However,manytestinstanceswerechallenging,showingonemoretimethat,ingeneral,thegapisnotnecessarilyagoodmeasureofamodel.Gadidov,ParijaandWilhelm(1997)appliedtheFGPtothe16binaryinstancesinMIPLIB.Thegapsfortheseinstancesrangesfrom0%toover96%andaverages19.5%.TheFGPsolved12oftheseinstancesinlessthan230seconds;theremainingfourrequired660,17 770,4404and9623seconds.OSLrequiredsignificantlymoretimetosolveeachinstance.TheseMIPLIBproblemshavebeenconsideredparticularlychallenging,butitappearsthattheSPASDproblemsaremoreso.OurexperienceconfirmstheimportanceofevaluatingasolutionapproachspecificallyonSPASDinstances,whichareparticularlychallenging.Theassemblylinebalancing(ALB)problemiscloselyrelatedtotheSPASDproblem(e.g.,considerconstraints(1)-(3)).Specializedbranch-and-boundalgorithms(e.g.,Johnson(1988),Hoffman(1992),andSchollandKlein(1997))havebeenshowntobequiteeffectiveinsolvingtheALBproblem,especiallyiftheoptimalnumberofstationsisthesame,oronelargerthan,thetheoreticalminimalnumberofstations.Testshavedescribedtheeffectsoffactorssuchascycletime,numberoftasks,precedencerelationships(i.e.,orderstrength),andprocessingtimes(i.e.,ratioofmaximumprocessingtimetominimum).ThesesamefactorsaffecttheassignmentoftasksintheSPASDproblem.However,theSPASDPproblemmustalsodealwiththecombinatorialfeatureofselectingfromalternativemachinetypesthatcanperformeachtaskandassigningonemachinetypetoeachstation.ThisadditionalfeaturemakestheSPASDproblemsubstantiallymorechallenging.Wehopethattheseresultswillencourageapplicationofoursolutionapproachinindustry.ResultsshowthatitprovidesameansofsolvingavarietyofSPASDproblems.ApromisingdirectionforfutureresearchwouldbetoinvestigateextensionsthatwouldextendoursolutionapproachtoASDproblemsthatinvolvemultipleproductsandotherissuesrelatedtoflexibleassembly(atopicofwideinteresttoindustry)byexploitingthespecialstructuresembeddedinproblemsofthattype.Ourcontinuingresearchisfocusedinthisdirection.AcknowledgementsThismaterialisbaseduponworksupportedbytheNationalScienceFoundationonGrantsDDM-9114396andDMI-9500211.7.ReferencesArcus,A.L.,1966,COMSOAL:AComputerMethodofSequencingOperationsforAssemblyLines,inReadingsinProductionandOperationsManagement,JohnWiley&Sons,NewYork.Assche,F.V.,andHerroelen,W.S.,1998,AnOptimalProcedurefortheSingleModelDeterministicAssemblyLineBalancingProblems,EuropeanJournalofOperationalResearch,3,142-149.Baybars,I.,1986,AsurveyofExactAlgorithmsfortheAssemblyLineBalancingProblem,ManagementScience,32,909-932.18 DeReyck,B.,and,Herroelen,W.,1995,AssemblyLineBalancingbyResource-ConstrainedProjectScheduledTechniques:ACriticalAppraisal,WorkingPaper.Gadidov,R.,Parija,G.,and,Wilhelm,W.,1997,AFacetGenerationProcedureforsolving0/1integerprograms,toappearinOperationsResearch.Ghosh,S.,and,Gagnon,R.J.,1989,AComprehensiveLiteratureReviewandAnalysisoftheDesign,BalancingandSchedulingofAssemblySystems,InternationalJournalofProductionResearch,27,637-670.Graves,S.C.,andB.W.Lamar.1983.AnIntegerProgrammingProcedureforAssemblySystemDesignProblems.Opns.Res.31,522-545.Graves,S.C.,andC.H.Redfield.1988.EquipmentSelectionandTaskAssignmentforMultiproductAssemblySystemDesign.Int.J.Flex.Manu.Sys.1,31-50.Hackman,S.T.,Magazine,M.J.,and,Wee,T.S.,1989,Fast,EffectiveAlgorithmsforSimpleAssemblyLineBalancingProblem,OperationsResearch,6,916-924.Hoffman,T.R.,1992,Eureka:AHybridSystemforAssemblyLineBalancing,ManagementScience,38,39-47.Johnson,R.V.,1988,OptimallyBalancingLargeAssemblyLineswith‘Fable’,ManagementScience,34,240-253.Karp,R.M.,1972,ReducibilityAmongCombinatorialProblems,inComplexityofComputerApplications,R.E.MillerandJ.W.Thatcher(eds.),Plenum,NewYork,85-104.Kim,H.,and,Park,S.,1995,AStrongCuttingPlaneMethodfortheRoboticAssemblyLineBalancingProblem,InternationalJournalofProductionResearch,33,2311-2323.Kimms,A.,1998,MinimalInvestmentBudgetsforFlowLineConfiguration,WorkingPaper470,LehrstuhlfürProduktionundLogistik,InstitutfürBetriebswirtschaftslehre,Christian-AlbrechtsUniversitätzuKiel,Kiel,Germany.Nemhauser,G.L.,and,Wolsey,G.L.,1988,Integerandcombinatorialoptimization,JohnWiley&Sons,NewYork.Pinnoi,A.,and,Wilhelm,W.,1997a,AFamilyofHierarchicalModelsfortheAssemblySystemDesign,InternationalJournalofProductionResearch,35,253-280.Pinnoi,A.,and,Wilhelm,W.,1997b,ABranch-and-CutApproachforWorkloadSmoothingonAssemblyLines,ORSAJournalofComputing,9,335-350.19 Pinnoi,A.,and,Wilhelm,W.,1998,AssemblySystemDesign:ABranch-and-CutApproach,ManagementScience,44,103-118.Scholl,A.,1995,BalancingandSequencingofAssemblyLines,PhysicaVerlag,Heidelberg,Germany.Scholl,A.,andR.Klein,1997,SALOME:ABidirectionalBranch-and-BoundProcedureforAssemblyLinebalancing,INFORMSJournalonComputing,9(4).Ugurdag,H.F.,Papachristou,C.A.,and,Rachamadugu,R.,1997,DesigningPacedAssemblyLineswithFixedNumberofStations,EuropeanJournalofOperationalResearch,102,488-501.Wilhelm,W.E.,1999,AColumnGenerationApproachfortheAssemblySystemDesignProblemwithToolChanges,InternationalJournalofFlexibleManufacturingSystems,Vol.11,No.2,1999,forthcoming.20 Table1:20-task,SPASDtestinstancesProblemRowsVariablesZLPZBPGap(%)asdp1c1m2_2071064338220.5444553.7114.21asdp1c1m4_2088081238609.4243614.4311.48asdp1c1m6_20104097837888.3642726.6011.32asdp1c2m2_2074567839689.5041534.404.44asdp1c2m4_2087981637099.1241358.0210.30asdp1c2m6_201198108936815.8840164.758.34asdp1c3m2_2068562140792.0544523.038.38asdp1c3m4_2087981640631.1443343.316.26asdp1c3m6_201257113440031.4542323.015.41asdp2c1m2_2069662837945.6043991.3113.74asdp2c1m4_2087881240592.1245025.219.85asdp2c1m6_201094103139634.4543925.699.77asdp2c2m2_2071264938392.9841410.117.29asdp2c2m4_2088381741306.4942269.532.28asdp2c2m6_201261117840298.2941211.682.22asdp2c3m2_2067961237945.6041450.118.46asdp2c3m4_2092886339066.6443081.949.32asdp2c3m6_201191112438811.2142102.057.82asdp3c1m2_2072065436392.3443953.9217.20asdp3c1m4_2092286040893.4246103.6511.30asdp3c1m6_201165109839864.0646677.1614.60asdp3c2m2_2067061838229.8239559.303.36asdp3c2m4_2088682441410.2843995.125.86asdp3c2m6_201198113039259.1341968.356.46asdp3c3m2_2073267135093.1840424.1813.19asdp3c3m4_2092986740138.6743953.928.68asdp3c3m6_201246118539560.7141296.334.2021 Table2:30-task,SPASDtestinstancesProblemRowsVariablesZLPZBPGap(%)asdp1c1m2_301575146653222.4957839.007.98asdp1c1m4_301555165552391.7156812.337.78asdp1c1m6_302078197951653.4355033.466.14asdp1c2m2_301569147052596.5857020.977.76asdp1c2m4_301770167154152.8456192.153.63asdp1c2m6_302160206147652.3252293.958.88asdp1c3m2_301611150152099.9054390.974.21asdp1c3m4_301878167953946.7356231.574.06asdp1c3m6_302181208250935.4153585.624.95asdp2c1m2_301614152349910.3555438.129.97asdp2c1m4_301795169848271.3353891.3110.43asdp2c1m6_301962186647190.4552612.4410.31asdp2c2m2_301606150050925.9854556.086.65asdp2c2m4_301904180848975.2652954.557.51asdp2c2m6_302094199847390.5452331.669.44asdp2c3m2_301526142751380.5453256.983.52asdp2c3m4_301827169950922.8852431.762.88asdp2c3m6_302110201450988.0653927.595.45asdp3c1m2_301679158448763.6653828.539.41asdp3c1m4_301786169148492.9254814.1811.53asdp3c1m6_301946185149420.3758413.5315.40asdp3c2m2_301545144048413.9052075.627.03asdp3c2m4_301889179449555.9351978.354.66asdp3c2m6_302081198647838.5951668.757.41asdp3c3m2_301614151849892.8253156.986.14asdp3c3m4_301817172251052.8555466.307.96asdp3c3m6_301953200950774.7754388.256.6422 Table3:20-task,SPASDPMtestinstancesProblemRowsVariablesZLPZBPGap(%)asdpmp1m4n4_2014392038747.2642356.538.52asdpmp1m4n6_20143105637614.7341512.769.39asdpmp1m6n4_20183116437306.9641175.169.39asdpmp1m6n6_20183125236704.9240440.139.24asdpmp2m4n4_2014691138127.3741386.807.88asdpmp2m4n6_20146105636713.5540445.319.23asdpmp2m6n4_2018690538607.1741091.896.05asdpmp2m6n6_20186102436697.6539013.475.94asdpmp3m4n4_2014399438484.4641949.078.26asdpmp3m4n6_20143107735820.8340017.4810.5asdpmp3m6n4_20183108138489.4640571.905.13asdpmp3m6n6_20183112536757.4040008.048.12Table4:30-task,SPASDPMtestinstancesProblemRowsVariablesZLPZBPGap(%)asdpmp1m4n4_30190187348344.1053429.419.52asdpmp1m4n6_30190200247548.7852398.959.26asdpmp1m6n4_30240218047586.4551745.918.04asdpmp1m6n6_30240240646124.7851205.349.92asdpmp2m4n4_30190184747108.3052382.8310.07asdpmp2m4n6_30190196346220.6150753.808.94asdpmp2m6n4_30240214247435.5151739.068.32asdpmp2m6n6_30240237846195.0050313.438.19asdpmp3m4n4_30195179747910.9050403.854.95asdpmp3m4n6_30195191847263.2149201.733.94asdpmp3m6n4_30245217548059.8650037.443.95asdpmp3m6n6_30245241946009.4349780.867.5823 Table5:20-task,SPASDPRtestinstancesProblemRowsVariablesZLPZBPGap(%)asdprp1c1m4_2094578940640.0344242.458.14asdprp1c3m4_2097881138112.2943008.5011.38asdprp1c1m6_201183102038706.3642596.989.13asdprp1c3m6_201562108837435.0042477.0011.87asdprp2c1m4_2084174142171.2445557.337.43asdprp2c3m4_2090279538422.1245122.0414.85asdprp2c1m6_20116898239215.8043651.6110.16asdprp2c3m6_201178101038614.5144067.0712.37asdprp3c1m4_2087567543959.9748183.868.77asdprp3c3m4_2090679344636.5148332.747.65asdprp3c1m6_201207101142642.2647509.4710.24asdprp3c3m6_201200101642086.9446412.009.32Table6:30-task,SPASDPRtestinstancesProblemRowsVariablesZLPZBPGap(%)asdprp1c1m4_302372162554337.7558652.317.36asdprp1c3m4_302148164255181.4157755.114.46asdprp1c1m6_302442197953211.5156694.226.14asdprp1c3m6_302382190853151.2055163.893.65asdprp2c1m4_302180164952800.1056091.425.87asdprp2c3m4_302310169552383.4954801.314.41asdprp2c1m6_302529198852447.1055243.455.06asdprp2c3m6_302467200752534.4957150.618.08asdprp3c1m4_302228161553594.0160194.9710.97asdprp3c3m4_302255173754853.2359763.868.22asdprp3c1m6_302381201254796.9459852.558.45asdprp3c3m6_302688209653017.9759298.5410.5924 Table7:Testresultsfor20-task,SPASDinstancesBranchandCutOSLProblem**CutsNodesCPUNodesCPUasdp1c1m2_2073419984881455asdp1c1m4_20382551214826233519asdp1c1m6_2071516721792618asdp1c2m2_2025511565107214233asdp1c2m4_20649825792342934asdp1c2m6_20214133415717443544asdp1c3m2_205709878308020334123asdp1c3m4_206448378419023241asdp1c3m6_201055103675****asdp2c1m2_2055797831353****asdp2c1m4_2021029054789621113344asdp2c1m6_2016171706367613400asdp2c2m2_201556167578****asdp2c2m4_209171173591882727asdp2c2m6_2013561904719662596asdp2c3m2_2081885189****asdp2c3m4_20372311244333021asdp2c3m6_2027552138****asdp3c1m2_20672212691527****asdp3c1m4_2014215811351139889899asdp3c1m6_201752133975****asdp3c2m2_20383291762443122asdp3c2m4_2020731231198****asdp3c2m6_20583584581522030asdp3c3m2_20833107389****asdp3c3m4_20103912691527****asdp3c3m6_20157131213982689*Alltimesareinseconds**TimeorMemoryoverlimit25 Table8:Testresultsfor30-task,SPASDinstancesBranchandCutOSLProblem**CutsNodesCPUNodesCPUasdp1c1m2_3092075344151****asdp1c1m4_308435321523389713421asdp1c1m6_3071142246416****asdp1c2m2_30685229772332455asdp1c2m4_301065923991543122asdp1c2m6_309381383364****asdp1c3m2_3021671989474783467asdp1c3m4_3011256112211408****asdp1c3m6_3014282822187134414578asdp2c1m2_3034564233211****asdp2c1m4_3045532578****asdp2c1m6_3084563567245****asdp2c2m2_30434912913095325789asdp2c2m4_301801540983212asdp2c2m6_3023510252916729****asdp2c3m2_30103275101323423asdp2c3m4_3016341513716142819asdp2c3m6_3033443663336****asdp3c1m2_3048091982837147813967asdp3c1m4_3016707283811541****asdp3c1m6_3031571944580****asdp3c2m2_30308117214688377361asdp3c2m4_3047464682842****asdp3c2m6_30535552215508****asdp3c3m2_3022142882132189asdp3c3m4_3028831433706****asdp3c3m6_3019533078054134916283*Alltimesareinseconds**TimeorMemoryoverlimit26 Table9:Testresultsfor20-task,SPASDPMinstancesBranchandCutOSLProblem**CutsNodesCPUNodesCPUasdpmp1m4n4_2041020307543214asdpmp1m4n6_2010693191385****asdpmp1m6n4_2095526794****asdpmp1m6n6_2042912270****asdpmp2m4n4_2010278481431422asdpmp2m4n6_20405731785****asdpmp2m6n4_2011812148642490asdpmp2m6n6_2022124291****asdpmp3m4n4_2051411159542600asdpmp3m4n6_201072411414****asdpmp3m6n4_2084725332431327asdpmp3m6n6_2050036336****Table10:Testresultsfor30-task,SPASDPMinstancesBranchandCutOSLProblem**CutsNodesCPUNodesCPUasdpmp1m4n4_3033742441943****asdpmp1m4n6_3084714314911204321asdpmp1m6n4_30569921830583115411asdpmp1m6n6_3028904123415448****asdpmp2m4n4_301574833710841****asdpmp2m4n6_30305111633152557988asdpmp2m6n4_303220782548****asdpmp2m6n6_305856226****asdpmp3m4n4_302914382893217asdpmp3m4n6_302709423513****asdpmp3m6n4_304376407561467asdpmp3m6n6_3050971075851*****Alltimesareinseconds**TimeorMemoryoverlimit27 Table11:Testresultsfor20-task,SPASDPRinstancesBranchandCutOSLProblem**CutsNodesCPUNodesCPUasdprp1c1m4_209363291279592513915asdprp1c3m4_20114953214317****asdprp1c1m6_2079802433304****asdprp1c3m6_2059553093742****asdprp2c1m4_2054502202848****asdprp2c3m4_2014877412161983612asdprp2c1m6_2078252623757****asdprp2c3m6_201264682013****asdprp3c1m4_20883338171083092asdprp3c3m4_2053916493892590asdprp3c1m6_2021306334074818041asdprp3c3m6_2074122194071****Table12:Testresultsfor30-task,SPASDPRinstancesBranchandCutOSLProblem**CutsNodesCPUNodesCPUasdprp1c1m4_302416351814166****asdprp1c3m4_303108673954****asdprp1c1m6_302193613465****asdprp1c3m6_3046317989613122asdprp2c1m4_302191362113814****asdprp2c3m4_302861883109****asdprp2c1m6_302813046212083****asdprp2c3m6_302545678213014****asdprp3c1m4_30181263319635****asdprp3c3m4_305141617121124277asdprp3c1m6_301026241822613014asdprp3c3m6_3034206137414261*****Alltimesareinseconds**TimeorMemoryoverlimit28 Precedencediagram1for20-tasktestproblems:1U*2F*4U3B*5U8F10B6F9F17B7F11U18B12F13U14U15B16B19U20UFigure3*U=unrestrictedtaskB=backtaskF=fronttask29 Precedencediagram2for20-tasktestproblems:1U2B5B4U3B12U8F9F6F7F13B11U10F14B15B16F17U18U19U20UFigure430 Precedencediagram3for20-tasktestproblems:1U2B5B6F7F11U3B8F12U4B9F13B10F14B15U16F17U18U19U20UFigure531 Precedencediagram1for30-tasktestproblems:1U2U3B6B4B9U7U8U5B17F13F15B10F12U18F14F16B11F19F25B20F26B21U27U22U23U24U28U29UFigure630U32 Precedencediagram2for30-tasktestproblems:1U3F4B2B6F24U22B19F5B7F25B23F20B8U21B9F26B10U11F12F13U14U15U16U17U18U27U28U29U30UFigure733 Precedencediagram3for30-tasktestproblems:1U5U2F4B6F3F7U9U8B12F24F11B10B26F25U14U13F15B16B17U18B19U20B21U22U23U27F28U29U30UFigure834
