




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
SpatialschedulingforlargeassemblyblocksinshipbuildingAbstract:Thispaperaddressesthespatialschedulingproblem(SPP)forlargeassemblyblocks,whicharisesinashipyardassemblyshop。Thespatialschedulingproblemistoscheduleasetofjobs,ofwhicheachrequiresitsphysicalspaceinarestrictedspace。Thisproblemiscomplicatedbecauseboththeschedulingofassemblieswithdifferentduedatesandearlieststartingtimesandthespatialallocationofblockswithdifferentsizesandloadsmustbeconsideredsimultaneously。Thisproblemunderconsiderationaimstotheminimizationofboththemakespanandtheloadbalanceandincludesvariousreal-worldconstraints,whichincludesthepossibledirectionalrotationofblocks,theexistenceofsymmetricblocks,andtheassignmentofsomeblockstodesignatedworkplacesorworkteams.Theproblemisformulatedasamixedintegerprogramming(MIP)modelandsolvedbyacommerciallyavailablesolver.Atwo-stageheuristicalgorithmhasbeendevelopedtousedispatchingpriorityrulesandadiagonalfillspaceallocationmethod,whichisamodificationofbottom-left-fillspaceallocationmethod。ThecomparisonandcomputationalresultsshowstheproposedMIPmodelaccommodatesvariousconstraintsandtheproposedheuristicalgorithmsolvesthespatialschedulingproblemseffectivelyandefficiently。Keywords:Largeassemblyblock;Spatialscheduling;Loadbalancing;Makespan;Shipbuilding1.IntroductionShipbuildingisacomplexproductionprocesscharacterizedbyheavyandlargeparts,variousequipment,skilledprofessionals,prolongedleadtime,andheterogeneousresourcerequirements.Theshipbuildingprocessisdividedintosubprocessesintheshipyard,includingshipdesign,cuttingandbendingoperations,blockassembly,outfitting,painting,pre-erectionanderection。Theassemblyblocksarecalledtheminorassemblyblock,thesubassemblyblock,andthelargeassemblyblockaccordingtotheirsizeandprogressesinthecourseofassemblyprocesses。Thispaperfocusesonthespatialschedulingproblemoflargeassemblyblocksinassemblyshops。torecognizethattherearevariousspatialschedulingproblemsineveryaspectofshipbuildingduetothelimitedspace,facilities,equipment,laborandtime。TheSPPsoccurinvariousworkingareassuchascuttingandblastshops,assemblyshops,outfittingshops,pre—erectionyard,anddrydocks。TheSPPatdifferentareashasdifferentrequirementsandconstraintstocharacterizetheuniqueSPPs.Inaddition,thedepletionofenergyresourcesonlandputmoreemphasisontheoceandevelopment。Theshipbuildingindustriesfacethetransitionoffocusfromthetraditionalshipbuildingtooceanplantmanufacturing.Therefore,thediversityofassemblyblocks,materials,facilitiesandoperationsinshipyardsincreasesrapidly。TherearesomesolutionproviderssuchasSiemens™andDassultSystems™toprovideintegratedsoftwareincludingproductlifemanagement,enterpriseresourceplanningsystem,simulationandetc。Theyindicatedtheneedsofefficientalgorithmstosolvemedium-tolarge-sizedSPPproblemsin20
min,sothattheshopcanquicklyre-optimizetheproductionplanuponthefrequentandunexpectedchangesinshopfloorswiththeongoingoperationsonexitingblocksintact。Therearemanydifferentapplicationswhichrequireefficientschedulingalgorithmswithvariousconstraintsandcharacteristics(HYPERLINK”/science/article/pii/S0360835215002296"Kimetal。,2013,b9015"NguyenandYun,2014
and
HYPERLINK”/science/article/pii/S0360835215002296"\l”b9020"Yanetal.,2014)。However,thespatialschedulingproblemwhichconsidersspatiallayoutanddynamicjobschedulinghasnotbeenstudiedextensively.Untilnow,spatialschedulinghastobecarriedoutbyhumanschedulersonlywiththeirexperiencesandhistoricaldata。Evenwhenhumanexpertshavemuchexperienceinspatialscheduling,ittakesalongtimeandintensiveefforttoproduceasatisfactoryschedule,duetothecomplexityofconsideringblocks’geometricshapes,loads,requiredfacilities,etc。Inpractice,spatialschedulingformorethanasix—monthperiodisbeyondthehumanschedulers’capacity.Moreover,thespaceintheworkingareastendstobethemostcriticalresourceinshipbuilding。Therefore,theeffectivemanagementofspatialresourcesthroughautomationofthespatialschedulingprocessisacriticalissueintheimprovementofproductivityinshipbuildingplants.Ashipyardassemblyshopisconsistedofpinnedworkplaces,equipment,andoverhangcranes。Duetotheheavyweightoflargeassemblyblock,overhangcranesareusedtoaccessanyareasoverotherobjectswithoutanyhindranceintheassemblyshop。Theheightofcranescanlimittheheightofblocksthatcanbeassembledintheshop。Theshopcanbeconsideredasatwo—dimensionalspace。Theblocksareplacedonpreciselypinnedworkplaces。Oncetheblockisallocatedtoacertainareainaworkplace,itisdesirablenottomovetheblockagaintodifferentlocationsduetothesizeandweightofthelargeassemblyblocks.Therefore,itisimportanttoallocatetheworkspacetoeachblockcarefully,sothattheworkspaceinanassemblyshopcanbeutilizedinamostefficientway。Inaddition,sinceeachblockhasitsduedatewhichispre—determinedatthestageofshipdesign,thetardinessofablockassemblycanleadtoseveredelayinthefollowingoperations。Therefore,inthespatialschedulingproblemforlargeassemblyblocks,theschedulingofassemblyprocessesforblocksandtheallocationofblockstospecificlocationsinworkplacesmustbeconsideredatthesametime.Astheterminologysuggests,spatialschedulingpursuestheoptimalspatiallayoutandthedynamicschedulewhichcanalsosatisfytraditionalschedulingconstraintssimultaneously。Inaddition,therearemanyconstraintsorrequirementswhichareseriousconcernsonshopfloorsandthesecomplicatetheSPP。Theconstraintsorrequirementsthisstudyconsideredareexplainedhere:(1)Blockscanbeputineitherdirections,horizontalorvertical。(2)Sincetheshipissymmetricaroundthecenterline,thereexistsymmetricblocks.Thesesymmetricblocksarerequiredtobeputnexttoeachotheronthesameworkplace。(3)Someblocksarerequiredtobeputonacertainspecialareaoftheworkplace,becausetheworkteamsonthatareahasspecialequipmentorskillstoachieveacertainlevelofqualityorcompletethenecessarytasks。(4)Frequently,theproductionplanmaynotbeimplementedasplanned,sothatfrequentmodificationsinproductionplansarerequiredtocopewiththechangesintheshop。Atthesemodifications,itisrequiredtoproduceanewmodifiedproductionplanwhichdoesnotremoveormovethepre—existingblocksintheworkplacetocompletetheongoingoperations.(5)Ifpossibleatanytime,theloadbalancingovertheworkteams,i。e.,workplacesaredesirableinordertokeepalltaskassignmentstoworkteamsfairanduniform。Lee,Lee,andChoi(1996)studiedaspatialschedulingthatconsidersnotonlytraditionalschedulingconstraintslikeresourcecapacityandduedates,butalsodynamicspatiallayoutoftheobjects.Theyusedtwo—dimensionalarrangementalgorithmdevelopedbyHYPERLINK”http:///science/article/pii/S0360835215002296”Lozano-Perez(1983)todeterminethespatiallayoutofblocksinshipbuilding。HYPERLINK”/science/article/pii/S0360835215002296”Koh,Eom,andJang(2008)extendedtheirpreciousworks(Kohetal。,1999)byproposingthelargestcontactareapolicytoselectabetterallocationofblocks。\l”b0015”Cho,Chung,Park,Park,andKim(2001)proposedaspatialschedulingsystemforblockpaintingprocessinshipbuilding,includingblockscheduling,fourarrangementalgorithmsandblockassignmentalgorithm。Parketal.(2002)extendedShin,Kwon,andRyu(2008)proposedabottom—left-fillheuristicmethodforspatialplanningofblockassembliesandsuggestedaplacementalgorithmforblocksbydifferentialevolutionarrangementalgorithm.b0050”Liu,Chua,andWee(2011)proposedasimulationmodelwhichenabledmultiplepriorityrulestobecompared。HYPERLINK”http:///science/article/pii/S0360835215002296"\l”b0080”Zheng,Jiang,andChen(2012)proposedamathematicalprogrammingmodelforspatialschedulingandusedseveralheuristicspatialschedulingstrategies(gridsearchingandgeneticalgorithm)。b0075”ZhangandChen(2012)proposedanothermathematicalprogrammingmodelandproposedtheagglomerationalgorithm.Thisstudypresentsanovelmixedintegerprogramming(MIP)formulationtoconsiderblockrotations,symmetricalblocks,pre-existingblocks,loadbalancingandallocationofcertainblockstopre—determinedworkspace.TheproposedMIPmodelswereimplementedbycommerciallyavailablesoftware,LINGO®andproblemsofvarioussizesaretested.ThecomputationalresultsshowthattheMIPmodelisextremelydifficulttosolveasthesizeofproblemsgrows。Toefficientlysolvetheproblem,atwo—stageheuristicalgorithmhasbeenproposed。Section2describesspatialschedulingproblemsandassumptionswhichareusedinthisstudy。Section3presentsamixedintegerprogrammingformulation.InSections0035"5。TheconclusionsaregiveninSections0040”6。2.ProblemdescriptionsTheshipdesigndecideshowtodividetheshipintomanysmallerpieces.Themetalsheetsarecut,blast,bendandweldtobuildsmallblocks。Thesesmallblocksareassembledtobiggerassemblyblocks.Duringthisshipbuildingprocess,allblockshavetheirearlieststartingtimeswhicharedeterminedfromthepreviousoperationalstepandduedateswhicharerequiredbythenextoperationalstep.Ateachstep,theblockshavetheirownshapesofvarioussizesandhandlingrequirements.Duringtheassembly,noblockcanoverlapphysicallywithothersoroverhangtheboundaryofworkplace.Thespatialschedulingproblemcanbedefinedasaproblemtodeterminetheoptimalscheduleofagivensetofblocksandthelayoutofworkplacesbydesignatingtheblocks’workplacesimultaneously。Asthetermimplies,spatialschedulingpursuestheoptimaldynamicspatiallayoutschedulewhichcanalsosatisfytraditionalschedulingconstraints.Dynamicspatiallayoutschedulecanbeincludingthespatialallocationissue,temporalallocationissueandresourceallocationissue.AnexampleofspatialschedulingisgiveninHYPERLINK”/science/article/pii/S0360835215002296"\l”f0010”Fig.2。Thereare4blockstobeallocatedandscheduledinarectangularworkplace。Eachblockisshadedindifferentpatterns。HYPERLINK”http:///science/article/pii/S0360835215002296”\l”f0010"Fig。2showsthe6—dayspatialscheduleoffourlargeblocksonagivenworkplace。Blocks1and2arepre—existedorallocatedatday1.Theearlieststartingtimesofblocks3and4aredays2and4,respectively.Theprocessingtimesofblocks1,2and3are4,2and4
days,respectively。Thespatialschedulemustsatisfythetimeandspaceconstraintsatthesametime.Therearemanyobjectivesinspatialscheduling,includingtheminimizationofmakespan,theminimumtardiness,themaximumutilizationofspatialandnon-spatialresourcesandetc.Theobjectiveinthisstudyistominimizethemakespanandbalancetheworkloadovertheworkspaces。Therearemanyconstraintsforspatialschedulingproblemsinshipbuilding,dependingonthetypesofshipsbuilt,theoperationalstrategiesoftheshop,organizationalrestrictionsandetc.Somebasicconstraintsaregivenasfollows;(1)allblocksmustbeallocatedongivenworkplacesforassemblyprocessesandmustnotoversteptheboundaryoftheworkplace;(2)anyblockcannotoverlapwithotherblocks;(3)allblockshavetheirownearlieststartingtimeandduedates;(4)symmetricalblocksneedstobeplacedside-by—sideinthesameworkspace.\l”f0015"Fig。3showshowsymmetricalblocksneedtobeassigned;(5)someblocksneedtobeplacedinthedesignatedworkspace;(6)therecanbeexistingblocksbeforetheplanninghorizon;(7)workloadsforworkplacesneedstobebalancedasmuchaspossible。Inadditiontotheconstraintsdescribedabove,thefollowingassumptionsaremade。(1)Theshapeofblocksandworkplacesisrectangular。(2)Onceablockisplacedinaworkplace,itcannotbemovedorremovedfromitslocationuntiltheprocessiscompleted.(3)Blockscanberotatedatanglesof0°and90°(see\l”f0020"Fig.4)。(4)Thesymmetricblockshavethesamesizes,arerotatedatthesameangleandshouldbeplacedside-by-sideonthesameworkplace。(5)Thenon—spatialresources(suchaspersonnelorequipment)areadequate。3。AmixedintegerprogrammingmodelAMIPmodelisformulatedandgiveninthissection.Theobjectivefunctionistominimizemakespanandthesumofdeviationfromaverageworkloadperworkplace,consideringtheblockrotation,thesymmetricalblocks,pre—existingblocks,loadbalancingandtheallocationofcertainblockstopre—determinedworkspace。AworkspacewiththelengthLENWandthewidthWIDWisconsideredtwo-dimensionalrectangularspace.Sincetherectangularshapesfortheblockshavebeenassumed,ablockcanbeplacedonworkspacebydetermining(x,y)coordinates,where0
⩽
x
⩽
LENWand0
⩽
y
⩽
WIDW。Hence,thedynamiclayoutofblocksonworkplacesissimilartotwo-dimensionalbinpackingproblem。Inadditiontotheblockallocation,theoptimalscheduleneedstobeconsideredatthesametimeinspatialschedulingproblems。Zaxisisintroducedtodescribethetimedimension.Then,spatialschedulingproblembecomesathree—dimensionalbinpackingproblemwithvariousobjectivesandconstraints。Thedecisionvariablesofspatialschedulingproblemare(x,y,z)coordinatesofallblockswithinathree—dimensionalspacewhosesizesareLENW,WIDWandTinx,yandzaxes,whereTrepresentstheplanninghorizon.Thisspaceisillustratedinf0025”Fig。5。Inf0030”Fig。6,thespatialschedulingoftwoblocksintoaworkplaceisillustratedasanexample。Theparametersp1andp2indicatetheprocessingtimesforBlocks1and2,respectively.Asshowninzaxis,Block2isscheduledafterBlock1iscompleted。4。Atwo-stageheuristicalgorithmThecomputationalexperimentsfortheMIPmodelinSection\l”s0015”3havebeenconductedusingacommerciallyavailablesolver,LINGO®.Obtainingglobaloptimumsolutionsisverytimeconsuming,consideringthenumberofvariablesandconstraints。Ashipisconsistedofmorethan8hundredlargeblocksandthesizeofproblemusingMIPmodelisbeyondtoday’scomputationalability.Atwo-stageheuristicalgorithmhasbeenproposedusingthedispatchingpriorityrulesandadiagonalfillmethod。4.1。Stage1:LoadbalancingandsequencingPastresearchonspatialschedulingproblemsconsidersvariouspriorityrules。\l”b0045”Leeetal.(1996)usedapriorityrulefortheminimumslacktimeofblocks.HYPERLINK”/science/article/pii/S0360835215002296"\l”b0015”Choetal.(2001)andParketal.(2002)usedtheearliestduedate.HYPERLINK”/science/article/pii/S0360835215002296”Fig。7.Thefirststepofthealgorithminthisstageistogrouptheblocksbasedontheurgencypriority.Theurgencypriorityiscalculatedbysubtractingtheearlieststartingtimeandtheprocessingtimefromtheduedateforeachblock。Thesmallertheurgencypriority,themoreurgenttheblockneedstobedscheduled。Thenallblocksaregroupedintoanappropriatenumberofgroupsforareasonablenumberoflevelsinurgencypriorities.Letgbethisdiscretionarynumberofgroups。Thereareggroupsofblocksbasedontheurgencyofblocks.Thenumberofblocksineachgroupdoesnotneedtobeidentical.Blocksineachgrouparere—orderedgroupedintoasmanysubgroupsasworkplaces,consideringtheworkloadofblockssuchastheweightorweldinglength。Theblocksineachsubgrouphavethesimilarurgencyandworkloads。Then,theseblocksineachsubgroupareorderedinanascendingorderoftheearlieststartingtime.Thisorderingwillbeusedtoblockallocationsinsequence。Thesubgroupcorrespondstotheworkplace。Ifblockimustbeprocessedatworkplacewandiscurrentlyallocatedtootherworkplaceorsubgroupthanw,blockiisswappedwithablockatthesamepositionofblockiinanascendingorderoftheearlieststartingtimeatitsworkplace(orsubgroup)。Sincethesymmetricblocksmustbelocatedonasameworkplace,asimilarswappingmethodcanbeused。Oneofsymmetricblockswhichareallocatedintodifferentworkplace(orsubgroups)needstobeselectedfirst。Inthisstudy,weselectedoneofsymmetricblockswhicheverhasshownupearlierinanascendingorderoftheearlieststartingtimeattheircorrespondingworkplace(orsubgroup).Then,theselectedblockisswappedwithablockatthesamepositionofsymmetricblocksinanascendingorderoftheearlieststartingtimeatitsworkplace(orsubgroups).4。2。Stage2:SpatialallocationOncetheblocksinaworkplace(orsubgroup)aresequentiallyorderedindifferenturgencyprioritygroups,eachblockcanbeassignedtoworkplacesonebyone,andallocatedtoaspecificlocationonaworkplace。Therehasbeenpreviousresearchonheuristicplacementmethods.Thebottom—left(BL)placementmethodwasproposedbyHYPERLINK”http:///science/article/pii/S0360835215002296"\l”b0005”Baker,Coffman,andRivest(1980)andplacesrectanglessequentiallyinabottom—leftmostposition。HYPERLINK”http:///science/article/pii/S0360835215002296”\l”b0030”Jakobs(1996)usedabottom—leftmethodthatiscombinedwithahybridgeneticalgorithm(see\l”f0040”Fig。8).HYPERLINK”http:///science/article/pii/S0360835215002296"\l”b0055”LiuandTeng(1999)developedanextendedbottom-leftheuristicwhichgivesprioritytodownwardmovement,wheretherectanglesisonlyslideleftwardsifnodownwardmovementispossible.b0010"Chazele(1983)proposedthebottom-left—fill(BLF)method,whichsearchesforlowestbottom-leftpoint,holesatthelowestbottom-leftpointandthenplacetherectanglesequentiallyinthatbottom—leftposition.Iftherectangleisnotoverlapped,therectangleisplacedandthepointlistisupdatedtoindicatenewplacementpositions.Iftherectangleisoverlapped,thenextpointinthepointlistisselecteduntiltherectanglecanbeplacedwithoutanyoverlap.HYPERLINK”/science/article/pii/S0360835215002296"\l”b0025”HopperandTurton(2000)madeacomparisonbetweentheBLandBLFmethods。TheyconcludedthattheBLFmethodalgorithmachievesbetterassignmentpatternsthantheBLmethodforHopper’sexampleproblems.Spatialallocationinshipbuildingisdifferentfromtwo-dimensionalpackingproblem.Blockshaveirregularpolygonalshapesinthespatialallocationandblockscontinuouslyappearanddisappearsincetheyhavetheirprocessingtimes。ThisfrequentplacementandremovalofblocksmakesBLFmethodlesseffectiveinspatialallocationoflargeassemblyblock。Inordertosolvethesedrawbacks,wehavemodifiedtheBLFmethodappropriatetospatialschedulingforlargeassemblyblocks.Inaworkplace,sincetheblocksareplacedandremovedcontinuously,itismoreefficienttoconsiderboththebottom—leftandtop—rightpointsofplacedblocksinsteadofbottom-leftpointsonly.Wedenoteitasdiagonalfillplacement(seeHYPERLINK”/science/article/pii/S0360835215002296”Fig。9)。Sincethenumberofpotentialplacementconsiderationsincreases,ittakesabitmoretimetoimplementdiagonalfillbutthecomputationalresultsshowsthatitisnegligible.ThediagonalfillmethodshowsbetterperformancesthantheBLFmethodinspatialschedulingproblems.WhentheBLFmethodisusedinspatialallocation,thealgorithmmakestheallocationofsomeblocksdelayeduntiltheinterferencebypre—positionedblocksareremoved.Itgeneratesalesseffectiveandlessefficientspatialschedule.Theproposeddiagonalfillplacementmethodresolvethisdelaysbetterbyallocatingtheblocksassoonaspossibleinagreedyway,asshowninHYPERLINK”http:///science/article/pii/S0360835215002296"Fig。10。Thepotentialdrawbacksfromthegreedyapproachesisresolvedbyanotherplacementstrategytominimizethepossibledeadspaces,whichwillbeexplainedinthefollowingparagraphs。TheBLFmethodonlyfocusedontwo-dimensionalbinpacking.Frequentremovalandplacementofblocksinaworkspacemayleadtoaccumulationofdeadspaces,whicharesmallandunusablespacesamongblocks.Aminimalpossible—deadspacestrategyhasbeenusedalongwiththeBLFmethod.Possible—deadspacesarebeinggeneratedoverthespatialschedulingandtheyhavelesschancetobeallocatedforfutureblocks。Theminimalpossible—deadspacestrategyminimizesthepotentialdeadspaceafterallocatingthefollowingblocks(HYPERLINK”/science/article/pii/S0360835215002296”\l”b0020”Chung,2001
and
Kohetal。,2008)byconsideringthe0°and90°rotationoftheblockandallocatingthefollowingblockforminimalpossible-deadspace.Fig.11。Consideringtherotationoftheschedulingblocksandtheplacementconsiderationpointsfromthediagonalfillplacementmethods,theschedulingblockswillbefinallyallocated。Inthistwo—stagealgorithm,blockstendtobeplacedadjacenttooneofthealternativeedgesandtheirassignmentsaredonepreferentiallytominimizefracturedspaces。5.ComputationalresultsTodemonstratetheeffectivenessandefficiencyoftheproposedMIPformulationandheuristicalgorithm,theactualdataabout800+largeassemblyblocksfromoneofmajorshipbuildingcompanieshasbeenobtainedandused。Alltestproblemsaregeneratedfromthisreal-worlddata.AllcomputationalexperimentshavebeencarriedoutonapersonalcomputerwithaIntel®Core™i3—2100CPU@3。10
GHzwith2
GBRAM.TheMIPmodelinSection\l”s0015”3hasbeenprogrammedandsolvedusingLINGO®version10。0,acommerciallyavailablesoftwarewhichcansolvelinearandnonlinearmodels.Theproposedtwo—stageheuristicalgorithmhasbeenprogrammedinJAVAprogramminglanguage。Becauseourcomputationaleffortstoobtaintheoptimalsolutionsforevensmallproblemsaremorethansignificant,thecomplexityofSPPcanberecognizedasoneofmostdifficultandtimeconsumingproblems.DependingonthescalingfactorαinobjectivefunctionoftheproposedMIPformulation,theperformanceoftheMIPmodelvariessignificantly.Settingαlessthan0.01makestheloadbalancingcapabilitytobeignoredfromtheoptimalsolutionintheMIPmodel。Forcomputationalexperimentsinthisstudy,theresultswiththescalingfactorsetto0。01isshownanddiscussed。Thevalueneedstobefine-turnedtoobtainthedesirableoutcomes。HYPERLINK”/science/article/pii/S0360835215002296"\l”t0005"Table1showsacomparisonofcomputationalresultsandperformancebetweentheMIPmodelsandtwo-stageheuristicalgorithm。AsshowninTable1,theproposedtwo—stageheuristicalgorithmfindsthenear-optimalsolutionsformediumandlargeproblemsveryquicklywhiletheoptimalMIPmodelswasnotabletosolvetheproblemsofmediumorlargesizesduetothememoryshortageoncomputers。ItisobservedthatthecomputationaltimesfortheMIPproblemsarerapidlygrowingastheproblemsizesincreases.ThetestproblemsinHYPERLINK”http:///science/article/pii/S0360835215002296”a38255。00030。7400。21850––53.7600.719100––133.7802。948200––328。86012。523300––416.06040.154400––532。36073.214Bestfeasiblesolutionafter10
hinGlobalSolverofLINGO®.\o"Full—sizetable—Opensnewwindow"Full-sizetableHYPERLINK”/science/article/pii/S0360835215002296”Tableoptions\l”t0005"\o"Viewinworkspace”ViewinworkspaceHYPERLINK”/science/article/pii/S0360835215002296"\o”DownloadasCSV”DownloadasCSVTheoptimalsolutionsfortestproblemswithmorethan50blocksinHYPERLINK”/science/article/pii/S0360835215002296”\l”t0005"Table1havebeennotobtainedevenafter24
h.Thebestknownfeasiblesolutionsafter10
hforthetestproblemswith20blocksand30blocksarereportedinHYPERLINK”http:///science/article/pii/S0360835215002296”\l”t0005"Table1.ItisobservedthattheLINGO®doesnotsolvethenonlinearconstraintsverywellasshowninHYPERLINK”http:///science/article/pii/S0360835215002296"\l”t0005”Table1。Forverysmallproblemwith10blocks,theLINGO®wasabletoachievetheoptimalsolutions。Forslightlybiggerproblems,theLINGO®tooksignificantlymoretimetofindfeasiblesolutions.Fromthisobservation,theapproachestoobtainthelowerboundthroughtherelaxationmethodandupperboundsaresignificantrequiredinfutureresearch.Incontrary,theproposedtwo—stageheuristicalgorithmwasabletofindthegoodsolutionsveryquickly。Forthesmallesttestproblemwith10blocks,itwasabletofindtheoptimalsolutionaswell.Thecomputationaltimesare1014and0.026s,respectively,fortheMIPapproachandtheproposedalgorithm.Interestingly,theproposedheuristicalgorithmfoundsignificantlybettersolutionsinonly0。078and0。218
s,respectively,forthetestproblemswith20and30blocks。Forthesetwoproblems,theLINGO®generatestheworsesolutionsthantheheuristicsafter10
hofcomputationaltimes。Thesymbol‘–’inHYPERLINK”/science/article/pii/S0360835215002296"\l”f0060”Fig.12showspartialsolutionsoftestproblemswith20and30blockson2workplaces.ThepurposeofHYPERLINK”/science/article/pii/S0360835215002296”Fig.12istoshowtheprogressofproductionplanninggeneratedbythetwo—stageheuristicalgorithm。Twoworkplacesareindifferentsizesof(40,30)and(35,40),respectively.6。ConclusionsAsglobalwarmingisexpectedtoopenanewwaytotransportamongcontinentthroughNorthPoleSeaandtoexpeditetheoceansmoreaggressively,theneedsformoreshipsandoceanplantsareforthcoming。Theshipbuildingindustriescurrentlyfaceincreaseddiversityofassemblyblocksinlimitedproductionshipyard.Spatialschedulingforlargeassemblyblocksholdsthekeyroleinsuccessfuloperationsoftheshipbuildingcompanies.Thetaskofspatialschedulingtakesplaceatalmosteverystageofshipbuildingprocessesandthelargeassemblyshopisoneofthemostcongestedoperationalareasintoday'sshipbuilding。Itisalsoknownthatthespatialschedulingproblemhasbeenthemajorsourceofthebottleneck。Thepractitionersinshipbuildingindustriesrequirestheir
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年度高端电子产品市场产品价格保密协议
- 2025版建筑行业专业工匠用工合作协议合同
- 二零二五年度网络直播平台第三方打赏担保协议
- 2025年户外遮阳窗帘安装及维护保养合同
- 二零二五年度温泉度假村洗浴区承包合同协议
- 二零二五年酒店集团厨师长人才引进合同
- 2025年度新品发布临时促销员服务合同
- 2025版智能监控设备销售与定制安装合同
- 二零二五年度白灰行业市场调研购销合同模板
- 二零二五版人工智能技术研发指导服务协议
- 拔尖创新人才培养的评价与反馈机制
- 艺术类高中课程走班方案
- 【排放清单】省市县行业温室气体排放清单报告模板
- 《篮球裁判法及规则》课件
- 中国普通食物营养成分表(修正版)
- 隧道工程施工劳务分包合同
- Excel常用函数公式及技巧
- 学校心理健康教育合作协议书
- 2024-2030年中国军用滑环行业市场发展趋势与前景展望战略分析报告
- 部编版高中语文必修上第六单元任务群教学设计
- 线上线下教学衔接北师大版数学三年级下册口算脱式计算、应用题复习、期中、期末检测试卷(含部分答案解析)
评论
0/150
提交评论