工业工程英文文献及外文翻译

《工业工程英文文献及外文翻译》由会员分享，可在线阅读，更多相关《工业工程英文文献及外文翻译（11页珍藏版）》请在装配图网上搜索。

1、附录附录 1：英文文献Line Balancing in the Real WorldAbstract: Line Balancing (LB) is a classic, well-researched Operations Research (OR) optimization problem of significant industrial importance. It is one of those problems where domain expertise does not help very much: whatever the number of years spent so

2、lving it, one is each time facing an intractable problem with an astronomic number of possible solutions and no real guidance on how to solve it in the best way, unless one postulates that the old way is the best way .Here we explain an apparent paradox: although many algorithms have been proposed i

3、n the past, and despite the problem s practical importance, just one commercially availableLB software currently appears to be available for application in industries such as automotive. We speculate that this may be due to a misalignment between the academic LB problem addressed by OR, and the actu

4、al problem faced by the industry.Keyword: Line Balancing, Assembly lines, OptimizationLine Bala ncing in the Real WorldEma nuel Falke nauerOptimal Desig nAv. Jea nne 19A bote2, B-1050 Brussels, Belgium+32 (0)2 646 10 74E.Falke naueroptimaldesig n. com1 In troducti onAssembly Line Balancing, or simpl

5、y 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 some sense. Ever since Henry Ford introduction of assembly lin es, LB has bee n an optimizati on problem of sig nifica nt in dustrial importanee: the

6、efficiency differenee between an optimal and a sub-optimal assig nment can yield econo mies (or waste) reach ing millio ns of dollars per year.LB is a classic Operations Research (OR) optimization problem, having been tackled by OR over several decades. Many algorithms have bee n proposed for the pr

7、oblem. Yet despite the practical importance of the problem, and the OR efforts that have been made to tackle it, little commercially available software is available to help industry in optimizing their lines. In fact, according to a recent survey by Becker and Scholl (2004), there appear to be curre

8、ntly just two commercially available packages featuring both a state of the art optimization algorithm and a user-frie ndly in terface for data man ageme nt.Furthermore, one of those packages appearsto handle only the cleanfdrmulation of the problem (Simple Assembly Line Balancing Problem, or SALBP)

9、, which leaves only one package available for industries such as automotive. This situation appearsto be paradoxical, or at least un expected: give n the huge econo mies LB can gen erate, one would expect several software packages vying to grab a part of those econo mies.It appears that the gap betw

10、een the available OR results and their dissemination in Today industry, is probably due to a misalignment between the academic LB problem addressedby most of the OR approaches,and the actual problem being faced by the industry. LB is a difficult optimization problem even its simplest forms are NP-ha

11、rd - see Garry and Johnson, 1979), so the approach taken 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 general, in the particular case of LB it led some definitions of the problem hat ignore

12、 many aspects of the real-world problem.Unfortun ately, many of the aspects that have bee n left out in the OR approach are in fact crucial to industries such as automotive, in the sense that any solution ignoring (violati ng) those aspects becomes unu sable in the in dustry.In the sequel, we first

13、briefly recall classic OR definitions of LB, and then review how the actual line balancing problem faced by the industry differs from them, and why a solution to the classic OR problem maybe unusable in some industries.2 OR Definitions of LBThe classic OR definition of the line balancing problem, du

14、bbed SALBP (Simple Assembly Line Balancing Problem) by Becker and Scholl (2004), goes as follows. Given a set of tasks of various durations, a set of precedence constraints among the tasks, and a set of workstations, assign each task to exactly one workstation in such a way that no precedence constr

15、aint is violated and the assignment is optimal. The optimality criterion gives rise to two variants of the problem: either a cycle time is given that cannot be exceeded by the sum of durations of all tasks assigned to any workstation and the number of workstations is to be minimized, or the number o

16、f workstations is fixed and the line cycle time, equal to the largest sum of durations of task assigned to a workstation, is to be minimized.Although the SALBP only takes into account two constraints (the precedence constraints plus the cycle time, or the precedenceconstraints plus the number of wor

17、kstations), it is by far the variant of line balancing that has been the most researched. We have contributed to that effort in Falkenauer and Delchambre (1992), where we proposed a Grouping Genetic Algorithm approach that achieved some of the best performance in the field. The Grouping Genetic Algo

18、rithm technique itself was presented in detail in Falkenauer (1998).However well researched, the SALBP is hardly applicable in industry, as we will see shortly. The fact has not escaped the attention of the OR researches, and Becker and Scholl (2004) define many extensions to SALBP, yielding a commo

19、n denomination GALBP (Generalized Assembly Line Balancing Problem). Each of the extensions reported in their authoritative survey aims to handle an additional difficulty present in real-world line balancing. We have tackled one of those aspects in Falkenauer (1997), also by applying the Grouping Gen

20、etic Algorithm.The major problem with most of the approaches reported by Becker and Scholl (2004) is that they generalize the simple SALBP in just one or two directions. The real world line balancing, as faced in particular by the automotive industry, requires tackling many of those generalizations

21、simultaneously.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 instances of the problem, even though they are difficult to solve to optimality, are a trick

22、y target for line balancing software, because small instances 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 machinery, etc.), since those industries routinely feature Assembly lines with doze

23、ns or hundreds of workstations, and hundreds or thousands of Operations. Those industries are therefore the prime targets for line balancing software.Unfortunately, those same industries also need to take into account many of theGALBP extensions at the same time, which may explain why, despite the i

24、mpressive OR Work done on line balancing; only one commercially available software seems tube currently available for those industries.We identify below some of the additional difficulties (with respect to SALBP) that must be tackled in a line balancing tool, in order to be applicable in those indus

25、tries.3.1 Do Not Balance but Re-balanceMany of the OR approachesimplicitly assume that the problem to be solved involves a new, yet-to-be-built assembly line, possibly housed in a new, yet-to-be-built factory. To our opinion, this is the gravest oversimplification of the classic OR approach, for in

26、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 needs tube rebalanced rather than balanced, the need arising from changes in the product or the mix of models being

27、 assembled in the line, the assembly technology, the available workforce, or the production targets. This has some far-reaching implications, outlined below.3.2 Workstations Have IdentitiesAs pointed out above, the vast majority of real-world line balancing tasks involves existing lines housed in ex

28、isting factories. In practice, this seemingly observation has one far-reaching consequence, namely that each workstation in the line does have its own identity. This identity is not due to any inapacity of abstraction on part of the process engineers, but rather to the fact that the workstations are

29、 indeed not identical: each has its own space constraints (e.g. a workstation below a low ceiling cannot elevate the car above the operators its own heavy equipment that cannot be moved spare huge costs, its own capacity of certain supplies (e.g. compressed air), its own restrictions on the operatio

30、ns that can be carried out there (e.g. do not place welding operations just beside the painting shop), etc.3.3 Cannot Eliminate WorkstationsSince workstations do have their identity (as observed above), it becomes obvious that a real-world LB tool cannot aim at eliminating workstations. Indeed, unle

31、ss the eliminated workstations were all in the front of the line or its tail, their elimination would create gaping holes in the line, by virtue of the other workstations of their identities, including their geographical positions in the workshop. Also, it softens the case that many workstations tha

32、t could possibly be eliminated by the algorithm are in fact necessary because of zoning constraints.4 ConclusionsuninteheadretaiThe conclusions inspection 3 stems from our extensive contacts with automotive and related industries, and reflects their true needs. Other exotic II constraints may apply

33、in any given real-world assembly line, but line balancing tool for those industries must be able to handle at least those aspects of the problem. This is very far from the clean II academic SALBP, as well as most GALBPoeXt reported by Becker and Scholl (2004). In fact, such a tool must simultaneousl

34、y solve several-hard problems:? Find a feasible defined replacement for all undefined (?ANY )ergonomic con stra in ts on workstati on s, i.e. One compatible with the ergono mic con stra in ts a nd precedenceconstraints defined on operations, as well as zoning constraints and possible drifting operat

35、i ons? Solve the within-workstation scheduling problem on all workstations, for all products being assembled on the line? Assign the operations to workstations to achieve the best average balance, while keep ing the peak times at a man ageable level. Clearly, the real-world line balancing problem de

36、scribed above is extremely difficult to solve. This is compo un ded byte size of the problem encoun tered in the target in dustries, which routi nely feature assembly lines with doze ns or hun dreds of workstatio ns with multiple operators, and hun dreds or thousa nds of operati ons.We ve identified

37、 a number of aspects of the line balancing problem hat are vital in industries such as automotive, yet that have been either neglected in the OR work on the problem, or han dled separately from each other. Accord ing to our experie nce, a line bala ncing to applicable in those in dustries must be ab

38、le to han dle all of them simulta neously. That gives rise to an extremely complex optimizati on problem.The complexity of the problem, and the need to solve it quickly, may explain why there appears to be just one commercially available software for solving it, namely outline by Optimal Design. Mor

39、e information on Outline, including its rich graphic user in terface, is available atnttp:/www.optimaldesig n. com/OptiLi ne/OptiLi ne.htm .Refere nces1 Becker C. and Scholl, A. (2004) A survey on problems and methods in generalized assemblyline balancing, European Journal of Operations Research,in

40、press. Available online at http:/dx.doi.org/doi:10.1016/j.ejor.2004.07.023. Journal article.2 Falkenauer, E. and Delchambre, A. (1992) Genetic Algorithm for Bin Packing and Line Balancing, Proceedingsof the 1992 IEEE International Conference on Robotics and Automation, May10-15, 1992, Nice, France.

41、IEEE Computer Society Press, Los Alamitos, CA. Pp. 1186-1192. Co nference proceedi ngs.3 Falkenauer, E. (1997) A Grouping Genetic Algorithm for Line Balancing with Resource Dependent Task Times, Proceedings of the Fourth International Conference on Neural Information Processing (ICONIP 97)University

42、 of Otego, Dunedin, New Zealand, November 24-28, 1997. Pp. 464-468. Conference proceed in gs.4 Falkenauer, E. (1998) Genetic Algorithms and Grouping Problems, John Wiley& Sons, Chi Chester, UK. Book.5 Gary. R. and Joh nson D. S. (1979) Computers and In tractability - A Guide to the Theory of NP-comp

43、lete ness, W.H.Freema n Co., San Fran cisco, USA. Book.附录 2：中文文献生产线平衡在现实世界摘要：生产线平衡(LB )是一个经典的，精心研究的显著工业重要性的运筹学(OR)优化问题。这是其中一个所在领域的专业知识并没有太大帮助的问题之 一：无论花了多少年解决它，面对每一次棘手的问题与可能的天文数字的解决 方案都并不是关于如何解决这个问题的最好办法，除非你假定老办法是最好的 办法。在这里，我们解释一个明显的悖论： 虽然很多算法已经被提出， 在过去， 尽管该问题的实际重要性只是一个市场销售的 LB 软件。目前似乎可用于工业， 如汽车中的应用。

44、我们推测，这可能是由于在学术 LB 问题之间的没有通过运 筹学路径和生产业实际面对的问题。关键词 ：生产线平衡，装配生产线，优化生产线平衡在现实世界伊曼纽尔 福肯奈尔优化设计地址：珍妮大道 19A，2 道， B-1050 布鲁塞尔，比利时+32（0）2 646 10 74E.Falkenauer1 引言 装配线平衡，或者简称生产线平衡（ LB ），是一个操作工作站沿着装配线 分配的问题，在这样一种方式，该分配是在某种意义上最优的。自从亨利?福特引进组装生产线， LB 已经成为影响工业重要性的最优化问题：在效率不同的 最优和次优分配之间的差异可以产生经济（或浪费）达到数百万美元每年。LB是一个经

45、典的运筹学（OR）的优化问题，已通过被运筹学解决达以上几十 年。许多算法已经被提出了去解决这个问题。尽管问题的有实际重要性，并已 经取得了或努力，但很少的商业软件是可以帮助行业优化其生产线。事实上， 根据最近贝克尔和绍尔（ 2004）的一项调查显示，似乎有目前只有两个市场销 售的软件包有特色，即是最先进的优化算法的状态和数据管理的用户友好的界 面。此外，这些软件包，似乎只处理 -干净 的提法的问题（简单装配线平衡问 题，或SALBP）,这让只有一个软件包可用于工业，如汽车业。这种情况似乎 是自相矛盾的，或者至少是意想不到的：给定的 LB 可以产生的巨大经济，人 们能够所期望的几个软件包争先恐后

46、地抓住这些经济体的一部分。看来，现有的运筹学结果以及它们在传播之间存在差距。当今的工业，很 可能是由于在学术 LB 问题之间通过运筹学大多数的或接近解决，对于企业所 面对的实际问题。 LB 是一个困难的优化问题（即使是最简单的形式是 NP-hard 的形式见 GAREY 和约翰逊， 1979），因此采取的运筹学方式通常被用以简化它， 为了把它的复杂性服从运筹学工具的水平。 虽然这一般是一个非常有效的方法， 在 LB 的特定情况下，它导致了一些这种无视现实世界的问题的许多方面问题 的定义。不幸的是，许多已经离开了运筹学方面，实际在至关重要的行业，如 汽车，在这个意义上，任何解决方案忽略（违反）这

47、些方面在使得在同行业中 变得不可用。在下面章节中，我们先简单回顾一下经典运筹学对 LB 的定义，然后查看 如何面对行业不同于他们的实际生产线平衡问题，为什么解决经典运筹学问题 可能无法使用在一些行业。2 生产线平衡的运筹学定义经典的运筹学定义的生产线平衡问题，被称为 SALBP （简单装配线平衡问 题）由贝克尔和绍尔（ 2004）。特定一组不同期限的任务，任务之间的一组优先 约束和 一系列工作站， 以这样一种方式分配给每个任务只有一个工作站， 没有 优先约束被违反和分配是最优的。最优标准产生该问题的两种变型：要么一个 周期时间是考虑到不能超过了分配给任何工作站和数量的所有任务持续时间的 总和工

48、作站将被最小化，或工作站的数量是固定的线周期时间，等于任务分配 给工作站的持续时间的总和最大的，是成为组合最小化。虽然 SALBP 只考虑两个约束条件 （任一优先级约束加上循环时间， 或优先 约束加的数量工作站） ，它是迄今为止生产线平衡的变体，已经被研究最多的。 我们在Falkenauer和Delchambre促成了这一努力（1992），在那里我们建议取 得一些最好的一个分组遗传算法的方法性能的领域。 该分组遗传算法技术本身 已提交详细见 Falkenauer（ 1998）。但是深入研究， SALBP 几乎不适用于工业，就像我们将看到不久的时间 内。事实上也没有逃脱运筹学研究，和贝克尔的关注

49、和绍尔（ 2004）定义了许多扩展到SALBP，产生了常用的单位 GALBP （广义装配线平衡问题）。每个 扩展报道在他们的权威调查旨在处理存在的另一个真实世界的生产线平衡困难。 我们已经通过采用分组遗传算法攻克了在Falkenauer （1997）的方面。与大多数报道贝克尔和舍尔的方法的主要问题（2004）是他们推广了在短短的一个或两个方向简单SALBP。现实世界上生产线平衡，作为汽车行业所面临的特别要 求进行这些遗传算法。3 在现实世界中有什么不同？但即使是简单的 SALBP 是 NP-hard 的，它是远离捕捉真实的复杂性在现实 世界中的化身的问题。另一方面，即使小的情况下的问题，他们以

50、最优难以解 决一个棘手的目标对于平衡软件来说，因为这个问题的小实例，可以被近似的 仿真。但是情况并非如此，在汽车及相关行业（公共汽车，卡车，飞机，重型 机械等），因为这些行业的常规功能有几十个或上百个工作站， 以及数以百计或 数以千计的组装线操作。因此，这些行业对生产线平衡软件的首要市场目标。不幸的是，同样是这些行业也需要考虑到很多 GALBP 扩展的同时这也可 以解释为什么尽管有令人印象深刻的运筹平衡所做的工作中，只有似乎一个市 场销售的软件是目前可用于这些行业。 我们找出下面的一些额外的困难 （相对 于 SALBP ），该必须解决在生产线平衡的工具，以适用于这些行业。3.1 不均衡，但再平

51、衡许多运筹学办法隐含假定要解决的问题涉及一个新的，但将要建的装配生 产线，或者有可能住在一个新的，但将要建造的工厂。在我们认为，这是一个 经典的运筹学方法，做最严重的简单化。实际上，这是很少的情况下。真实世 界的生产线平衡任务的绝大多数涉及到现有的生产线， 安置在现有的工厂 -事实 上，目标线通常需要重新排列而非均衡，从变化的产物所产生的需要或混合车 型组装的线，组装技术，可用劳动力或生产目标。这有一些深远的影响，下文 将以概述。3.2 工作站有身份正如上面所指出的，真实世界的生产线平衡任务的绝大多数涉及安置在现 有工厂现有生产线。在实践中，这种看似 -不感兴趣I观察有一个深远的后果， 即在该

52、行的每个工作站确实有其自己的身份。 这个身份是该工艺工程师的一部 分不因为任何丧失工作能力。而事实是，即工作站确实不相同的：每个人都有 自己的间限制（如工作站低于低天花板不能提升车子超过操作者的头） ，其自身 的重型设备，因为成本可以不移动备用巨大的，其自身的某些物资的能力（如压缩空气），其对可以在那里进行的操作的限制（例如，不要把焊操作只是旁边 的涂装车间）等。3.3 不能消除工作站由于工作站也有自己的身份（如上述观察） ，它变得明显，一个真实世界的 LB 工具无法旨在消除工作站。事实上，除非淘汰的工作站都在该行或它的末尾 的前面，他们的淘汰会造成张开的线孔，凭借他们的身份和其他工作站的补充

53、， 在车间的地理位置。此外，它通常的情况是许多工作站可能会因该算法被淘汰， 其实是必要的由于区划的限制。4 结论在第三部分的结论中从我们与广泛接触的汽车和相关行业，并反映他们的 真实需求。其他的限制可能适用于任何给定的现实世界的流水线，而一个生产 线平衡工具，必须能够处理这些行业问题中的至少那些方面。 这是从很远的干 净”学术SALBP，以及所报告的贝克尔和舍尔最 GALBP扩展（2004）。事实 上，这样的工具必须同时解决几个 NP 难问题： ?寻找一个可行的定义替换所有未定义人体工程学在工作站上的限制，即，一个 兼容的人体工程学限制和操作上的优化定义约束，以及区划的限制和可能的漂 移操作

54、?解决了在工作站调度问题上的所有工作站，对所有在装配线上组装的产品 ?将操作工作站，以达到最佳的平均余额，同时保持高峰时间在一个可控的水平。显然，上面描述的现实世界的生产线平衡的问题是极为困难解决。 这是由 该问题的目标中遇到的行业问题大小不同，其中经常设有数十个或数百个组装 线工作站与多个运营商。我们已经确定了一些在生产线平衡问题，如在汽车业这是非常重要的方面， 但已不是忽略了运筹学工作在问题上的作用。根据我们的经验，一个线平衡适 用于这些行业工具必须能够处理这些问题。 这产生了一个极其复杂的优化问题。 该问题的复杂性，以及需要解决它的迫切性，也许可以解释为什么不只能通过 一个商业软件来解决

55、它，即通过优化设计 OPTILINE 。你可以上 OPTILINE 了 解更多信息，包括其丰富的图形的用户界面。 。参考文献1 Becker C. and Scholl, A. (2004)普通装配线平衡问题方法研究，欧洲运筹学 年刊，在线观看 http:/dx.doi.Org/doi:10.1016/j.ejor.2004.07.023. Journal article.2 Falke nauer, E. and Delchambre, A. (1992)遗传算法在生产线平衡和处理应用，1992年IEEE国际自动化和工业会议，五月10-15, 1992,法国IEEE电脑出版协会,Los Alamitos, CA. Pp 1186-1192.3 Falke nauer, E. (1997)基于资源任务时间的遗传算法在生产线平衡中应用发表在第四次国际信息进程大会。渥太渥大学，新西兰11月24-28, 1997.页数464-4684 Falke nauer, E. (1998)遗传算法和群体问题，Joh n Wiley & So ns, Chichester, 英国5 GareyM. R. and Johnson D. S. (1979)电脑和技术一NP 理论导论 W.H.Freema n Co., San Fran cisco 美国