船舶專業(yè)外文文獻(xiàn)

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