搜索
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-sizedSPPproblemsin20min,sothattheshopcanquicklyre-optimizetheproductionplanuponthefrequentandunexpectedchangesinshopfloorswiththeongoingoperationsonexitingblocksintact.Therearemanydifferentapplicationswhichrequireefficientschedulingalgorithmswithvariousconstraintsandcharacteristics(KimandMoon,2003,Kimetal.,2013,NguyenandYun,2014andYanetal.,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,theschedulingofassemblyprocessesforblocksandtheallocationofblockstospecificloc