工業(yè)工程英文文獻(xiàn)及外文翻譯

附錄附錄1：英文文獻(xiàn)LineBalancingintheRealWorldAbstract:LineBalancing(LB)isaclassic,well-researchedOperationsResearch(OR)optimizationproblemofsignificantindustrialimportance.Itisoneofthoseproblemswheredomainexpertisedoesnothelpverymuch:whateverthenumberofyearsspentsolvingit,oneiseachtimefacinganintractableproblemwithanastronomicnumberofpossiblesolutionsandnorealguidanceonhowtosolveitinthebestway,unlessonepostulatesthattheoldwayisthebestway.Hereweexplainanapparentparadox:althoughmanyalgorithmshavebeenproposedinthepast,anddespitetheproblem’spracticalimportance,justonecommerciallyavailableLBsoftwarecurrentlyappearstobeavailableforapplicationinindustriessuchasautomotive.WespeculatethatthismaybeduetoamisalignmentbetweentheacademicLBproblemaddressedbyOR,andtheactualproblemfacedbytheindustry.Keyword:LineBalancing,Assemblylines,Optimization

LineBalancingintheRealWorldEmanuelFalkenauerOptimalDesignAv.Jeanne19Abo?te2,B-1050Brussels,Belgium+32(0)264610741IntroductionAssemblyLineBalancing,orsimplyLineBalancing(LB),istheproblemofassigningoperationstoworkstationsalonganassemblyline,insuchawaythattheassignmentbeoptimalinsomesense.EversinceHenryFord’sintroductionofassemblylines,LBhasbeenanoptimizationproblemofsignificantindustrialimportance:theefficiencydifferencebetweenanoptimalandasub-optimalassignmentcanyieldeconomies(orwaste)reachingmillionsofdollarsperyear.LBisaclassicOperationsResearch(OR)optimizationproblem,havingbeentackledbyORoverseveraldecades.Manyalgorithmshavebeenproposedfortheproblem.Yetdespitethepracticalimportanceoftheproblem,andtheOReffortsthathavebeenmadetotackleit,littlecommerciallyavailablesoftwareisavailabletohelpindustryinoptimizingtheirlines.Infact,accordingtoarecentsurveybyBeckerandScholl(2004),thereappeartobecurrentlyjusttwocommerciallyavailablepackagesfeaturingbothastateoftheartoptimizationalgorithmandauser-friendlyinterfacefordatamanagement.Furthermore,oneofthosepackagesappearstohandleonlythe“clean”formulationoftheproblem(SimpleAssemblyLineBalancingProblem,orSALBP),whichleavesonlyonepackageavailableforindustriessuchasautomotive.Thissituationappearstobeparadoxical,oratleastunexpected:giventhehugeeconomiesLBcangenerate,onewouldexpectseveralsoftwarepackagesvyingtograbapartofthoseeconomies.ItappearsthatthegapbetweentheavailableORresultsandtheirdisseminationinToday’sindustry,isprobablyduetoamisalignmentbetweentheacademicLBproblemaddressedbymostoftheORapproaches,andtheactualproblembeingfacedbytheindustry.LBisadifficultoptimizationproblemevenitssimplestformsareNP-hard–seeGarryandJohnson,1979),sotheapproachtakenbyORhastypicallybeentosimplifyit,inordertobringittoalevelofcomplexityamenabletoORtools.Whilethisisaperfectlyvalidapproachingeneral,intheparticularcaseofLBitledsomedefinitionsoftheproblemhatignoremanyaspectsofthereal-worldproblem.Unfortunately,manyoftheaspectsthathavebeenleftoutintheORapproachareinfactcrucialtoindustriessuchasautomotive,inthesensethatanysolutionignoring(violating)thoseaspectsbecomesunusableintheindustry.Inthesequel,wefirstbrieflyrecallclassicORdefinitionsofLB,andthenreviewhowtheactuallinebalancingproblemfacedbytheindustrydiffersfromthem,andwhyasolutiontotheclassicORproblemmaybeunusableinsomeindustries.2ORDefinitionsofLBTheclassicORdefinitionofthelinebalancingproblem,dubbedSALBP(SimpleAssemblyLineBalancingProblem)byBeckerandScholl(2004),goesasfollows.Givenasetoftasksofvariousdurations,asetofprecedenceconstraintsamongthetasks,andasetofworkstations,assigneachtasktoexactlyoneworkstationinsuchawaythatnoprecedenceconstraintisviolatedandtheassignmentisoptimal.Theoptimalitycriteriongivesrisetotwovariantsoftheproblem:eitheracycletimeisgiventhatcannotbeexceededbythesumofdurationsofalltasksassignedtoanyworkstationandthenumberofworkstationsistobeminimized,orthenumberofworkstationsisfixedandthelinecycletime,equaltothelargestsumofdurationsoftaskassignedtoaworkstation,istobeminimized.AlthoughtheSALBPonlytakesintoaccounttwoconstraints(theprecedenceconstraintsplusthecycletime,ortheprecedenceconstraintsplusthenumberofworkstations),itisbyfarthevariantoflinebalancingthathasbeenthemostresearched.WehavecontributedtothateffortinFalkenauerandDelchambre(1992),whereweproposedaGroupingGeneticAlgorithmapproachthatachievedsomeofthebestperformanceinthefield.TheGroupingGeneticAlgorithmtechniqueitselfwaspresentedindetailinFalkenauer(1998).Howeverwellresearched,theSALBPishardlyapplicableinindustry,aswewillseeshortly.ThefacthasnotescapedtheattentionoftheORresearches,andBeckerandScholl(2004)definemanyextensionstoSALBP,yieldingacommondenominationGALBP(GeneralizedAssemblyLineBalancingProblem).Eachoftheextensionsreportedintheirauthoritativesurveyaimstohandleanadditionaldifficultypresentinreal-worldlinebalancing.WehavetackledoneofthoseaspectsinFalkenauer(1997),alsobyapplyingtheGroupingGeneticAlgorithm.ThemajorproblemwithmostoftheapproachesreportedbyBeckerandScholl(2004)isthattheygeneralizethesimpleSALBPinjustoneortwodirections.Therealworldlinebalancing,asfacedinparticularbytheautomotiveindustry,requirestacklingmanyofthosegeneralizationssimultaneously.3WhatDiffersintheRealWorld?AlthougheventhesimpleSALBPisNP-hard,itisfarfromcapturingthetruecomplexityoftheprobleminitsreal-worldincarnations.Ontheotherhand,smallinstancesoftheproblem,eventhoughtheyaredifficulttosolvetooptimality,areatrickytargetforlinebalancingsoftware,becausesmallinstancesoftheproblemcanbesolvedclosetoptimalitybyhand.Thatishowevernotthecaseintheautomotiveandrelatedindustries(Bus,truck,aircraft,heavymachinery,etc.),sincethoseindustriesroutinelyfeatureAssemblylineswithdozensorhundredsofworkstations,andhundredsorthousandsofOperations.Thoseindustriesarethereforetheprimetargetsforlinebalancingsoftware.Unfortunately,thosesameindustriesalsoneedtotakeintoaccountmanyoftheGALBPextensionsatthesametime,whichmayexplainwhy,despitetheimpressiveORWorkdoneonlinebalancing;onlyonecommerciallyavailablesoftwareseemstubecurrentlyavailableforthoseindustries.Weidentifybelowsomeoftheadditionaldifficulties(withrespecttoSALBP)thatmustbetackledinalinebalancingtool,inordertobeapplicableinthoseindustries.3.1DoNotBalancebutRe-balanceManyoftheORapproachesimplicitlyassumethattheproblemtobesolvedinvolvesanew,yet-to-be-builtassemblyline,possiblyhousedinanew,yet-to-be-builtfactory.Toouropinion,thisisthegravestoversimplificationoftheclassicORapproach,forinpractice,thisishardlyeverthecase.Thevastmajorityofreal-worldlinebalancingtasksinvolveexistinglines,housedinexistingfactories–infect,thetargetlinetypicallyneedstuberebalancedratherthanbalanced,theneedarisingfromchangesintheproductorthemixofmodelsbeingassembledintheline,theassemblytechnology,theavailableworkforce,ortheproductiontargets.Thishassomefar-reachingimplications,outlinedbelow.3.2WorkstationsHaveIdentitiesAspointedoutabove,thevastmajorityofreal-worldlinebalancingtasksinvolvesexistinglineshousedinexistingfactories.Inpractice,thisseemingly“uninteresting”observationhasonefar-reachingconsequence,namelythateachworkstationinthelinedoeshaveitsownidentity.Thisidentityisnotduetoany“incapacityofabstraction”onpartoftheprocessengineers,butrathertothefactthattheworkstationsareindeednotidentical:eachhasitsownspaceconstraints(e.g.aworkstationbelowalowceilingcannotelevatethecarabovetheoperators’heads),itsownheavyequipmentthatcannotbemovedsparehugecosts,itsowncapacityofcertainsupplies(pressedair),itsownrestrictionsontheoperationsthatcanbecarriedoutthere(e.g.donotplaceweldingoperationsjustbesidethepaintingshop),etc.3.3CannotEliminateWorkstationsSinceworkstationsdohavetheiridentity(asobservedabove),itbecomesobviousthatareal-worldLBtoolcannotaimateliminatingworkstations.Indeed,unlesstheeliminatedworkstationswereallinthefrontofthelineoritstail,theireliminationwouldcreategapingholesintheline,byvirtueoftheotherworkstations’retainingoftheiridentities,includingtheirgeographicalpositionsintheworkshop.Also,itsoftensthecasethatmanyworkstationsthatcouldpossiblybeeliminatedbythealgorithmareinfactnecessarybecauseofzoningconstraints.4ConclusionsTheconclusionsinspection3stemsfromourextensivecontactswithautomotiveandrelatedindustries,andreflectstheirtrueneeds.Other“exotic”constraintsmayapplyinanygivenreal-worldassemblyline,butlinebalancingtoolforthoseindustriesmustbeabletohandleatleastthoseaspectsoftheproblem.Thisisveryfarfromthe“clean”academicSALBP,aswellasmostGALBPextensionsreportedbyBeckerandScholl(2004).Infact,suchatoolmustsimultaneouslysolveseveral-hardproblems:?Findafeasibledefinedreplacementforallundefined(‘ANY’)ergonomicconstraintsonworkstations,i.e.Onecompatiblewiththeergonomicconstraintsandprecedenceconstraintsdefinedonoperations,aswellaszoningconstraintsandpossibledriftingoperations?Solvethewithin-workstationschedulingproblemonallworkstations,forallproductsbeingassembledontheline?Assigntheoperationstoworkstationstoachievethebestaveragebalance,whilekeepingthepeaktimesatamanageablelevel.Clearly,thereal-worldlinebalancingproblemdescribedaboveisextremelydifficulttosolve.Thisiscompoundedbytesizeoftheproblemencounteredinthetargetindustries,whichroutinelyfeatureassemblylineswithdozensorhundredsofworkstationswithmultipleoperators,andhundredsorthousandsofoperations.We’veidentifiedanumberofaspectsofthelinebalancingproblemthatarevitalinindustriessuchasautomotive,yetthathavebeeneitherneglectedintheORworkontheproblem,orhandledseparatelyfromeachother.Accordingtoourexperience,alinebalancingtoapplicableinthoseindustriesmustbeabletohandleallofthemsimultaneously.Thatgivesrisetoanextremelycomplexoptimizationproblem.Thecomplexityoftheproblem,andtheneedtosolveitquickly,mayexplainwhythereappearstobejustonecommerciallyavailablesoftwareforsolvingit,namelyoutlinebyOptimalDesign.MoreinformationonOutline,includingitsrichgraphicuserinterface,isavailableat.References1BeckerC.andScholl,A.(2004)`Asurveyonproblemsandmethodsingeneralizedassemblylinebalancing',EuropeanJournalofOperationsResearch,inpress.Availableonlineat:///doi:10.1016/j.ejor.2004.07.023.Journalarticle.2Falkenauer,E.andDelchambre,A.(1992)`GeneticAlgorithmforBinPackingandLineBalancing',Proceedingsofthe1992IEEEInternationalConferenceonRoboticsandAutomation,May10-15,1992,Nice,France.IEEEComputerSocietyPress,LosAlamitos,CA.Pp.1186-1192.Conferenceproceedings.3Falkenauer,E.(1997)`AGroupingGeneticAlgorithmforLineBalancingwithResourceDependentTaskTimes',ProceedingsoftheFourthInternationalConferenceonNeuralInformationProcessing(ICONIP’97),UniversityofOtego,Dunedin,NewZealand,November24-28,1997.Pp.464-468.Conferenceproceedings.4Falkenauer,E.(1998)GeneticAlgorithmsandGroupingProblems,JohnWiley&Sons,ChiChester,UK.Book.5Gary.R.andJohnsonD.S.(1979)ComputersandIntractability-AGuidetotheTheoryofNP-completeness,Co.,SanFrancisco,USA.Book.

附錄2：中文文獻(xiàn)生產(chǎn)線平衡在現(xiàn)實(shí)世界摘要：生產(chǎn)線平衡（LB）是一個(gè)經(jīng)典的，細(xì)心探討的顯著工業(yè)重要性的運(yùn)籌學(xué)（OR）優(yōu)化問(wèn)題。這是其中一個(gè)所在領(lǐng)域的專業(yè)學(xué)問(wèn)并沒(méi)有太大幫助的問(wèn)題之一：無(wú)論花了多少年解決它，面對(duì)每一次麻煩的問(wèn)題與可能的天文數(shù)字的解決方案都并不是關(guān)于如何解決這個(gè)問(wèn)題的最好方法，除非你假定老方法是最好的方法。在這里，我們說(shuō)明一個(gè)明顯的悖論：雖然很多算法已經(jīng)被提出，在過(guò)去，盡管該問(wèn)題的實(shí)際重要性只是一個(gè)市場(chǎng)銷售的LB軟件。目前好像可用于工業(yè)，如汽車中的應(yīng)用。我們推想，這可能是由于在學(xué)術(shù)LB問(wèn)題之間的沒(méi)有通過(guò)運(yùn)籌學(xué)路徑和生產(chǎn)業(yè)實(shí)際面對(duì)的問(wèn)題。關(guān)鍵詞：生產(chǎn)線平衡，裝配生產(chǎn)線，優(yōu)化

生產(chǎn)線平衡在現(xiàn)實(shí)世界伊曼紐爾?？夏螤杻?yōu)化設(shè)計(jì)地址：珍妮大道19A，2道，B-1050布魯塞爾，比利時(shí)+32（0）264610741引言裝配線平衡，或者簡(jiǎn)稱生產(chǎn)線平衡（LB），是一個(gè)操作工作站沿著裝配線安排的問(wèn)題，在這樣一種方式，該安排是在某種意義上最優(yōu)的。自從亨利?福特引進(jìn)組裝生產(chǎn)線，LB已經(jīng)成為影響工業(yè)重要性的最優(yōu)化問(wèn)題：在效率不同的最優(yōu)和次優(yōu)安排之間的差異可以產(chǎn)生經(jīng)濟(jì)（或奢侈）達(dá)到數(shù)百萬(wàn)美元每年。LB是一個(gè)經(jīng)典的運(yùn)籌學(xué)（OR）的優(yōu)化問(wèn)題，已通過(guò)被運(yùn)籌學(xué)解決達(dá)以上幾十年。很多算法已經(jīng)被提出了去解決這個(gè)問(wèn)題。盡管問(wèn)題的有實(shí)際重要性，并已經(jīng)取得了或努力，但很少的商業(yè)軟件是可以幫助行業(yè)優(yōu)化其生產(chǎn)線。事實(shí)上，依據(jù)最近貝克爾和紹爾（2004）的一項(xiàng)調(diào)查顯示，好像有目前只有兩個(gè)市場(chǎng)銷售的軟件包有特色，即是最先進(jìn)的優(yōu)化算法的狀態(tài)和數(shù)據(jù)管理的用戶友好的界面。此外，這些軟件包，好像只處理“干凈”的提法的問(wèn)題（簡(jiǎn)潔裝配線平衡問(wèn)題，或SALBP），這讓只有一個(gè)軟件包可用于工業(yè)，如汽車業(yè)。這種狀況好像是自相沖突的，或者至少是意想不到的：給定的LB可以產(chǎn)生的巨大經(jīng)濟(jì)，人們能夠所期望的幾個(gè)軟件包爭(zhēng)先恐后地抓住這些經(jīng)濟(jì)體的一部分?？磥?lái)，現(xiàn)有的運(yùn)籌學(xué)結(jié)果以及它們?cè)趥鞑ブg存在差距。當(dāng)今的工業(yè)，很可能是由于在學(xué)術(shù)LB問(wèn)題之間通過(guò)運(yùn)籌學(xué)大多數(shù)的或接近解決，對(duì)于企業(yè)所面對(duì)的實(shí)際問(wèn)題。LB是一個(gè)困難的優(yōu)化問(wèn)題（即使是最簡(jiǎn)潔的形式是NP-hard的形式見(jiàn)GAREY和約翰遜，1979），因此實(shí)行的運(yùn)籌學(xué)方式通常被用以簡(jiǎn)化它，為了把它的困難性聽(tīng)從運(yùn)籌學(xué)工具的水平。雖然這一般是一個(gè)特別有效的方法，在LB的特定狀況下，它導(dǎo)致了一些這種無(wú)視現(xiàn)實(shí)世界的問(wèn)題的很多方面問(wèn)題的定義。不幸的是，很多已經(jīng)離開了運(yùn)籌學(xué)方面，實(shí)際在至關(guān)重要的行業(yè)，如汽車，在這個(gè)意義上，任何解決方案忽視（違反）這些方面在使得在同行業(yè)中變得不行用。在下面章節(jié)中，我們先簡(jiǎn)潔回顧一下經(jīng)典運(yùn)籌學(xué)對(duì)LB的定義，然后查看如何面對(duì)行業(yè)不同于他們的實(shí)際生產(chǎn)線平衡問(wèn)題，為什么解決經(jīng)典運(yùn)籌學(xué)問(wèn)題可能無(wú)法運(yùn)用在一些行業(yè)。2生產(chǎn)線平衡的運(yùn)籌學(xué)定義經(jīng)典的運(yùn)籌學(xué)定義的生產(chǎn)線平衡問(wèn)題，被稱為SALBP（簡(jiǎn)潔裝配線平衡問(wèn)題）由貝克爾和紹爾（2004）。特定一組不同期限的任務(wù)，任務(wù)之間的一組優(yōu)先約束和一系列工作站，以這樣一種方式安排給每個(gè)任務(wù)只有一個(gè)工作站，沒(méi)有優(yōu)先約束被違反和安排是最優(yōu)的。最優(yōu)標(biāo)準(zhǔn)產(chǎn)生該問(wèn)題的兩種變型：要么一個(gè)周期時(shí)間是考慮到不能超過(guò)了安排給任何工作站和數(shù)量的全部任務(wù)持續(xù)時(shí)間的總和工作站將被最小化，或工作站的數(shù)量是固定的線周期時(shí)間，等于任務(wù)安排給工作站的持續(xù)時(shí)間的總和最大的，是成為組合最小化。雖然SALBP只考慮兩個(gè)約束條件（任一優(yōu)先級(jí)約束加上循環(huán)時(shí)間，或優(yōu)先約束加的數(shù)量工作站），它是迄今為止生產(chǎn)線平衡的變體，已經(jīng)被探討最多的。我們?cè)贔alkenauer和Delchambre促成了這一努力（1992），在那里我們建議取得一些最好的一個(gè)分組遺傳算法的方法性能的領(lǐng)域。該分組遺傳算法技術(shù)本身已提交具體見(jiàn)Falkenauer（1998）。但是深化探討，SALBP幾乎不適用于工業(yè)，就像我們將看到不久的時(shí)間內(nèi)。事實(shí)上也沒(méi)有逃脫運(yùn)籌學(xué)探討，和貝克爾的關(guān)注和紹爾（2004）定義了很多擴(kuò)展到SALBP，產(chǎn)生了常用的單位GALBP（廣義裝配線平衡問(wèn)題）。每個(gè)擴(kuò)展報(bào)道在他們的權(quán)威調(diào)查旨在處理存在的另一個(gè)真實(shí)世界的生產(chǎn)線平衡困難。我們已經(jīng)通過(guò)采納分組遺傳算法攻克了在Falkenauer（1997）的方面。與大多數(shù)報(bào)道貝克爾和舍爾的方法的主要問(wèn)題（2004）是他們推廣了在短短的一個(gè)或兩個(gè)方向簡(jiǎn)潔SALBP?，F(xiàn)實(shí)世界上生產(chǎn)線平衡，作為汽車行業(yè)所面臨的特殊要求進(jìn)行這些遺傳算法。3在現(xiàn)實(shí)世界中有什么不同？但即使是簡(jiǎn)潔的SALBP是NP-hard的，它是遠(yuǎn)離捕獲真實(shí)的困難性在現(xiàn)實(shí)世界中的化身的問(wèn)題。另一方面，即使小的狀況下的問(wèn)題，他們以最優(yōu)難以解決一個(gè)麻煩的目標(biāo)對(duì)于平衡軟件來(lái)說(shuō)，因?yàn)檫@個(gè)問(wèn)題的小實(shí)例，可以被近似的仿真。但是狀況并非如此，在汽車及相關(guān)行業(yè)（公共汽車，卡車，飛機(jī)，重型機(jī)械等），因?yàn)檫@些行業(yè)的常規(guī)功能有幾十個(gè)或上百個(gè)工作站，以及數(shù)以百計(jì)或數(shù)以千計(jì)的組裝線操作。因此，這些行業(yè)對(duì)生產(chǎn)線平衡軟件的首要市場(chǎng)目標(biāo)。不幸的是，同樣是這些行業(yè)也須要考慮到很多GALBP擴(kuò)展的同時(shí)這也可以說(shuō)明為什么盡管有令人印象深刻的運(yùn)籌平衡所做的工作中，只有好像一個(gè)市場(chǎng)銷售的軟件是目前可用于這些行業(yè)。我們找出下面的一些額外的困難（相對(duì)于SALBP），該必需解決在生產(chǎn)線平衡的工具，以適用于這些行業(yè)。3.1不均衡，但再平衡很多運(yùn)籌學(xué)方法隱含假定要解決的問(wèn)題涉及一個(gè)新的，但將要建的裝配生產(chǎn)線，或者有可能住在一個(gè)新的，但將要建立的工廠。在我們認(rèn)為，這是一個(gè)經(jīng)典的運(yùn)籌學(xué)方法，做最嚴(yán)峻的