船舶專業(yè)外文文獻

1、SpatialschedulingforlargeassemblyblocksinshipbuildingAbstract:Thispaperaddressesthespatialschedulingproblem(SPP)forlargeassemblyblocks,whicharisesinashipyardassemblyshop.Thespatialschedulingproblemistoscheduleasetofjobs,ofwhicheachrequiresitsphysicalspaceinarestrictedspace.Thisproblemiscomplicatedbe

2、causeboththeschedulingofassemblieswithdifferentduedatesandearlieststartingtimesandthespatialallocationofblockswithdifferentsizesandloadsmustbeconsideredsimultaneously.Thisproblemunderconsiderationaimstotheminimizationofboththemakespanandtheloadbalanceandincludesvariousreal-worldconstraints,whichincl

3、udesthepossibledirectionalrotationofblocks,theexistenceofsymmetricblocks,andtheassignmentofsomeblockstodesignatedworkplacesorworkteams.Theproblemisformulatedasamixedintegerprogramming(MIP)modelandsolvedbyacommerciallyavailablesolver.Atwo-stageheuristicalgorithmhasbeendevelopedtousedispatchingpriorit

4、yrulesandadiagonalfillspaceallocationmethod,whichisamodificationofbottom-left-fillspaceallocationmethod.ThecomparisonandcomputationalresultsshowstheproposedMIPmodelaccommodatesvariousconstraintsandtheproposedheuristicalgorithmsolvesthespatialschedulingproblemseffectivelyandefficiently.Keywords:Large

5、assemblyblock;Spatialscheduling;Loadbalancing;Makespan;Shipbuilding1.IntroductionShipbuildingisacomplexproductionprocesscharacterizedbyheavyandlargeparts,variousequipment,skilledprofessionals,prolongedleadtime,andheterogeneousresourcerequirements.Theshipbuildingprocessisdividedintosubprocessesinthes

6、hipyard,includingshipdesign,cuttingandbendingoperations,blockassembly,outfitting,painting,pre-erectionanderection.Theassemblyblocksarecalledtheminorassemblyblock,thesubassemblyblock,andthelargeassemblyblockaccordingtotheirsizeandprogressesinthecourseofassemblyprocesses.Thispaperfocusesonthespatialsc

7、hedulingproblemoflargeassemblyblocksinassemblyshops.Fig.1showsasnapshotoflargeassemblyblocksinashipyardassemblyshop.Recently,theresearchersandpractitionersatacademiaandshipbuildingindustriesrecentlygottogetherat“SmartProductionTechnologyForuminShipbuildingandOceanPlantIndustries”torecognizethatthvar

8、iousspatialschedulingproblemsineveryaspectofshipbuildingduetothelimitedspace,facilities,equipment,laborandtime.TheSPPsoccurinvariousworkingareassuchascuttingandblastshops,assemblyshops,outfittingshops,pre-erectionyard,anddrydocks.TheSPPatdifferentareashasdifferentrequirementsandconstraintstocharacte

9、rizetheuniqueSPPs.Inaddition,thedepletionofenergyresourcesonlandputmoreemphasisontheoceandevelopment.Theshipbuildingindustriesfacethetransitionoffocusfromthetraditionalshipbuildingtooceanplantmanufacturing.Therefore,thediversityofassemblyblocks,materials,facilitiesandoperationsinshipyardsincreasesra

10、pidly.TherearesomesolutionproviderssuchasSiemens?andDassultSystems?toprovideintegratedsoftwareincludingproductlifemanagement,enterpriseresourceplanningsystem,simulationandetc.Theyindicatedtheneedsofefficientalgorithmstosolvemedium-tolarge-sizedSPPproblemsin20min,sothattheshopcanquicklyre-optimizethe

11、productionplanuponthefrequentandunexpectedchangesinshopfloorswiththeongoingoperationsonexitingblocksintact.Therearemanydifferentapplicationswhichrequireefficientschedulingalgorithmswithvariousconstraintsandcharacteristics(KimandMoon,2003,Kimetal.,2013,NguyenandYun,2014andYanetal.,2014).However,thesp

12、atialschedulingproblemwhichconsidersspatiallayoutanddynamicjobschedulinghasnotbeenstudiedextensively.Untilnow,spatialschedulinghastobecarriedoutbyhumanschedulersonlywiththeirexperiencesandhistoricaldata.Evenwhenhumanexpertshavemuchexperienceinspatialscheduling,ittakesalongtimeandintensiveefforttopro

13、duceasatisfactoryschedule,duetothecomplexityofconsideringblocksgeometricshapes,loads,requiredfacilities,etc.Inpractice,spatialschedulingformorethanasix-monthperiodisbeyondthehumanschedulerscapacity.Moreover,thespaceintheworkingareastendstobethemostcriticalresourceinshipbuilding.Therefore,theeffectiv

14、emanagementofspatialresourcesthroughautomationofthespatialschedulingprocessisacriticalissueintheimprovementofproductivityinshipbuildingplants.Ashipyardassemblyshopisconsistedofpinnedworkplaces,equipment,andoverhangcranes.Duetotheheavyweightoflargeassemblyblock,overhangcranesareusedtoaccessanyareasov

15、erotherobjectswithoutanyhindranceintheassemblyshop.Theheightofcranescanlimittheheightofblocksthatcanbeassembledintheshop.Theshopcanbeconsideredasatwo-dimensionalspace.Theblocksareplacedonpreciselypinnedworkplaces.Oncetheblockisallocatedtoacertainareainaworkplace,itisdesirablenottomovetheblockagainto

16、differentlocationsduetothesizeandweightofthelargeassemblyblocks.Therefore,itisimportanttoallocatetheworkspacetoeachblockcarefully,sothattheworkspaceinanassemblyshopcanbeutilizedinamostefficientway.Inaddition,sinceeachblockhasitsduedatewhichispre-determinedatthestageofshipdesign,thetardinessofablocka

17、ssemblycanleadtoseveredelayinthefollowingoperations.Therefore,inthespatialschedulingproblemforlargeassemblyblocks,theschedulingofassemblyprocessesforblocksandtheallocationofblockstospecificlocationsinworkplacesmustbeconsideredatthesametime.Astheterminologysuggests,spatialschedulingpursuestheoptimals

18、patiallayoutandthedynamicschedulewhichcanalsosatisfytraditionalschedulingconstraintssimultaneously.Inaddition,therearemanyconstraintsorrequirementswhichareseriousconcernsonshopfloorsandthesecomplicatetheSPP.Theconstraintsorrequirementsthisstudyconsideredareexplainedhere:(1)Blockscanbeputineitherdire

19、ctions,horizontalorvertical.(2)Sincetheshipissymmetricaroundthecenterline,thereexistsymmetricblocks.Thesesymmetricblocksarerequiredtobeputnexttoeachotheronthesameworkplace.(3)Someblocksarerequiredtobeputonacertainspecialareaoftheworkplace,becausetheworkteamsonthatareahasspecialequipmentorskillstoach

20、ieveacertainlevelofqualityorcompletethenecessarytasks.(4)Frequently,theproductionplanmaynotbeimplementedasplanned,sothatfrequentmodificationsinproductionplansarerequiredtocopewiththechangesintheshop.Atthesemodifications,itisrequiredtoproduceanewmodifiedproductionplanwhichdoesnotremoveormovethepre-ex

21、istingblocksintheworkplacetocompletetheongoingoperations.(5)Ifpossibleatanytime,theloadbalancingovertheworkteams,i.e.,workplacesaredesirableinordertokeepalltaskassignmentstoworkteamsfairanduniform.Lee,Lee,andChoi(1996)studiedaspatialschedulingthatconsidersnotonlytraditionalschedulingconstraintsliker

22、esourcecapacityandduedates,butalsodynamicspatiallayoutoftheobjects.Theyusedtwo-dimensionalarrangementalgorithmdevelopedbyLozano-Perez(1983)todeterminethespatiallayoutofblocksinshipbuilding.Koh,Park,Choi,andJoo(1999)developedablockassemblyschedulingsystemforashipbuildingcompany.Theyproposedatwo-phase

23、approachthatincludesaschedulingphaseandaspatiallayoutphase.Koh,Eom,andJang(2008)extendedtheirpreciousworks(Kohetal.,1999)byproposingthelargestcontactareapolicytoselectabetterallocationofblocks.Cho,Chung,Park,Park,andKim(2001)proposedaspatialschedulingsystemforblockpaintingprocessinshipbuilding,inclu

24、dingblockscheduling,fourarrangementalgorithmsandblockassignmentalgorithm.Parketal.(2002)extendedChoetal.(2001)utilizingstrategysimulationintwoconsecutiveoperationsofblastingandpainting.Shin,Kwon,andRyu(2008)proposedabottom-left-fillheuristicmethodforspatialplanningofblockassembliesandsuggestedaplace

25、mentalgorithmforblocksbydifferentialevolutionarrangementalgorithm.Liu,Chua,andWee(2011)proposedasimulationmodelwhichenabledmultiplepriorityrulestobecompared.Zheng,Jiang,andChen(2012)proposedamathematicalprogrammingmodelforspatialschedulingandusedseveralheuristicspatialschedulingstrategies(gridsearch

26、ingandgeneticalgorithm).ZhangandChen(2012)proposedanothermathematicalprogrammingmodelandproposedtheagglomerationalgorithm.Thisstudypresentsanovelmixedintegerprogramming(MIP)formulationtoconsiderblockrotations,symmetricalblocks,pre-existingblocks,loadbalancingandallocationofcertainblockstopre-determi

27、nedworkspace.TheproposedMIPmodelswereimplementedbycommerciallyavailablesoftware,LINGO?andproblemsofvarioussizesaretested.ThecomputationalresultsshowthattheMIPmodelisextremelydifficulttosolveasthesizeofproblemsgrows.Toefficientlysolvetheproblem,atwo-stageheuristicalgorithmhasbeenproposed.Section2desc

28、ribesspatialschedulingproblemsandassumptionswhichareusedinthisstudy.Section3presentsamixedintegerprogrammingformulation.InSection4,atwo-stageheuristicalgorithmhasbeenproposed,includingblockdispatchingpriorityrulesandadiagonalfillspaceallocationheuristicmethod,whichismodifiedfromthebottom-left-fillsp

29、aceallocationmethodputationalresultsareprovidedinSection5.TheconclusionsaregiveninSection6.2.ProblemdescriptionsTheshipdesigndecideshowtodividetheshipintomanysmallerpieces.Themetalsheetsarecut,blast,bendandweldtobuildsmallblocks.Thesesmallblocksareassembledtobiggerassemblyblocks.Duringthisshipbuildi

30、ngprocess,allblockshavetheirearlieststartingtimeswhicharedeterminedfromthepreviousoperationalstepandduedateswhicharerequiredbythenextoperationalstep.Ateachstep,theblockshavetheirownshapesofvarioussizesandhandlingrequirements.Duringtheassembly,noblockcanoverlapphysicallywithothersoroverhangtheboundar

31、yofworkplace.Thespatialschedulingproblemcanbedefinedasaproblemtodeterminetheoptimalscheduleofagivensetofblocksandthelayoutofworkplacesbydesignatingtheblocksworkplacesimultaneously.Asthetermimplies,spatialschedulingpursuestheoptimaldynamicspatiallayoutschedulewhichcanalsosatisfytraditionalschedulingc

32、onstraints.Dynamicspatiallayoutschedulecanbeincludingthespatialallocationissue,temporalallocationissueandresourceallocationissue.AnexampleofspatialschedulingisgiveninFig.2.Thereare4blockstobeallocatedandscheduledinarectangularworkplace.Eachblockisshadedindifferentpatterns.Fig.2showsthe6-dayspatialsc

33、heduleoffourlargeblocksonagivenworkplace.Blocks1and2arepre-existedorallocatedatday1.Theearlieststartingtimesofblocks3and4aredays2and4,respectively.Theprocessingtimesofblocks1,2and3are4,2and4days,respectively.Thespatialschedulemustsatisfythetimeandspaceconstraintsatthesametime.Therearemanyobjectivesi

34、nspatialscheduling,includingtheminimizationofmakespan,theminimumtardiness,themaximumutilizationofspatialandnon-spatialresourcesandetc.Theobjectiveinthisstudyistominimizethemakespanandbalancetheworkloadovertheworkspaces.Therearemanyconstraintsforspatialschedulingproblemsinshipbuilding,dependingonthet

35、ypesofshipsbuilt,theoperationalstrategiesoftheshop,organizationalrestrictionsandetc.Somebasicconstraintsaregivenasfollows;(1)allblocksmustbeallocatedongivenworkplacesforassemblyprocessesandmustnotoversteptheboundaryoftheworkplace;(2)anyblockcannotoverlapwithotherblocks;(3)allblockshavetheirownearlie

36、ststartingtimeandduedates;(4)symmetricalblocksneedstobeplacedside-by-sideinthesameworkspace.Fig.3showshowsymmetricalblocksneedtobeassigned;(5)someblocksneedtobeplacedinthedesignatedworkspace;(6)therecanbeexistingblocksbeforetheplanninghorizon;(7)workloadsforworkplacesneedstobebalancedasmuchaspossibl

37、e.Inadditiontotheconstraintsdescribedabove,thefollowingassumptionsaremade.(1)Theshapeofblocksandworkplacesisrectangular.(2)Onceablockisplacedinaworkplace,itcannotbemovedorremovedfromitslocationuntiltheprocessiscompleted.(3)Blockscanberotatedatanglesof0and90(seeFig.4).(4)Thesymmetricblockshavethesame

38、sizes,arerotatedatthesameangleandshouldbeplacedside-by-sideonthesameworkplace.(5)Thenon-spatialresources(suchaspersonnelorequipment)areadequate.3.AmixedintegerprogrammingmodelAMIPmodelisformulatedandgiveninthissection.Theobjectivefunctionistominimizemakespanandthesumofdeviationfromaverageworkloadper

39、workplace,consideringtheblockrotation,thesymmetricalblocks,pre-existingblocks,loadbalancingandtheallocationofcertainblockstopre-determinedworkspace.AworkspacewiththelengthLENWandthewidthWIDWisconsideredtwo-dimensionalrectangularspace.Sincetherectangularshapesfortheblockshavebeenassumed,ablockcanbepl

40、acedonworkspacebydetermining(x,y)coordinates,where0?x?LENWand0?y?WIDW.Hence,thedynamiclayoutofblocksonworkplacesissimilartotwo-dimensionalbinpackingproblem.Inadditiontotheblockallocation,theoptimalscheduleneedstobeconsideredatthesametimeinspatialschedulingproblems.Zaxisisintroducedtodescribethetimed

41、imension.Then,spatialschedulingproblembecomesathree-dimensionalbinpackingproblemwithvariousobjectivesandconstraints.Thedecisionvariablesofspatialschedulingproblemare(x,y,z)coordinatesofallblockswithinathree-dimensionalspacewhosesizesareLENW,WIDWandTinx,yandzaxes,whereTrepresentstheplanninghorizon.Th

42、isspaceisillustratedinFig.5.InFig.6,thespatialschedulingoftwoblocksintoaworkplaceisillustratedasanexample.Theparametersp1andp2indicatetheprocessingtimesforBlocks1and2,respectively.Asshowninzaxis,Block2isscheduledafterBlock1iscompleted.4.Atwo-stageheuristicalgorithmThecomputationalexperimentsfortheMI

43、PmodelinSection3havebeenconductedusingacommerciallyavailablesolver,LINGO?.Obtainingglobaloptimumsolutionsisverytimeconsuming,consideringthenumberofvariablesandconstraints.Ashipisconsistedofmorethan8hundredlargeblocksandthesizeofproblemusingMIPmodelisbeyondtodayscomputationalabili-tsyt.aAgetwhoeurist

44、icalgorithmhasbeenproposedusingthedispatchingpriorityrulesandadiagonalfillmethod.4.1.Stage1:LoadbalancingandsequencingPastresearchonspatialschedulingproblemsconsidersvariouspriorityrules.Leeetal.(1996)usedapriorityrulefortheminimumslacktimeofblocks.Choetal.(2001)andParketal.(2002)usedtheearliestdued

45、ate.Shinetal.(2008)consideredthreedispatchingpriorityrulesforstartdate,finishdateandgeometriccharacteristics(length,breadth,andarea)ofblocks.LiuandTeng(1999)compared9differentdispatchingpriorityrulesincludingfirst-comefirst-serve,shortestprocessingtime,leastslack,earliestduedate,criticalratio,mostwa

46、itingtimemultipliedbytonnage,minimalarearesidue,andrandomjobselection.Zhengetal.(2012)usedadispatchingruleoflongestprocessingtimeandearlieststarttime.Twopriorityrulesareusedinthisstudytodivideallblocksintogroupsforloadbalancingandtosequencethemconsideringtheduedateandearlieststartingtime.Twopriority

47、rulesarestreamlinedtoload-balanceandsequencetheblocksintoanalgorithmwhichisillustratedinFig.7.Thefirststepofthealgorithminthisstageistogrouptheblocksbasedontheurgencypriority.Theurgencypriorityiscalculatedbysubtractingtheearlieststartingtimeandtheprocessingtimefromtheduedateforeachblock.Thesmallerth

48、eurgencypriority,themoreurgenttheblockneedstobedscheduled.Thenallblocksaregroupedintoanappropriatenumberofgroupsforareasonablenumberoflevelsinurgencypriorities.Letgbethisdiscretionarynumberofgroups.Thereareggroupsofblocksbasedontheurgencyofblocks.Thenumberofblocksineachgroupdoesnotneedtobeidentical.

49、Blocksineachgrouparere-orderedgroupedintoasmanysubgroupsasworkplaces,consideringtheworkloadofblockssuchastheweightorweldinglength.Theblocksineachsubgrouphavethesimilarurgencyandworkloads.Then,theseblocksineachsubgroupareorderedinanascendingorderoftheearlieststartingtime.Thisorderingwillbeusedtoblock

50、allocationsinsequence.Thesubgroupcorrespondstotheworkplace.Ifblockimustbeprocessedatworkplacewandiscurrentlyallocatedtootherworkplaceorsubgroupthanw,blockiisswappedwithablockatthesamepositionofblockiinanascendingorderoftheearlieststartingtimeatitsworkplace(orsubgroup).Sincethesymmetricblocksmustbelo

51、catedonasameworkplace,asimilarswappingmethodcanbeused.Oneofsymmetricblockswhichareallocatedintodifferentworkplace(orsubgroups)needstobeselectedfirst.Inthisstudy,weselectedoneofsymmetricblockswhicheverhasshownupearlierinanascendingorderoftheearlieststartingtimeattheircorrespondingworkplace(orsubgroup

52、).Then,theselectedblockisswappedwithablockatthesamepositionofsymmetricblocksinanascendingorderoftheearlieststartingtimeatitsworkplace(orsubgroups).4.2.Stage2:SpatialallocationOncetheblocksinaworkplace(orsubgroup)aresequentiallyorderedindifferenturgencyprioritygroups,eachblockcanbeassignedtoworkplace

53、sonebyone,andallocatedtoaspecificlocationonaworkplace.Therehasbeenpreviousresearchonheuristicplacementmethods.Thebottom-left(BL)placementmethodwasproposedbyBaker,Coffman,andRivest(1980)andplacesrectanglessequentiallyinabottom-leftmostposition.Jakobs(1996)usedabottom-leftmethodthatiscombinedwithahybr

54、idgeneticalgorithm(seeFig.8).LiuandTeng(1999)developedanextendedbottom-leftheuristicwhichgivesprioritytodownwardmovement,wheretherectanglesisonlyslideleftwardsifnodownwardmovementispossible.Chazele(1983)proposedthebottom-left-fill(BLF)method,whichsearchesforlowestbottom-leftpoint,holesatthelowestbot

55、tom-leftpointandthenplacetherectanglesequentiallyinthatbottom-leftposition.Iftherectangleisnotoverlapped,therectangleisplacedandthepointlistisupdatedtoindicatenewplacementpositions.Iftherectangleisoverlapped,thenextpointinthepointlistisselecteduntiltherectanglecanbeplacedwithoutanyoverlap.HopperandT

56、urton(2000)madeacomparisonbetweentheBLandBLFmethods.TheyconcludedthattheBLFmethodalgorithmachievesbetterassignmentpatternsthantheBLmethodforHopperproblems.Spatialallocationinshipbuildingisdifferentfromtwo-dimensionalpackingproblem.Blockshaveirregularpolygonalshapesinthespatialallocationandblockscont

57、inuouslyappearanddisappearsincetheyhavetheirprocessingtimes.ThisfrequentplacementandremovalofblocksmakesBLFmethodlesseffectiveinspatialallocationoflargeassemblyblock.Inordertosolvethesedrawbacks,wehavemodifiedtheBLFmethodappropriatetospatialschedulingforlargeassemblyblocks.Inaworkplace,sincetheblock

58、sareplacedandremovedcontinuously,itismoreefficienttoconsiderboththebottom-leftandtop-rightpointsofplacedblocksinsteadofbottom-leftpointsonly.Wedenoteitasdiagonalfillplacement(seeFig.9).Sincethenumberofpotentialplacementconsiderationsincreases,ittakesabitmoretimetoimplementdiagonalfillbutthecomputati

59、onalresultsshowsthatitisnegligible.ThediagonalfillmethodshowsbetterperformancesthantheBLFmethodinspatialschedulingproblems.WhentheBLFmethodisusedinspatialallocation,thealgorithmmakestheallocationofsomeblocksdelayeduntiltheinterferencebypre-positionedblocksareremoved.Itgeneratesalesseffectiveandlesse

60、fficientspatialschedule.Theproposeddiagonalfillplacementmethodresolvethisdelaysbetterbyallocatingtheblocksassoonaspossibleinagreedyway,asshowninFig.10.Thepotentialdrawbacksfromthegreedyapproachesisresolvedbyanotherplacementstrategytominimizethepossibledeadspaces,whichwillbeexplainedinthefollowingpar