开题（四稿）－高飞.doc

同济大学硕士研究生学位论文选题报告及论文工作计划课 题名 称 轿车发动机生产线的平衡优化研究及应用 学 号 0520030098 研 究 生 高飞 专业、年级 工业工程2005级 所在院、系 机械工程学院 导 师 郑永前 副 导 师 选 题 时间 年 月 日 同济大学研究生院年 月 日一、立论依据课题来源、选题依据和背景情况、课题研究目的、理论意义和实际应用价值流水生产线在制造系统中占有重要位置，被广泛应用。利用它进行各种产品的生产是现代化大生产的一种主要生产形式。采用大量生产方式的大部分产品，特别是一些较为复杂的产品，如汽车、家电等都在流水线上进行生产直至最终产品的。流水生产线的重要作用在制造企业中是不可替代的，也是至关重要的。随着市场经济的发展，国内制造企业面临着激烈的市场竞争，其中不少国营大中型企业不同程度的陷入了困境。要使这些企业走出困境，并以最低的成本为社会提供满足市场需求的具有竞争力的产品，是国内制造企业面临的最重要的课题之一。目前，国内制造企业设备落后固然是普遍现象，实际上管理更落后。即使一些设备相当先进的制造企业由于其管理不善、设计不合理而造成的人力、设备等的浪费相当严重，一般工厂多未很好的利用生产线的平衡技术。生产线不平衡的现象十分明显。据统计，对于我国企业，生产线的平衡率通常都很低。很多生产线经过进一步的平衡都可以将生产率进一步的提高。所以，生产线的平衡是一个比较迫切要解决的问题。实现生产线的平衡，对于提高生产效率，增加利润，增强企业的竞争力，发展我国工业都有重要的意义。特别是在资源日益缺乏的今天，其对于有效利用资源，缓和资源不足问题也有深远的意义。轿车发动机是轿车领域技术最密集的关键部件，其结构、工艺性等各方面都是及其的复杂。由于工艺的繁琐性，生产线在整个生产过程中就显得较为关键。不论是发动机各个零部件的生产装配还是最后的总装，由于被生产的零部件的多样性、工艺的繁琐性，轿车发动机生产线就显得尤为重要。轿车发动机生产线是一个对发动机各个零部件进行生产并最后总体装配的流水线工艺过程，每个工位之间是流水线生产，因此每个工位操作之间的最大化平衡，才能保证生产的连续性和稳定性。轿车发动机生产线一般都包括多条生产流水线，例如发动机缸盖生产线、发动机总装生产线等等。在发动机生产线上，目前国内普遍采用在线上配置自动化加工设备以提高效率，但是往往事与愿违，由于工位之间的不平衡导致了整个生产线的效率低下。本课题旨在针对轿车发动机生产线，研究的目的就是致力于提出一种新的可行有效的优化算法来优化平衡轿车发动机生产线，该优化算法针对轿车发动机生产线复杂性而专门设计的。这种优化算法将是基于混合遗传算法的，其核心思想就是将启发式算法和遗传算法进行集合，综合两者的优势。生产线的优化平衡涉及到多个方面，但是可以根据生产线平衡问题的求解目标不同，大体上可以分为两类子问题，分别称为第一类平衡问题和第二类平衡问题。在满足单元作业之间的约束关系和给定节拍时间的前提下，将单元作业分配给各工位，并使所需的工位数最小，这是第一类平衡问题。而第二类平衡问题是指在满足上述作业之间的约束关系和给定工位数的前提下，分配单元作业，使工位的最大作业时间最小。在本课题研究中应该包括这两类生产线平衡的子问题。不过由于时间和其他方面因素的限制，本课题只着重对生产线平衡的第一类子问题的优化平衡进行研究。生产线平衡问题是指如何分配各生产操作到不同的工位，使得整条生产线保持最高的生产效率。生产流水线平衡问题属于组合优化范畴，是一个典型的NPHard问题。特别是对于轿车发动机生产线，其工艺非常繁琐，所以求解难度较大，对它的研究有一定的挑战性，也具有重要的现实意义。二、文献综述国内外研究现状、发展动态；所阅文献的查阅范围及手段生产线平衡是生产线研究中最重要的设计问题，生产流水线的平衡问题是与生产流水线线问世之日同时出现的。生产流水线平衡问题最早由Bryton B1于1954年在他的硕士论文中提出，Salveson1于1955年首先建立了单品种装配流水线的数学模型，并给出了模型的解法。目前生产流水线平衡主要应用于新的生产流水线的设计和现有的生产流水线的优化与改进。从研究方向看主要集中在以下两个方面: 使得流水线的工作站数最少（即第一类平衡问题）和使得流水线的循环时间最低（第二类平衡问题）。其中有很多的出版物都提到了这个问题。在文献中有下面几种生产线平衡的问题，按照产品种类分为：1.单一模型生产线平衡问题；2.混合模型和多模型生产线平衡问题。按照生产线的布局形式分：1. 单边生产线；2. 双边生产线；3. 平行生产线。按照任务操作时间分为：1. 固定操作时间；2. 随机操作时间2。其中研究的重点在于单一产品具有固定任务时间的单边生产线，通常是在节拍时间已知的条件下进行简单的平衡。Ghosh 和Gagnom 3在1989 年给出了一个关于各种装配线的平衡算法的总结。针对生产线平衡及其相关问题的研究，国内外学者做了不少工作。虽然许多研究者给出了各种各样的算法来进行生产流水线的平衡，但是至今还没有有效的最优算法。大体上可以把这些算法归结为3种类型:启发式方法、最优化方法(数学模型法)和工业工程方法。最优化方法就是通过建立数学模型来寻找问题的最优解。尽管数学模型法能找到最优解，但实际应用时十分繁琐，往往一个很小的问题需要构造的模型非常大，计算机耗时也较多。只能局限于作业元素个数较少的ALB问题的求解。启发式方法以其简便、易懂、快速和满意赢得了众多管理人员的信赖和欢迎，并被广泛应用于各个领域。它的产生主要是为了克服现实建模的困难，提供一种更有效的决策工具，与最优化方法相比较，启发式方法的优点主要有：逻辑模型接近于现实，流程图建立在决策者经验的基础上，因此启发式方法隐含着多目标方案；它的主要局限是它的静态性，即在平衡过程中，固定的准则是预先确定的优先准则，而从产品加工过程、市场需求和公司战略来看，环境是动态变化的。We-Min Chow4在他的著作Assembly Line Design中总结了多种启发式的算法，不过上述基于启发式规则的传统算法只是按某种规则得到一个可行方案，缺乏多种方案的比较，最终解的可信度不高。吴君华5等给出了装配线平衡问题的数学模型描述，并进行了相应的启发式算法研究。在各种启发式算法中，由于近年来遗传算法求解复杂优化问题的巨大潜力及其在工业工程领域的成功应用，这种算法得到了广泛的关注。宋华明6等人提出了基于遗传算法的启发式程序来解决装配线平衡问题，并通过计算结果表明遗传算法是一种有效解决装配线平衡问题的工具。陈晓峰7等人受到鳗鱼效应的启发而提出了一种周期性自适应交换、变异遗传算法，通过实例证明了此算法可以解决简单遗传算法容易早熟收敛的问题。王芸凤8等人运用混合遗传算法求解装配线平衡问题，该算法将启发式规则和遗传算法以及模拟退火算法综合在一起，既利用了启发式规则基于经验的优势，可以提高算法的速度，又可使遗传算法和模拟退火算法优势互补，有效地解决了装配线平衡问题。此算法应用于实例分析，经过72次的迭代计算，结果表明设备的利用率可达92.13，有效地证明了算法的可行性和有效性。Ponnambalam9运用多目标遗传算法来求解线平衡问题，作者在文中运用了14种启发式规则来代替染色体基因，对6种启发式方法策略进行对比分析，利用C+语言工具进行迭代计算，CPU的运行时间大大减少，结果表明算法的可行性。Brahim Rekiek3应用组合遗传算法(Grouping Genetic Algorithm GGA)求解ALB2问题。目前，许多学者运用遗传算法解决生产线平衡问题，在不同程度上取得了一定的经济效果。以工业工程为主的生产线平衡相关技术主要是方法研究和作业测定两大技术，运用该技术的优点就是使企业在不投资或少投资情况下，不增加工人劳动强度甚至是降低劳动强度，通过实施一系列适合自身特点改善方法，对生产过程的作业程序、作业方法、MOD法、物料配置、空间布局及作业环境等各方面进行改善，达到企业平衡生产线进而提高生产能力、取得经济效益的目标。改善是企业永恒的主题，而工业工程所追求的目标就是永无止境的改善，运用相关技术对生产线平衡，为企业降低消耗，提高生产率。最近一、二十年，工业的内外环境发生了很大的变化，知识经济时代正在到来，生产线平衡方法体系也将具有新的特点和研究方向，以适应新环境下经济增长的需要。此外还有设备布置等相关方法也可以适当提高生产线平衡率，为企业带来更大的经济效益。工业工程方法需要决策者运用工作研究和作业测定技术对作业工序进行深入分析，但对于作业元素个数较多且约束条件较多的ALB问题则体现出一定的局限性。文献的查阅主要是近年来发表的专著，刊登在国内外主要相关期刊中的文章。查阅手段主要是：文献检索、Internet查询、图书馆资料查询。参考文献：1. 邓小波.汽车混流装配线的仿真研究D.华中科技大学，2005 2. 秦杏敏.双边装配线平衡与仿真评价D.上海交通大学，20053. Ghosh Soumen, Gagnom R J.A comprehensive literature review and analysis of the design, balancing and scheduling of assembly lines. International Journal of Production Research,1989,27(4):637-670.4. 刘晋浩,侯东亮.装配线平衡问题的求解方法浅析J.森林工程,2006,22(4):21-235.吴君华,夏巨谌,曹山河.ALB问题的数学模型及其优化算法的研究J. 系统仿真学报, 1999,11(5):358-360 6. 宋华明,韩玉启.基于遗传算法的装配线平衡J.系统工程,2002,1(109):87-917. 陈晓峰 肖田元 郝新 乔桂秀.应用遗传算法解决装配线平衡问题J.计算机工程与应用,2001,23:81-838. 王芸凤, 刘明周, 于宝证.求解装配线平衡问题的混合遗传算法J.合肥工业大学学报, 2005,28(6):616-6199.Ponnambalam S G.A multi objective genetic algorithm for solving assembly line balancing problem J.Int.Adv.Manuf.Technol.2000(16):341-352.三、研究内容1学术构想与思路、主要研究内容及拟解决的关键技术本课题是针对轿车发动机生产线的平衡优化，首先对于选题的背景进行相应的概述。接着考虑生产线的平衡技术，其中包括对国内外的生产线平衡算法进行研究、生产线平衡问题的界定、启发式算法的基本理论以及遗传算法的介绍。接着考虑生产流水线的情况，其中首先对流水生产线的基本原理、特征以及分类和设计条件等进行详述，接着结合轿车发动机的特点对其生产线的应的特点进行归纳和总结。然后考虑轿车发动机的特点，针对轿车发动机的生产线进行平衡算法的设计。最后结合大众轿车发动机生产线这个实例来验证所设计算法的可行性和有效性。具体内容框架见图1所式。生产线的平衡技术国内外算法研究综述生产线平衡问题界定遗传算法的研究启发式算法的基本理论的研究流水生产线概念、特征的研究轿车发动机生产线平衡问题的算法设计流水生产线轿车发动机生产线的归纳和总结流水线的分类和设计条件的研究流水生产线的基本原理的研究大众轿车发动机生产线的实例验证图12拟采取的研究方法、技术路线、实施方案及可行性分析由于本课题只着重对轿车发动机生产线平衡的第一类子问题（ALB1问题）的优化平衡进行研究，即在满足作业元素之间的约束关系和给定节拍时间的前提下，将单元作业分配给各工位，并使所需的工位数最小。所以考虑如下：1、指定作业元素之间的相互关系，即画出优先关系图。2、决定生产线的节拍。 3、计算理论上的最小工作地数，满足节拍时间的约束。4、设计选择分派作业元素至工作站的主要规，即平衡算法的设计。本课题拟采用遗传算法进行平衡算法的设计。5、根据设计好的平衡算法，分派作业元素至工作站，直到把所有的作业元素都分配完，即得到一个最优解。6、估算生产线的平衡效率，或者利用另外一个等价的指标，即平衡延迟率。7、利用专业仿真软件对已经平衡优化过的生产线进行动态的仿真，看其是否达到了优化的水平，并输出仿真结果。本课题拟采用matlab来进行动态的仿真。其中，最为关键的，而且也是最难点的是平衡优化算法的研究设计以及对于优化结果的动态的仿真。对于平衡优化算法设计，本课题拟采用遗传算法来设计生产线的平衡算法，拟设计如下：1.总体设计a确定遗传算法的有关参数，包括遗传算法的群体容量、交叉概率、变异概率和迭代次数；b. 初始化种群；c. 计算染色体适应值；d. 判断适应值是否符合要求，产生新一代结果，否则转向c，输出结果。2.遗传算法设计a. 编码本课题拟采用序列编码方式：按照作业元素分派至工作站的先后顺序，将作业元素排成一列，每个作业元素对应一个基因位。b.译码按照上述顺序将作业元素分配到工作站，满足一个工作站的所有作业元素时间之和不超过节拍时间。c.适应度函数 同时考虑要求工位数最少，而且还考虑生产线的负荷最均衡。d.初始化种群利用启发式规则,产生k个初始可行解,因为启发式规则是基于经验的,这样产生的初始种群比较好,而且可以加快算法速度。f.选择、交叉和变异针对生产线平衡的特点,在进行选择、交叉和变异时，应尽保留父代个体基因间的顺序位置和邻接关系。选择拟采用锦标赛选择，即计算父代个体中k个解的适应度f，选择最大的作为子代个体，保留局部最优。交叉拟采用的交叉算子是基于PMX(Partial Matched Crossover)实现的。它随机地在两染色体内确定一个交叉片断,并通过交换两交叉片断中的相同元素子序列来生成满足作业顺序约束的新染色体。变异拟选用互换操作(SWAP)和插入操作(INS)。互换操作即随机选择个体x,随机产生变异点x(i)和x(j)。若x(i)和x(j)是非关联任务或者x(i)和x(j)是关联任务,但当前位置不符合优化的约束条件,则做变异操作,产生新个体x。插入操作即随机选择个体x，随机选择某个无约束点x(i)插入到个体x中的不同随机位置，产生新个体x。算法的设计结构框图如图2所式。对于利用设计的平衡算法优化的结果，本课题将采用matlab仿真软件对其进行动态的仿真，这样可以动态的考虑所设计的平衡算法的可行性和有效性。基于启发式规则的种群初始化工位数和负荷均衡的评价达到迭代次数交叉和变异下一代群体终止条件判断？最佳的生产线工位划分NYNY针对生产线的序列编码图2四、研究基础1所需实验手段、研究条件和实验条件创建实验室研究环境，需用到以下的一些软件和硬件：终端： CPU P 1.5GMemory 1GVirtual memory 2GDisk free space 5G图形卡 64M上网设备： TPLINK路由器软件：终端： Windows NT SP5/ Windows 2000 SP2开发工具： Matlab6.5 Visual Studio2所需经费，包含经费来源、开支预算（工程设备、材料须填写名称、规格、数量） 终端 10000 打印复印 500 TPLINK路由器 150 移动存储设备 2000五、工作计划序号阶段及内容工作量估计（时数）起讫日期阶段成果形式12345678前期调研，现场资料搜集以及相关学术资料收集相关编程语言、Proe及仿真软件的学习平衡算法的初步设计： 考虑基于遗传算法的平衡算法设计的大体框架及相关内容对平衡算法进行设计：确定基于遗传算法的平衡算法的设计结合收集回来的资料进行算法的实例验证并调试算法用matlab6.5对算法优化后的结果进行动态的仿真评价撰写硕士论文答辩准备及答辩30050030080060060010002002008.92008.10-2008.122008.12-2007.12007.1-2007.42007.4-2007.6