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.Fig.1showsasnapshotoflargeassemblyblocksinashipyardassemblyshop.Recently,theresearchersandpractitionersatacademiaandshipbuildingindustriesrecentlygottogetherat“SmartProductionTechnologyForuminShipbuildingandOceanPlantIndustries”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(KimandMoon,2003,Kimetal.,2013,NguyenandYun,2014

and

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.,workplacesaredesirableinordertoThedecisionvariablesofspatialschedulingproblemare(x,y,z)coordinatesofallblockswithinathree-dimensionalspacewhosesizesareLENW,WIDWandTinx,yandzaxes,whereTrepresentstheplanninghorizon.ThisspaceisillustratedinFig.5.InFig.6,thespatialschedulingoftwoblocksintoaworkplaceisillustratedasanexample.Theparametersp1andp2indicatetheprocessingtimesforBlocks1and2,respectively.Asshowninzaxis,Block2isscheduledafterBlock1iscompleted.4.Atwo-stageheuristicalgorithmThecomputationalexperimentsfortheMIPmodelinSection3havebeenconductedusingacommerciallyavailablesolver,LINGO?.Obtainingglobaloptimumsolutionsisverytimeconsuming,consideringthenumberofvariablesandconstraints.Ashipisconsistedofmorethan8hundredlargeblocksandthesizeofproblemusingMIPmodelisbeyondtoday’scomputationalability.Atwo-stageheuristicalgorithmhasbeenproposedusingthedispatchingpriorityrulesandadiagonalfillmethod.4.1.Stage1:LoadbalancingandsequencingPastresearchonspatialschedulingproblemsconsidersvariouspriorityrules.Leeetal.(1996)usedapriorityrulefortheminimumslacktimeofblocks.Choetal.(2001)andParketal.(2002)usedtheearliestduedate.Shinetal.(2008)consideredthreedispatchingpriorityrulesforstartdate,finishdateandgeometriccharacteristics(length,breadth,andarea)ofblocks.LiuandTeng(1999)compared9differentdispatchingpriorityrulesincludingfirst-comefirst-serve,shortestprocessingtime,leastslack,earliestduedate,criticalratio,mostwaitingtimemultipliedbytonnage,minimalarearesidue,andrandomjobselection.Zhengetal.(2012)usedadispatchingruleoflongestprocessingtimeandearlieststarttime.Twopriorityrulesareusedinthisstudytodivideallblocksintogroupsforloadbalancingandtosequencethemconsideringtheduedateandearlieststartingtime.Twopriorityrulesarestreamlinedtoload-balanceandsequencetheblocksintoanalgorithmwhichisillustratedinFig.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)placementmethodwasproposedbyBaker,Coffman,andRivest(1980)andplacesrectanglessequentiallyinabottom-leftmostposition.Jakobs(1996)usedabottom-leftmethodthatiscombinedwithahybridgeneticalgorithm(seeFig.8).LiuandTeng(1999)developedanextendedbottom-leftheuristicwhichgivesprioritytodownwardmovement,wheretherectanglesisonlyslideleftwardsifnodownwardmovementispossible.Chazele(1983)proposedthebottom-left-fill(BLF)method,whichsearchesforlowestbottom-leftpoint,holesatthelowestbottom-leftpointandthenplacetherectanglesequentiallyinthatbottom-leftposition.Iftherectangleisnotoverlapped,therectangleisplacedandthepointlistisupdatedtoindicatenewplacementpositions.Iftherectangleisoverlapped,thenextpointinthepointlistisselecteduntiltherectanglecanbeplacedwithoutanyoverlap.HopperandTurton(2000)madeacomparisonbetweentheBLandBLFmethods.TheyconcludedthattheBLFmethodalgorithmachievesbetterassignmentpatternsthantheBLmethodforHopper’sexampleproblems.Spatialallocationinshipbuildingisdifferentfromtwo-dimensionalpackingproblem.Blockshaveirregularpolygonalshapesinthespatialallocationandblockscontinuouslyappearanddisappearsincetheyhavetheirprocessingtimes.ThisfrequentplacementandremovalofblocksmakesBLFmethodlesseffectiveinspatialallocationoflargeassemblyblock.Inordertosolvethesedrawbacks,wehavemodifiedtheBLFmethodappropriatetospatialschedulingforlargeassemblyblocks.Inaworkplace,sincetheblocksareplacedandremovedcontinuously,itismoreefficienttoconsiderboththebottom-leftandtop-rightpointsofplacedblocksinsteadofbottom-leftpointsonly.Wedenoteitasdiagonalfillplacement(seeFig.9).Sincethenumberofpotentialplacementconsiderationsincreases,ittakesabitmoretimetoimplementdiagonalfillbutthecomputationalresultsshowsthatitisnegligible.ThediagonalfillmethodshowsbetterperformancesthantheBLFmethodinspatialschedulingproblems.WhentheBLFmethodisusedinspatialallocation,thealgorithmmakestheallocationofsomeblocksdelayeduntiltheinterferencebypre-positionedblocksareremoved.Itgeneratesalesseffectiveandlessefficientspatialschedule.Theproposeddiagonalfillplacementmethodresolvethisdelaysbetterbyallocatingtheblocksassoonaspossibleinagreedyway,asshowninFig.10.Thepotentialdrawbacksfromthegreedyapproachesisresolvedbyanotherplacementstrategytominimizethepossibledeadspaces,whichwillbeexplainedinthefollowingparagraphs.TheBLFmethodonlyfocusedontwo-dimensionalbinpacking.Frequentremovalandplacementofblocksinaworkspacemayleadtoaccumulationofdeadspaces,whicharesmallandunusablespacesamongblocks.Aminimalpossible-deadspacestrategyhasbeenusedalongwiththeBLFmethod.Possible-deadspacesarebeinggeneratedoverthespatialschedulingandtheyhavelesschancetobeallocatedforfutureblocks.Theminimalpossible-deadspacestrategyminimizesthepotentialdeadspaceafterallocatingthefollowingblocks(Chung,2001

and

Kohetal.,2008)byconsideringthe0°and90°rotationoftheblockandallocatingthefollowingblockforminimalpossible-deadspace.Fig.11showsanexampleofthreepossible-deadspacecalculationsusingtheneighborblocksearchmethod.Whenanewschedulingblockisconsideredtobeallocated,therectangularboundaryofneighboringblocksandtheschedulingblocksissearched.Thisboundarycanbecalculatedbyobtainingthesmallestandthelargestxandycoordinatesofneighboringblocksandtheschedulingblocks.Throughthisprocedure,thepossible-deadspacecanbecalculatedasshowninFig.11.Consideringtherotationoftheschedulingblocksandtheplacementconsiderationpointsfromthediagonalfillplacementmethods,theschedulingblockswillbefinallyallocated.Inthistwo-stagealgorithm,blockstendtobeplacedadjacenttooneofthealternativeedgesandtheirassignmentsaredonepreferentiallytominimizefracturedspaces.5.ComputationalresultsTodemonstratetheeffectivenessandefficiencyoftheproposedMIPformulationandheuristicalgorithm,theactualdataabout800+largeassemblyblocksfromoneofmajorshipbuildingcompanieshasbeenobtainedandused.Alltestproblemsaregeneratedfromthisreal-worlddata.AllcomputationalexperimentshavebeencarriedoutonapersonalcomputerwithaIntel?Core?i3-2100CPU@3.10

GHzwith2

GBRAM.TheMIPmodelinSection3hasbeenprogrammedandsolvedusingLINGO?version10.0,acommerciallyavailablesoftwarewhichcansolvelinearandnonlinearmodels.Theproposedtwo-stageheuristicalgorithmhasbeenprogrammedinJAVAprogramminglanguage.Becauseourcomputationaleffortstoobtaintheoptimalsolutionsforevensmallproblemsaremorethansignificant,thecomplexityofSPPcanberecognizedasoneofmostdifficultandtimeconsumingproblems.DependingonthescalingfactorαinobjectivefunctionoftheproposedMIPformulation,theperformanceoftheMIPmodelvariessignificantly.Settingαlessthan0.01makestheloadbalancingcapabilitytobeignoredfromtheoptimalsolutionintheMIPmodel.Forcomputationalexperimentsinthisstudy,theresultswiththescalingfactorsetto0.01isshownanddiscussed.Thevalueneedstobefine-turnedtoobtainthedesirableoutcomes.Table1showsacomparisonofcomputationalresultsandperformancebetweentheMIPmodelsandtwo-stageheuristicalgorithm.AsshowninTable1,theproposedtwo-stageheuristicalgorithmfindsthenear-optimalsolutionsformediumandlargeproblemsveryquicklywhiletheoptimalMIPmodelswasnotabletosolvetheproblemsofmediumorlargesizesduetothememoryshortageoncomputers.ItisobservedthatthecomputationaltimesfortheMIPproblemsarerapidlygrowingastheproblemsizesincreases.ThetestproblemsinTable1have2workplaces.Table1.ComputationalresultsandperformancebetweentheMIPmodelsandtwo-stageheuristicalgorithm.NumberofblocksTheMIPmodelTwo-stageheuristicalgorithmOptimalsolutionTime(s)BestknownsolutionTime(s)1012.3601014.00012.3600.0262022.380a38250.00021.3800.0783098.344a38255.00030.7400.21850––53.7600.719100––133.7802.948200––328.86012.523300––416.06040.154400––532.36073.214Bestfeasiblesolutionafter10

hinGlobalSolverofLINGO?.\o"Full-sizetable-Opensnewwindow"Full-sizetableTableoptions\o"Viewinworkspace"Viewinworkspace\o"DownloadasCSV"DownloadasCSVTheoptimalsolutionsfortestproblemswithmorethan50blocksinTable1havebeennotobtainedevenafter24

h.Thebestknownfeasiblesolutionsafter10

hforthetestproblemswith20blocksand30blocksarereportedinTable1.ItisobservedthattheLINGO?doesnotsolvethenonlinearconstraintsverywellasshowninTable1.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‘–’inTable1indicatesthattheGlobalSolverofLINGO?didnotfindthefeasiblesolutions.Anotherobservationonthetwo-stageheuristicalgorithmsistherobustcomputationaltimes.Thecomputationtimesdoesnotchangemuchastheproblemsizesincrease.Itisbecausethesimplepriorityrulesareusedwithoutconsideringmanycombinatorialconfigurations.Fig.12showspartialsolutionsoftestproblemswith20and30blockson2workplaces.ThepurposeofFig.12istoshowtheprogressofproductionplanninggeneratedbythetwo-stageheuristicalgorithm.Twoworkplacesareindifferentsizesof(40,30)and(35,40),respectively.6.ConclusionsAsglobalwarmingisexpectedtoopenanewwaytotransportamongcontinentthroughNorthPoleSeaandtoexpeditetheoceansmoreaggressively,theneedsformoreshipsandoceanplantsareforthcoming.Theshipbuildingindustriescurrentlyfaceincreaseddiversityofassemblyblocksinlimitedproductionshipyard.Spatialschedulingforlargeassemblyblocksholdsthekeyroleinsuccessfuloperationsoftheshipbuildingcompanies.Thetaskofspatialschedulingtakesplaceatalmosteverystageofshipbuildingprocessesandthelargeassemblyshopisoneofthemostcongestedoperationalareasintoday’sshipbuilding.Itisalsoknownthatthespatialschedulingproblemhasbeenthemajorsourceofthebottleneck.Thepractitionersinshipbuildingindustriesrequirestheirproductionplanningsystemtooptimizethespatialschedulingandtorespondquicklytothechangesontheshopfloorbyre-optimizingtheproductionplanin20-mintimeframe.Mostcompaniesuseasystememployingheuristicmethodsinanad-hocmannerwithoutknowinghowgoodtheirplanningsystemis.Tobenchmarktheperformanceoftheheuristicalgorithms,anovelMIPmodelhasbeenproposedconsideringvariousreal-worldconstraintsthatareraisedbyfieldprofessionalsandengineers.Thoseincludeblockrotations,symmetricalblocks,pre-existingblocks,loadbalancingandallocationofcertainblockstopre-determinedworkspace.Theseconstraintshavenotbeenconsideredsimultaneouslybypreviousresearchers.TheMIPformulationcanbeusedasatargettoevaluatetheirspatialschedulingsysteminshipbuildingcompanies.Inaddition,theexpectationandneedofmajorsolutioncompaniessuchasSiemens?andDassultSystems?isanefficientandeffectivealgorithmtoperformspatialscheduling.Whenanewtypeofshipsoroceanplantsisdesignedandbuilt,thereisahigherchancetoobserveunexpectedinterruptionsinproductionflows.Theseinterruptionscausesignificantlossesintime,labor,resourceandetc.Therefore,theneedtore-optimizespatialschedulingquicklyinshorteramountofcomputationaltimesbecomesgreater.Theproposedtwo-stageheuristicalgorithmusesasimplepriorityrulesanddispatchingrulestogrouptheblocksforquickloadbalancingandsuggeststhediagonalfillplacementmethodwhichisfittospatialschedulinginshipbuilding.Thecomputationalresultsshowthattheproposedalgorithmfindsgoodsolutionsefficientlyandeffectivelyfortestproblemsofallsizes.Italsodemonstratesthatthecomputationaltimesoftheproposedalgorithmarerobusttoproblemsizes.Infuture,duetotheincapabilityoftheMIPsolvertoobtaintheoptimalsolutionefficiently,therelationoftheproposedmodelisbeingperformedtoobtainthelowerbound.AcknowledgementThisworkwassupportedbya2-YearResearchGrantofPusanNationalUniversity.ReferenceBakeretal.,1980B.S.Baker,E.G.Coffman,R.L.RivestOrthogonalpackingintwodimensionsSIAMJournalofComputing,9(4)(1980),pp.846–855Chazele,1983B.ChazeleThebottom-leftbin-packingheuristic:AnefficientimplementationIEEETransactionsonComputers,c-32(8)(1983),pp.697–707Choetal.,2001K.K.Cho,K.H.Chung,C.Park,J.C.Park,H.S.KimAspatialschedulingsystemforblockpaintingprocessinshipbuildingCIRPAnnals-ManufacturingTechnology,50(1)(2001),pp.339–342Chung,2001Chung,K.H.(2001).Astudyonoperationschedulingsystemforblockpaintingprocessinshipbuilding,Ph.D.Thesis,PusanNationalUniversity.HopperandTurton,2000E.Hopper,B.C.H.TurtonAnempiricalinvestigationofmeta-heuristicandheuristicalgorithmsfora2DpackingproblemEuropeanJournalofOperationsResearch,128(1