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

1、附錄附錄1英文文獻(xiàn)Li ne Bala ncing in the Real WorldAbstract：Li neBala ncing (LB) is a classic, well-researchedOperati ons Research (OR) optimizati on problem of sig nifica ntin dustrialimporta nee. It is one of those problems where doma in expertise does not help very much: whatever the nu mber of years spe

2、 nt sol ving it, one is each time facing an in tractable problem with an astro no mic nu mber of possible solutions and no real guidance on how to solve it in the best way, uni ess one postulates that the old way is the best way .Here we expla in an appare nt paradox: although many algorithms have b

3、ee n proposed in the past, and despite the problem ' s practical importance, just one commercially available LB software currently appears to be available for application in industries such as automotive. Wespeculate that this may be due to a misalig nment betwee n the academic LB problem addres

4、sed byOR, and the actual problem faced by the in dustry.Keyword： Li ne Bala ncing, Assembly lin es, Optimizatio nLine Bala ncing in the Real WorldEma nuel Falke nauer Optimal Desig nAv. Jeanne 19A bo ? te2, B-1050 Brussels, Belgium+32 (0)2 646 10 74E.Falke naueroptimaldesig n. com1 In troducti onAss

5、embly Line Balancing, or simply Line Balancing (LB), is the problem of assigning operations to workstations along an assembly line, in such a way that the assignment be optimal in somesense. Ever since Henry Ford' s introduction of assembly lines, LB has been an optimization problem of sig nific

6、a ntin dustrialimporta nee: the efficie ncydiffere nee betwee nan optimal and a sub-optimal assig nment can yield econo mies (or waste) reaching millions of dollars per year.LB is a classic Operations Research (OR) optimizationproblem, havingbee n tackled by OR over several decades. Many algorithms

7、have bee n proposed for the problem. Yet despite the practical importa nee of the problem, and the OR efforts that have been made to tackle it, little commercially available software is available to help in dustryinoptimizing their lines.In fact, according to a recent survey by Beckerand Scholl (200

8、4), there appear to be currently just two commercially available packages featuring both a state of the art optimization algorithm and a user-frie ndlyin terface for data man ageme nt. Furthermore,one of those packages appears to handle only the“ clean ” formulationof the problem (Simple Assembly Li

9、ne Balancing Problem, or SALBP), which leaves only one package available for industries such as automotive. This situati on appears to be paradoxical, or at least un expected: give n the huge econo mies LB can gen erate,one would expect several softwarepackages vying to grab a part of those econo mi

10、es.It appears that the gap between the available OR results and their dissemination in Today ' s industry, is probably due to a misalignment between the academic LB problem addressed by most of the OR approaches, and the actual problem being faced by the in dustry. LB is a difficult optimizati o

11、n problem eve n its simplest forms are NP-hard see Garryand Joh nson ,1979), so the approach take n by OR has typically bee n to simplify it, i n order to bring it to a level of complexity ame nable to OR tools. While this is a perfectly valid approach in gen eral, i n the particular case of LB it l

12、ed some definitions of the problem hat ignore many aspects of the real-world problem.Unfortunately, many of the aspects that have been left out in the OR approach are in fact crucial to industries such as automotive, in the sense that any solutionignoring (violating) those aspects becomesunu sable i

13、n the in dustry.In the sequel, we first briefly recall classic OR definitions of LB,and the n review how the actual li ne bala ncing problem faced by theindustry differs from them, and why a solution to the classic ORproblem maybe unu sable in some in dustries.2 OR Defini tio ns of LBThe classic ORd

14、efinitionof the line balancing problem, dubbed SALBP(Simple Assembly Line Balancing Problem) by Becker and Scholl (2004), goes as follows. Give n a set of tasks of various durati ons, a set of precede nee con stra intsamon gthe tasks, and a set of workstati ons, assig neach task to exactly one works

15、tati on in such a way that no precede nee constraint is violated and the assignment is optimal. The optimality criteriongives rise to two variants of the problem: either a cycle timeis give n that cannot be exceeded by the sum of durati ons of all tasks assig ned to any workstati on and the nu mber

16、of workstati ons is to beminimized, or the numberof workstations is fixed and the line cycle time, equal to the largest sum of durations of task assigned to a workstation, is to be mi ni mized.Although the SALBP on ly takes in to acco unt two con strai nts(theprecede nee con stra intsplus the cycle

17、time, or the precede neeconstraints plus the number of workstations), it is by far the variant of line balancing that has been the most researched. Wehave contributed to that effort in Falke nauer and Delchambre (1992), where we proposed a Group ing Gen etic Algorithm approach that achieved some of

18、the best performanee in the field. The Grouping Genetic Algorithm technique itself was presented in detail in Falkenauer (1998).However well researched, the SALBP is hardly applicable in in dustry, as we will see shortly. The fact has not escaped the attention of the OR researches, and Becker and Sc

19、holl (2004) defi ne many exte nsions to SALBP, yieldi ng a com mon denomin ati on GALBP (Ge neralized Assembly Li ne Bala ncing Problem). Each of the exte nsions reported in their authoritative survey aims to handle an additional difficultypresent inreal-world line bala ncing. We have tackled one of

20、 those aspects in Falke nauer (1997), also by appl ying the Group ing Gen etic Algorithm.The major problem with most of the approaches reported by Becker andScholl (2004) is that they generalize the simple SALBP in just one or two direct ions. The real world line bala ncing, as faced in particular b

21、y the automotiveindustry,requirestacklingmany of thosegen eralizati ons simulta neously.3 What Differs in the Real World?Although even the simple SALBP is NP-hard, it is far from capturing the true complexity of the problem in its real-world incarnations. On the other hand, small in sta nces of the

22、problem, eve n though they are difficult to solve to optimality, are a tricky target for line balancing software, because small in sta nces of the problem can be solved closet optimality by hand. That is however not the case in the automotive and related industries(Bus, truck, aircraft, heavy machin

23、ery, etc.), sincethose in dustriesrouti nely feature Assembly lines with doze ns orhundreds of workstations, and hundreds or thousands of Operations. Those industries are therefore the prime targets for line balancing software.Unfortun ately, those same in dustries also n eed to take into acco unt m

24、any of the GALBP extensions at the same time, which may explain why, despite the impressive OR Work done on linebalancing;only onecommercially available software seemstube currently available for those in dustries.We ide ntify below some of the additi onal difficulties (with respect to SALBP) that m

25、ust be tackled in a line balancing tool, in order to be applicable in those in dustries.3.1 Do Not Balance but Re-balanceMany of the OR approaches implicitly assume that the problem to be solved invo Ives a n ew, yet-to-be-built assembly line, possibly housed in a n ew, yet-to-be-built factory. To o

26、ur opinion, this is the gravest oversimplification of the classic ORapproach, for in practice, this is hardly ever the case. The vast majority of real-world line bala ncing tasks invo Ive exist ing lin es, housed in exist ing factories infect,the target line typically n eeds tube rebala need rather

27、tha n bala need, the n eed aris ing from cha nges in the product or the mix of models being assembled in the line, the assemblytech no logy,the availableworkforce, or the productiontargets. This has some far-reachingimplicati ons, outl ined below.3.2 Workstatio ns Have Ide ntitiesAs pointed out abov

28、e, the vast majority of real-world line balancing tasks invoIves existing lines housed in existing factories. In practice, this seem in gly “ unin teresti ng ” observatio n has one far-reachi ng consequence, namely that each workstation in the line does have its own iden tity. This ide ntityis not d

29、ue to any “ in capacity of abstracti on ”on part of the process engineers,but rather to the fact that theworkstati ons are in deed not ide ntical: each has its own space con strai nts (e.g. a workstationbelow a low ceiling cannot elevate the car above theoperators ' heads), its own heavy equipme

30、nt that cannot be moved spare huge costs, its own capacity of certain supplies (e.g. compressed air), its own restrict ionson the operati ons that can be carried out there (e.g.do not place weldi ng operati ons just beside the painting shop), etc.3.3 Cannot Elimi nate Workstati onsSince workstati on

31、s do have their ide ntity (as observed above), it becomes obvious that a real-world LB tool cannot aim at eliminating workstati ons.In deed, uni ess the elimi nated workstati ons were all in thefront of the line or its tail, their eliminationwould create gaping holesin the line, by virtue of the oth

32、er workstati ons' retai ning of theiriden tities,in cludi ng their geographical positi ons in the workshop. Also,it softens the case that many workstations that could possibly be elimi nated by the algorithm are in fact n ecessary because of zoning con strai nts.4 Con clusi onsThe con clusi ons

33、in specti on 3 stems from our exte nsive con tacts with automotive and related industries, and reflects their true needs. Other “ exotic ” constraintsmay apply in any given real-world assembly line,but line bala ncing tool for those in dustries must be able to han dle at least those aspects of the p

34、roblem. This is very far from the “clean ” academic SALBP, as well as most GALBP exte nsions reported by Becker and Scholl (2004). In fact, such a tool must simultaneously solve several-hard problems:? Find a feasible defined replacement for all undefined ( ANY )ergono mic con stra ints on workstati

35、 on s, i.e. One compatible with the ergono mic con strai nts and precede nee con strai ntsdefi ned on operati ons,as well as zoning con stra ints and possible drift ing operati ons? Solve the within-workstationscheduling problem on allworkstations, for all products being assembled on the line? Assig

36、n the operations to workstations to achieve the best average bala nee, while keep ing the peak times at a man ageable level. Clearly, the real-worldlinebalancing problem described above is extremelydifficult to solve.This is compounded byte size of the problemencoun tered in the target in dustries,

37、which routi nely feature assembly lines with doze ns or hun dreds of workstati ons with multiple operators, and hun dreds or thousa nds of operati ons.We ve identified a number of aspects of the line balancing problem that are vital in industries such as automotive, yet that have been either neglect

38、ed in the ORwork on the problem, or handled separately from each other. Accord ing to our experie nee, a line bala ncing to applicable in those industries must be able to handle all of them simultaneously.Thatgives rise to an extremely complex optimizati on problem.The complexity of the problem, and

39、 the need to solve it quickly, may explain why there appears to be just one commercially available software for sol ving it, n amely outl ine by Optimal Desig n. More in formati on onOutli ne, in clud ing its rich graphic user in terface, is available at ne/OptiLi ne.htmRefere nces1 Becker C. and Sc

40、holl, A. (2004) 'A survey on problems and methods ingen eralized assemblyli ne bala ncin g', Europea n Jour nal of Operati ons Research,inpress.Availableon li neat. Journal article.2 Falkenauer, E. and Delchambre, A. (1992) 'Genetic Algorithm for BinPacking and Line Balancing', Proce

41、edingsof the 1992 IEEE InternationalConference on Robotics and Automation, May10-15, 1992, Nice, France.IEEE Computer Society Press, Los Alamitos, CA. Pp. 1186-1192. Conference proceed in gs.3 Falkenauer,E. (1997) 'A Grouping Genetic Algorithm for LineBalancing with Resource Dependent Task Times

42、', Proceedings of the Fourth InternationalConference on Neural Information Processing (ICONIP' 97),Un iversity of Otego, Dun edi n, New Zeala nd, November 24-28, 1997. Pp. 464-468. Conference proceed in gs.4 Falkenauer,E. (1998) Genetic Algorithms and Grouping Problems, JohnWiley& Sons,

43、Chi Chester, UK. Book.5 Gary. R. and Joh nson D. S. (1979) Computers and In tractability - AGuide to the Theory of NP-complete ness, W.H.Freema nCo., San Fran cisco, USA. Book.附錄2:中文文獻(xiàn)生產(chǎn)線(xiàn)平衡在現(xiàn)實(shí)世界摘要：生產(chǎn)線(xiàn)平衡（LB）是一個(gè)經(jīng)典的，精心研究的顯著工業(yè)重要性的運(yùn)籌學(xué)（OR優(yōu)化問(wèn)題。這是其中一個(gè)所在領(lǐng)域的專(zhuān)業(yè)知識(shí)并沒(méi)有太大幫助的問(wèn)題之 一：無(wú)論花了多少年解決它，面對(duì)每一次棘手的問(wèn)題與可能的天文數(shù)字的解決 方

44、案都并不是關(guān)于如何解決這個(gè)問(wèn)題的最好辦法，除非你假定老辦法是最好的 辦法。在這里，我們解釋一個(gè)明顯的悖論：雖然很多算法已經(jīng)被提出，在過(guò)去, 盡管該問(wèn)題的實(shí)際重要性只是一個(gè)市場(chǎng)銷(xiāo)售的 LB軟件。目前似乎可用于工業(yè)， 如汽車(chē)中的應(yīng)用。我們推測(cè)，這可能是由于在學(xué)術(shù)LB問(wèn)題之間的沒(méi)有通過(guò)運(yùn)籌 學(xué)路徑和生產(chǎn)業(yè)實(shí)際面對(duì)的問(wèn)題。關(guān)鍵詞：生產(chǎn)線(xiàn)平衡，裝配生產(chǎn)線(xiàn)，優(yōu)化生產(chǎn)線(xiàn)平衡在現(xiàn)實(shí)世界伊曼紐爾?？夏螤杻?yōu)化設(shè)計(jì)地址：珍妮大道19A, 2道，B-1050布魯塞爾，比利時(shí)+32（ 0）2 646 10 74E.Falke naueroptimaldesig n. com1引言裝配線(xiàn)平衡，或者簡(jiǎn)稱(chēng)生產(chǎn)線(xiàn)平衡（LB）,

45、是一個(gè)操作工作站沿著裝配線(xiàn)分配的問(wèn)題，在這樣一種方式，該分配是在某種意義上最優(yōu)的。自從亨利？福特引進(jìn)組裝生產(chǎn)線(xiàn)，LB已經(jīng)成為影響工業(yè)重要性的最優(yōu)化問(wèn)題：在效率不同的 最優(yōu)和次優(yōu)分配之間的差異可以產(chǎn)生經(jīng)濟(jì)（或浪費(fèi)）達(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)線(xiàn)。事實(shí)上，根據(jù) 最近貝克爾和紹爾（2004）的一項(xiàng)調(diào)查顯示，似乎有目前只有兩個(gè)市場(chǎng)銷(xiāo)售的 軟件包有特色，即是最先進(jìn)的優(yōu)化算法的狀態(tài)和數(shù)據(jù)管理的用戶(hù)友好的界面。 此外，這

46、些軟件包，似乎只處理“干凈”的提法的問(wèn)題（簡(jiǎn)單裝配線(xiàn)平衡問(wèn)題， 或SALBP，這讓只有一個(gè)軟件包可用于工業(yè)，如汽車(chē)業(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)GARE和約翰遜，1979），因此采取的運(yùn)籌學(xué)方式通常被用以簡(jiǎn)化它，為了把它的復(fù)雜性服從運(yùn)籌學(xué)工具的水平。雖然這一

47、般是一個(gè)非常有效的方法， 在LB的特定情況下，它導(dǎo)致了一些這種無(wú)視現(xiàn)實(shí)世界的問(wèn)題的許多方面問(wèn)題的 定義。不幸的是，許多已經(jīng)離開(kāi)了運(yùn)籌學(xué)方面，實(shí)際在至關(guān)重要的行業(yè)，如汽 車(chē)，在這個(gè)意義上，任何解決方案忽略（違反）這些方面在使得在同行業(yè)中變 得不可用。在下面章節(jié)中，我們先簡(jiǎn)單回顧一下經(jīng)典運(yùn)籌學(xué)對(duì) LB的定義，然后查看如 何面對(duì)行業(yè)不同于他們的實(shí)際生產(chǎn)線(xiàn)平衡問(wèn)題，為什么解決經(jīng)典運(yùn)籌學(xué)問(wèn)題可 能無(wú)法使用在一些行業(yè)。2生產(chǎn)線(xiàn)平衡的運(yùn)籌學(xué)定義經(jīng)典的運(yùn)籌學(xué)定義的生產(chǎn)線(xiàn)平衡問(wèn)題，被稱(chēng)為SALBP（簡(jiǎn)單裝配線(xiàn)平衡問(wèn)題）由貝克爾和紹爾（2004）。特定一組不同期限的任務(wù)，任務(wù)之間的一組優(yōu)先 約束和一系列工作站，以

48、這樣一種方式分配給每個(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ù)量是固定的線(xiàn)周期時(shí)間，等于任務(wù)分配 給工作站的持續(xù)時(shí)間的總和最大的，是成為組合最小化。雖然SALBP只考慮兩個(gè)約束條件（任一優(yōu)先級(jí)約束加上循環(huán)時(shí)間，或優(yōu)先 約束加的數(shù)量工作站），它是迄今為止生產(chǎn)線(xiàn)平衡的變體，已經(jīng)被研究最多的。 我們?cè)贔alkenauer和Delchambre促成了這一努力（1992），在那里我們建議取 得一些最好的一個(gè)分組遺傳算法的方法性能的領(lǐng)域。該分組遺傳算

49、法技術(shù)本身已提交詳細(xì)見(jiàn)Falkenauer （ 1998）。但是深入研究，SALBP幾乎不適用于工業(yè)，就像我們將看到不久的時(shí)間內(nèi)。 事實(shí)上也沒(méi)有逃脫運(yùn)籌學(xué)研究，和貝克爾的關(guān)注和 紹爾（2004）定義了許多擴(kuò) 展到SALBP產(chǎn)生了常用的單位GALBP（廣義裝配線(xiàn)平衡問(wèn)題）。每個(gè)擴(kuò)展報(bào)道 在他們的權(quán)威調(diào)查旨在處理存在的另一個(gè)真實(shí)世界的生產(chǎn)線(xiàn)平衡困難。我們已 經(jīng)通過(guò)采用分組遺傳算法攻克了在 Falkenauer（ 1997）的方面。與大多數(shù)報(bào)道 貝克爾和舍爾的方法的主要問(wèn)題（2004）是他們推廣了在短短的一個(gè)或兩個(gè)方向簡(jiǎn)單SALBP現(xiàn)實(shí)世界上生產(chǎn)線(xiàn)平衡，作為汽車(chē)行業(yè)所面臨的特別要求進(jìn)行 這些遺傳算法

50、。3在現(xiàn)實(shí)世界中有什么不同？但即使是簡(jiǎn)單的SALBP是NP-hard的，它是遠(yuǎn)離捕捉真實(shí)的復(fù)雜性在現(xiàn)實(shí) 世界中的化身的問(wèn)題。另一方面，即使小的情況下的問(wèn)題，他們以最優(yōu)難以解 決一個(gè)棘手的目標(biāo)對(duì)于平衡軟件來(lái)說(shuō)，因?yàn)檫@個(gè)問(wèn)題的小實(shí)例，可以被近似的 仿真。但是情況并非如此，在汽車(chē)及相關(guān)行業(yè)（公共汽車(chē)，卡車(chē)，飛機(jī)，重型 機(jī)械等），因?yàn)檫@些行業(yè)的常規(guī)功能有幾十個(gè)或上百個(gè)工作站，以及數(shù)以百計(jì)或數(shù)以千計(jì)的組裝線(xiàn)操作。因此，這些行業(yè)對(duì)生產(chǎn)線(xiàn)平衡軟件的首要市場(chǎng)目標(biāo)。不幸的是，同樣是這些行業(yè)也需要考慮到很多 GALBPT展的同時(shí)這也可以 解釋為什么盡管有令人印象深刻的運(yùn)籌平衡所做的工作中，只有似乎一個(gè)市場(chǎng) 銷(xiāo)售的軟件是目前可用于這些行業(yè)。我們找出下面的一些額外的困難 （相對(duì)于SALBP，該必須解決在生產(chǎn)線(xiàn)平衡的工具，以適用于這些行業(yè)。3.1不均衡，但再平衡許多運(yùn)籌學(xué)辦法隱含假定要解決的問(wèn)題涉及一個(gè)新的，但將要建的裝配生 產(chǎn)線(xiàn)，或者有可能住