1、 本科毕业论文外文翻译 外文译文题目 ： 对于 E 类型的简单生产线平衡问题的解决过程 学 院 : 机械自动化 专 业 : 工业工程 学 号 : 201003166078 学生姓名 : 谭柱森 指导教师 : 李颖 日 期 : 二一四年五月 武汉科技大学本科毕业论文外文翻译 A solution procedure for type E simple assembly line balancing problem Nai-Chieh Wei , I-Ming Chao Industrial Engineering and Management， I-Shou University, No. 1,
2、 Section 1, Syuecheng Rd. Dashu District, Kaohsiung City 84001, Taiwan, ROC. 对于 E 类型的简单生产线平衡问题的解决过程 Nai-Chieh Wei , I-Ming Chao 工业工程与管理，中华人民共和国，台湾省，高雄市，Syuecheng Rd. Dashu街一号， 义守大学 ，第一章第一节 武汉科技大学本科毕业论文外文翻译 1 摘要 本文提出了结合 SALBP-1和 SALBP-2的 E型简单装配线平衡问题（ SALBP-E），更多的，本研究为提出的模型提供了解决方法。提出的模型在最小化空闲时间的同时优化装配
3、线平衡率，为管理实践提供了更好的理解，计算结果表明：给出周期的上限 maxct 以后，提出的模型可以最优的解决问题，因为它含有最少的变量，约束和计算时间。 1前言 从研究者第一次讨论装配线平衡问题以来，大约有 50年了，在众多 有关生产线平衡问题中，最基本的是简单装配线平衡问题，早在 1954年， Bryton就定义并且研究了生产线平衡问题。后一年， Salverson建立了第一个生产线平衡的数学模型并提出了定性的解决步骤，这引来了很大的兴趣，在 Gutjahr 和 Nemhauser说明生产线平衡是一种 NP组合优化难题，大多数研究者希望开发一种能高效解决多种装配线问题的方法。在随后的几年
4、,生产线平衡成为了一个流行的主题， Kim, Kim, and Kim (1996) 把生产线平衡分为五类问题，其中的问题 1（ SALBP-1）和问题 (SALBP- )是两种基本的优化问题。 研究者发表了许多有关解决 SALBP-1问题的研究结果， Salverson（ 1995）用整数规划解决工作站分配问题， Jackson用动态规划解决 SALBP-1， Bowman提出了两种数学模型并引入了 0-1变量保证没有不同任务占用同一时间且同一任务不被分配到不同的工作站。 Talbot 和 Patterson (1984)提出了一个数学模型，它还有一个单一变量，专门用来计量分配到工作站的任务
5、数量， Essa, Delorme, Dolgui, 和 Guschins-kaya (2010) 提出了一个解决由相同的数控机床构成的线平衡问题的混合整数规划模型， Hack-man, Magazine, and Wee (1989)使用分支定界法解决了 SALBP-1，为了减小分支的数量，他们提出了启发式深度测量技术，提供了一个高效率的方法， Betts and Mahmoud (1989), Scholl and Klein(1997, 1999), Ege, Azizoglu, and Ozdemirel (2009)建议实施分支定界法，其他的启发式方法已经被用来解决多种问题，这些包括
6、模 拟退火算法 (Cakir, Altiparmak, Saeid Suresh Sabuncuoglu, Erel, Simaria & Vilarinho,2009)，现今，随着顾客多样化需求的出现，多目标问题产生了。例如， Rahimi-Vahed和 Mirzaei (2007)提出了一种混合多目标算法，包括总效用工作最小化，总生产速率变化最小化、总过程成本最小化。 Chica, Cordon, and Damas (2011)提出了一种模型，包含一系列具有冲突目标的联合优化，这些冲突目标包括周期、工作站数目、工作站数目的面积等。另一个有趣的延伸是混合模型问题，这是装配线平衡的一个特殊的
7、例子，它允许不同型号的产品在同一生产武汉科技大学本科毕业论文外文翻译 2 线上流动。为了解决混合模型装配线平衡问题， Erel和 Gken (1999)对混合模型装配线进行了研究并且建立了 0-1整数规划模型和结合顺 序图以减少决策变化和解决侠侣增长的约束条件 。 Kim 和 Jeong (2007)使用包含依赖于序列的准备时间的运输系统解决了混合模型装配线平衡中工作输入队列的优化问题。 zcan and Toklu (2009) 提出了一个数学模型，用来解决混合模型的双边装配线平衡问题，目标是解决成对工作站和已知周期的工作站数目的优化问题。 不同于 SALBP-1， SALBP-2的目标是给
8、定若干工作站，最小化它们的周期时间。大多数研究都只关注 SALBP-1的解，而不是关注 SALBP-2的解，这是因为SALBP-2可 以通过逐渐增加 SALBP-1的周期直到装配线平衡的方法来解决。早在1961年， Helgeson 和 Bimie就已经提出了一种解决 SALBP-2的启发式算法。Scholl (1999)提出了几个关于装配线系统安装和利用的决策问题，表明在有节奏的装配线中，平衡问题是非常重要的。 Scholl运用面向任务的分支定界法来解决SALBP-2，然后将结果与已存在的解决方案进行比较。 Klein和 Scholl (1996)采用新的统计方法作为解决方案，并且为直接解决
9、 SALBP-2开发了一个广义的分支定界法。此外， Gken 和 Agpak (2006)运用目标规划求解简单 U形装配线平衡问题，在这个问题中，决策者必须同时考虑几个冲突的目标。 Nearchou (2007)基于微分进化提出了一个启发式算法来解决 SALBP-2。紧接着， Nearchou (2008)基于多目标微分进化法又提出了一个新的启发式算法来解决 SALBP-2。 Gao, Sun, Wang, and Gen (2009)提出了一个机器人装配线平衡问题，在该问题中，装配线任务必须要分配给工作站，并且每一个工作站都需要选择一个可用的机器人以最小化周期为目的来处理分配 到的任务。在文
10、献中还表述了其他的方法。例如， Bock (2000)提出了用禁忌搜索解决 SALBB2，他还利用并行宽度拓展了禁忌搜索，并行宽度可以用来提升现存的禁忌搜索程序以解决装配线问题， Levitin, Rubinovitz, 和 Shnits(2006)开发了遗传算法，通过应用一个简单的进化规则和分支定界法解决大型、复杂的机器装配线平衡问题。 Asan 和 Tunali (2008)给出了遗传算法解决装配线问题的完整观点。 大多数研究都集中在 SALBP-1和 SALBP-2，很少有关于优化装配线平衡率 的研究。这种类型的问题被称作 SALBP-E，本文构建了 SALBP-E和解决 SALBP-E
11、问题的模型， SALBP-E被定义为 ，是处理装配线平衡率等问题的。所有工作的总时间是工作站的数目与周期的乘积。 SALBP-E试图让装配线平衡率最大而使空闲时间最小。换句话说， SALBP-E就是为了减少工作站的数目和周期。文章接下来的类容是这样组织的，章节 2介绍 SALBP-E的公式和解决过程。章节 3说明利用小到中型数学计算解决一个笔记本装配线模型和一些测试问题。文章最后做了一个总结。 武汉科技大学本科毕业论文外文翻译 3 2 SALBP-E的公式和解决 过程 SALBP-E集成了 SALBP1和 SALBP2模型，为了达到这个目标，定义以下符号和变量： n 任务数量（ i=1,2,3
12、， .n） m 站的数目（ j=1,2,3， .m） maxm 工作站最大值（ j=1,2,3， . maxm ） minm 工作站最小值（ j=1,2,3， . minm ） it 任务 i的运行时间 ct 周期 P 任务（ i， k）的子集，直接给出优先级关系 决策变量： ijx （ 0,1） 如果任务 i分配到任务 j为 1，否则为 0， ( min . maxi j= m m ； ) iy （ 0,1） 如果任何一个任务 i分配到 j为 1，否则为 0， (j=1. maxm ) ct 0 周期大于等于 0 *m 工作站最小数 SALBP-1的原始模型如下： （ 1） （ 2） （ 3
13、） （ 4） （ 5） 对于 SALBP1的原始模型，目标函数（ 1）保证了工作站数目 m最小，工作站的周期已知，约束（ 2）用来约束第 i个工作只能被分配到一个工作站。约束（ 3）约束分配到工作站 j的任务的总时间不超过周期。约束 4定义了优先关系，约束（ 5）武汉科技大学本科毕业论文外文翻译 4 确定了如果某个工作 i被分配到了工作站 j，则它的值为 1，否则为 0，在目标函数（ 1）中 ， 是 未知的且不能解出来，变量 y用来促进解决方案，修正后的模型 SALBP-1-i是如下定义的，目标函数（ 6）决定了在周期 CT已知情况下工作站最小数 mmin，约束（ 7） -（ 10）与上面 S
14、ALBP1的约束（ 2） -（ 5）定义类似。约束（ 11）的意思是如果任何一个工作分配到工作站 j，则它的值为 1，否则设置为 0. SALBP-1-i： .（ 6） . .（ 7） （ 8） （ 9） . .（ 10） .（ 11） SALBP-2的模型如下，目标函数是在工作站数目已知的情况下保证周期最小，约束 13-16与上文 SALBP1约束 2-5的定义方法相同。 SALBP-2 . （ 12） （ 13） （ 14） （ 15） （ 16） SALBP-E 结合了 SALBP-1和 SALBP-2 武汉科技大学本科毕业论文外文翻译 5 . (17) . (18) . (19) .
15、(20) (21) . (22) SALBP-E被定义为 ，所以空闲时间为 ，使装配线平衡率最大和空闲时间最少可以通过使产品的工作站数目和周期最小来实现，目标函数（ 17）使产品的周期和工作站数目最小，约束 18-22与 SALBP1-i的定义方法相同。 对于装配线平衡的大多数模型，第一步就是通过计算最早站 ei和最近站 li来确定哪个工作 i可以被分配，来减少分配到工作站的工作。两个变量 Ei和 Li，用来再定义 SALBP2模型， (Pastor, Corominas, & Lusa, 2004)，在 SALBP2-i模型中，表示任务 i之前的工作， 表示任务 i之后的工作。 X表示不超过
16、 x的 最大整数，和 是如下定义的： 再定义的 SALBP2模型叫做 SALBP2-i，有关符号和变量如下定义： 武汉科技大学本科毕业论文外文翻译 6 定义变量： 0 基于 SALBP-2-i模型，目标函数（ 23）保证了在工作站数目已知情况下周期ct最小，约束 24-27与上文中 SALBP1的定义类似。 SALBP-2-i . （ 23） .（ 24） .（ 25） （ 26） .（ 27） SALBP-E模型的最优工作站的数目定义为 m，在此之前 ctmax必须给出，ctmax表示所有工作的最大值与所有任务的时间被 2除后的值中间的较大者。这个值必须大于或者等于所有任务中的最长时间同时必
17、须所有任务的时间之和。如果ctmax比所有工作的总时间要大，那么只需要一个工作站就可以了，如果 ctmax小于或等于所有工作中最长时间，那么问题无解。 Ctmax的约束条件如下： ，平衡损失为 0 无解 在确定 ctmax值之后工作站的最 有数目就可以确定了。 M的值介于 mmin与mmax之间。工作站的最小数目 mmin是所有任务的总时间除以 ctmax，工作站的最大数目 mmax是所有任务的总时间除以所有任务中的最长时间。 M的值如下定义： 武汉科技大学本科毕业论文外文翻译 7 周期的上界 ctmax定义之后， LINGO 和 Excel VBA 可以取得 SALBP2和SALBP2-i的
18、工作站的数目，然后可用 EXCEL计算产品的工作作战数目和周期。 给出一个 ctmax m 在 mmax 与 mmin 之间 Solve SALBP-2 和 SALBP-2-i 计算 e=m*ct 得最优的 m， e， ct 输出最优 e， m， ct 结束 m mmax NO YES LINGO 配合EXCEL VBA 解决 SALBP-2 和 SALBP-2-i 工 作 站 数 目 m 由EXCEL VBA 确定，保证 m 由 mmax 增大到mmin 武汉科技大学本科毕业论文外文翻译 8 图 2 典型笔记本电脑装配 3计算结果 表 1 笔记本电脑装配职能 命令 功能 工具 A STRUC结构装配 螺旋给料器、螺丝刀、胶带分割器 B AFT装配 HDD、键盘、 RJ45标准线、 SY卡、扫描仪、笔记本 功能检测 TPDL C TPDL检测、程序下载 D R/I运行 支架试车 E PFT程序功能测试 电池、 BIOS电池、 ODD、 WWAN卡、笔记本、扫描仪 F 修饰、打包 螺丝刀、扫描仪、 DTC G SWDL下载 支架 WIP STRUC AFT TPDL R/I PFT COSM 打包 SWDL OBE 装运 修复 修复 修复 成功 失败 失败 成功 成功 失败
