用遗传算法解决设施布局问题外文文献翻译文档格式.docx

用遗传算法解决设施布局问题外文文献翻译文档格式.docx

《用遗传算法解决设施布局问题外文文献翻译文档格式.docx》由会员分享，可在线阅读，更多相关《用遗传算法解决设施布局问题外文文献翻译文档格式.docx（13页珍藏版）》请在冰点文库上搜索。

（Received12May2006;

accepted23July2006）

Abstract:

Thecomponentlayoutproblemrequiresefficientsearchoflarge,discontinuousspaces.Theefficientlayoutplanningofaproductionsiteisafundamentaltasktoanyprojectundertaking.Thispaperdescribesageneticalgorithm（GA）tosolvetheproblemofoptimalfacilitieslayoutinmanufacturingsystemdesignsothatmaterial-handlingcostsareminimized.Theperformanceoftheproposedheuristicistestedoverproblemsselectedfromtheliterature.Computationalresultsindicatethattheproposedapproachgivesbetterresultscomparedtomanyexistingalgorithmsinthisarea.

Keywords:

facilitylayout;

flexiblemanufacturing;

stochasticprogramming

1.INTRODUCTION

Componentlayoutplaysanimportantroleinthedesignandusabilityofmanyengineeringproducts.Thelayoutproblemisalsoclassifiedundertheheadingsofpacking,packaging,configuration,containerstuffing,palletloadingorspatialarrangementintheliterature.Theprobleminvolvestheplacementofcomponentsinanavailablespacesuchthatasetofobjectives

canbeoptimizedwhilesatisfyingoptionalspatialofperformanceconstraints.

Currenttoolsavailableinpracticetodesignerstoaidinthegeneralmechanicallayoutprocessmostlyremainatthestagesofphysicalorelectronicmodelswiththeassistanceofmanualadjustmentandvisualfeedback.

Thedifficultyinautomatingthemechanicalandelectromechanicallayoutprocessesstemsfrom:

（1）themodelingofthedesignobjectivesandconstraints;

（2）theconstraints;

（3）theidentificationofappropriateoptimizationsearchstrategies.

Anumberofdesigngoalscanbemodeledaslayoutobjectives.Inaddition,asetofconstrainsoftenhastobesatisfiedtoensuretheapplicabilityofthelayouts.Efficientcalculationsofobjectivesandconstraintsarenecessarytosolvethelayoutproblemsinreasonabletimesincetheanalysisofobjectivesandconstraintscanbecomputationallyexpensiveandalargenumberofevaluationsmayberequiredtoachieveconvergence.Thesearchspaceofthelayoutproblemisnon-linearandmultimodel,makingitvitaltoidentifyasuitablealgorithmtonavigatethespaceandfindgoodqualitysolutions.

Thelayoutgoalsareusuallyformulatedasobjectivefunctions.Theobjectivesmayreflectthecost,quality,performanceandservicerequirements.Variousconstraintsmaybenecessarytospecifyspatialrelationshipsbetweencomponents.Thespecificationsofcomponents,objectives,

constraints,andtopologicalconnectionsdefinealayoutproblemandanoptimizationsearchalgorithmtakestheproblemformulationandidentifiespromisingsolutionbyevaluatingdesignalternativesandevolvingdesignstates.Analysisofobjectivesandconstraintsvaryfromproblem

toproblem.However,theoptimizationsearchtechniqueandgeometricrepresentationandtheresultinginterferenceevaluationareproblemindependentandare,thus,thefocusforagenericlayouttool[1].

Theprimaryobjectiveofthedesignproblemistominimizethecostsassociatedwithproductionandmaterialsmovementlayout,semiconductormanufacturingandservicecenterlayout.ForUSmanufacturers,between20%and50%oftotaloperatingexpensesarespentonmaterialhandlingandanappropriatefacilitiesdesigncanreducethesecostsbyatleast10%-30%[2,3].

Alteringfacilitydesignsduetoincorrectdecisions,forecastsorassumptionsusuallyinvolvesconsiderablecost,timeanddisruptionofactivities.Ontheotherhand,gooddesigndecisionscanreapeconomicandoperationalbenefitsforalong–timeperiod.Therefore,thecriticalaspectsaredesignsthattranslatereadilyintophysicalrealityanddesignsthatare"

robust"

todeparturesfromassumptions.

Theprojectmanagerorplannerusuallyperformsthetaskofpreparingthelayoutbasedonhis/herownknowledgeandexpertise.Apparently,thiscouldresultinlayoutsthatdiffersignificantlyfromonepersontoanother.Toputthistaskintomoreperspective,researchershaveintroduceddifferentapproachestosystematicallyplanthelayoutofproductionsites[4,5]

Facilitylayoutplanningcangenerallybeclassifiedaccordingtotwomainaspects:

（1）methodoffacilityassignmentand

（2）layoutplanningtechnique.

Mathematicaltechniquesusuallyinvolvetheidentificationofoneormoregoalsthatthesoughtlayoutshouldstrivetoachieve.Awidelyusedgoalistheminimizationoftransportationcostsonsite.Thesegoalsarecommonlyinterpretedtowhatmathematiciansterm"

objectivefunctions"

.Thisobjectivefunctionisthenoptimizedunderproblem-specificconstraintsto

producethedesiredlayout.Systemsutilizingknowledge-basedtechniques,incontrast,providerulesthatassistplannersinlayoutplanningratherthanperformtheprocessbasedpurelyonaspecifiedoptimizationgoal（s）.

Usuallytheselectedfitnessfunctionistheminimumtotalcostsofhandlingofworkpieces.Ingeneral,thosecostsarethesumofthetransportcosts（theseareproportionaltotheintensityoftheflowanddistances）andothercosts

.Aneffectivefacilitylayoutdesignreduces.manufacturinglead-time,andincreasesthethroughput,henceincreasesoverallproductivityandefficiencyoftheplant.Themajortypesofarrangementsinmanufacturingsystemsaretheprocess,theflowlineorsingleline,themulti-line,thesemi-circularandthelooplayout.Theselectionofaspecificlayoutdefinesthewayinwhichpartsmovefromonemachinetoanothermachine.Theselectionofthemachinelayoutisaffectedbyanumberoffactors,namelythenumberofmachines,availablespace,similarityofoperationsequencesandthematerialhandlingsystemused.Therearemanytypesofmaterialhandlingequipmentthatincludeautomatedguidedvehicles,conveyersystems,robots,andothers.Theselectionofthematerialhandlingequipmentisimportantinthedesignofamodernmanufacturingfacility[6].

Theprobleminmachinelayoutdesignistoassignmachinestolocationswithinagivenlayoutarrangementsuchthatagivenperformancemeasureisoptimized.Themeasureusedhereistheminimizationofmaterialhandlingcost.Thisproblembelongstothenon-polynomialhard（NP-hard）class.Theproblemcomplexityincreasesexponentiallywiththenumberofpossiblemachinelocations.

2.LAYOUTSPACECHARACTERISTICSANDSOLUTIONAPPROACHES

Theproblemofplantlayoutinvolvesdistributingdifferentdepartments,equipment,andphysicalresourcesasbestaspossibleinthefacility,inordertoprovidegreaterefficiencyintheproductionofgoodsorservices.Theaimstobeachievedwhendealingwithaproblemoftheabovetypecangenerallybedescribedfromtwostances.Ontheonehand,manyresearchersdescribetheproblemasoneofoptimizingproductflow,fromtherawmaterialstagethroughtothefinalproduct.Thisisachievedbyminimizingthetotalmaterialhandlingcosts.Solvingtheprobleminthissenserequiresknowingdistancesbetweendepartments（usuallytakenfromtheircentroids）,thenumberoftripsbetweendepartments,andthecostperunit.

Ontheotherhand,layoutcanbeconsideredasadesignproblem.Seenfromthisangle,solvingtheprobleminvolvesnotonlycollectingthequantitativeinformationmentionedabove,butalsoqualitativeinformation,forinstance,howdifferentdepartmentsarerelatedfromthepointofviewofadjacency.

Thelayoutspaceisdefinedasthemathematicalrepresentationofthespaceofconfigurationsmappedagainstthecostperconfiguration.Deterministicalgorithmsareunabletonavigatesuchaspaceforgloballynear-optimalsolutions,andstochasticalgorithmsareusuallyrequiredforsolutionsofgoodquality.

Themannerofarrangingofworkingdeviceslargelydependsonthetypeofproduction.NP-hardproblemsareunsolvableinpolynomialtime[7]（Kusiak1990）.Accuratemathematicalsolutionsdonotexistforsuchproblem.Thecomplexityofsuchproblemsincreasesexponentially

withthenumberofdevices.Forinstance,aflexiblemanufacturingsystem（FMS）consistingofNmachineswillcompriseasolutionspacewiththesizeN.Theproblemistheoreticallysolvablealsobytestingallpossibilities（i.e.,randomsearching）butpracticalexperienceshowsthatinsuch

mannerofsolvingthecapabilitiesofeitherthehumanorthecomputerarefastexceeded.ForarrangingthedevicesintheFMSthenumberofpossiblesolutionsisequaltothenumberofpermutationsofNelements.WhenNislarge,itisdifficult,ifnotimpossible,toproducetheoptimalsolutionwithinareasonabletime,evenwithsupportofapowerfulcomputer.Withtoday'

scomputationpowerofmoderncomputersitispossibletosearchfortheoptimumsolutionbyexaminingthetotalspaceofsolutionssomewhereuptothedimensionsofspace10.Incaseofproblemsoflargerdimensionsitisnecessarytousesophisticatedsolvingmethodswhich,duringexaminingthesolutionspacesomehowlimitthemselvesandutilizepossiblesolutionsalreadyexamined[8].

3.LAYOUTSEARCHALGORITHMS

Thelayoutproblemcanhavedifferentformulations,butitisusuallyabstractedasanoptimizationproblem.Anassignmentofthecoordinatesandorientationsofcomponentsthatminimizesthecostandsatisfiescertainplacementrequirementsissought.TheproblemcanbeviewedasageneralizationofthequadraticassignmentproblemandthereforebelongstotheclassofNP-hardproblems[9].Consequentlyitishighlyunlikelythatexactsolutiontothegenerallayoutproblemcanbeobtainedinanamountoftimethatisboundedbyapolynomialinthesizeoftheproblem,resultingin