计算机辅助生产线平衡与产能分析研究

1、计算机辅助生产线平衡与产能分析研究计算机辅助生产线平衡与产能分析研究 计算机辅助生产线平衡与产能分析研究 摘要 生产线平衡是生产线设计规划中重要的组合优化决策问题,与生产线这一生产方式可谓同日而生,其相关的解决方案也可谓汗牛充栋,但是具体的算法设计却少见披露.本设计着重于计算机辅助生产线平衡和产能分析系统(Computer Aided Assembly Line Balancing and Capacity Analysis,CAALB&CA)的算法研究和编程实现.系统利用开放的关系数据库平台和面向对象的程序设计技术,构造了生产线平衡和产能分析中的作业,工作站,产品,生产线等仿真对象,导出了单

2、一产品与混合产品,直线与U型布局生产线平衡优化中先后关系矩阵,作业集合,网络图等基础算法,采用有序双点交叉遗传算法以同时实现这些生产线的平衡优化;并充分考虑实际工程应用可能的需求,提出了并行工作站和产能调整的概念和相应的算法;在混合产品生产线的平衡优化中还考虑了不同的优化目标函数和作业分配均衡度指标.在本文最后用实际工程的数据对系统进行了验证. 关键词:生产线平衡,产能分析,遗传算法,计算机辅助计算机辅助生产线平衡与产能分析研究 RESEARCH ON COMPUTER AIDED ASSEMBLY LINE BALANCING AND CAPACITY ANALYSIS ABSTRACT A

3、ssembly lines balancing problem is an important decision problem when (re-)configuring an assembly line. It consists of distributing the total workload for manufacturing any unit of the product to be assemb among the work stations along the line corresponding to the cycle time. Production capacity a

4、nalysis focuses on the balance of production capacity and production resource, which contributes much to the efficiency of a production system. This thesis aims to study the fundament algorithms for these two problems and builds up a test edition of the Computer Aided Assembly Line Balancing and Cap

5、acity Analysis System (CAALB&CA). In this system, a kind of genetic algorithm based on feasible tasks sequence is utilized to balance straight and U-shaped assembly line respectively. Then the author extends this algorithm to solve mix-model assembly line balancing problem by combining the products

6、into a virtual representative product. Whats more, this system also applies to the second kind of assembly line problem in which the stations number is fixed and the minimal cycle time is to be found. Key words: assembly line balancing, production capacity analysis,genetic algorithms, computer aided

7、计算机辅助生产线平衡与产能分析研究 目 录 第一章 绪论.1 1.1 问题的提出.1 1.1.1 背景介绍.1 1.1.2 生产线平衡问题的描述.1 1.1.3 生产线平衡问题的分类.2 1.2 研究意义.2 1.3 章节安排.3 第二章 生产线平衡问题方法研究.4 2.1 生产线平衡的基本概念.4 2.2 术语,符号定义及假设.4 2.2.1术语定义.4 2.2.2 符号定义.5 2.2.3 生产线平衡模型的假设.5 2.3 生产线平衡基本思路.5 2.4 生产线平衡的评价指标.6 2.4.1 生产线空闲时间.6 2.4.2 生产效率.6 2.4.3 生产线平滑指数.6 2.5生产线平衡问题

8、算法概要.7 2.6 U型布局生产线平衡.8 第三章 算法设计.9 3.1遗传算法概要介绍.9 3.2 单产品生产线平衡算法.9 3.2.1产品作业先后关系矩阵.9 3.2.2 构建可行作业序列.11 3.2.3 生成生产线平衡问题的可行解.11 3.2.4 遗传算法设计.12 3.2.5 ALB2型问题遗传算法设计.15 3.3 混合产品生产线平衡算法.15 3.3.1 由多个产品紧后作业集合构造混合生产线先后关系矩阵.15 3.3.2 由混合生产线先后关系矩阵生成作业的紧后作业集合.15 3.3.3 混合产品生产线平衡算法设计.17 3.4 产能调整算法.19 3.4.1 人员及设备分配.

9、19 3.4.2 产能调整.20 第四章 系统的设计与开发.21 4.1 系统的结构与功能.21 计算机辅助生产线平衡与产能分析研究 4.2系统模块功能简述.22 4.2.1通用数据管理模块.22 4.2.2 项目生成模块.22 4.2.3生产线平衡模块.22 4.2.4 产能调整模块.23 4.3 系统模型设计.23 4.3.1数据流程图.25 4.3.2系统对象.25 4.3.4 模块的结构与 第一章 绪论 1.1 问题的提出 1.1.1 背景介绍 从上世纪初福特创建第一条汽车工业流水线开始,流水生产线已逐渐成为现代化制造业中一种主要的生产组织形式,广泛应用于以家电,汽车为代表的大规模生产

10、中.流水生产线按照产品(零部件) 的生产工艺顺序排列工位,使产品(零部件)按照一定的速度,连续地和有节奏地经过各个工位依次加工,直到完成产品成品. 在这种生产组织形式下,一条流水生产线上固定地生产一种或少数几种制品,每个工位均固定完成一道或几道作业,各工位具有较高的专业化程度,同时工位按工艺顺序排列,加工对象在作业间单向移动,降低了工件搬运成本,减少了作业间的在制品数量.每道作业的工位数量同各道作业的加工时间比例相一致.而且每道作业都按统一的节拍进行生产(所谓节拍是指相邻两件制品的出产间隔时间),易于对各作业的产量进行的生产能力,并获得一个最接近实际生产能力的值.从整体上看,通过产能与负荷的平

11、衡,产能分析可以提高整个企业的生产运作效率.从局部上看,通过产能分析可以发现瓶颈环节,并可通过采取适当措施改善瓶颈环节,提高生产效率.同时产能分析还可以为MRPII/ERP中的能力需求计划提供产能依据.从结果上看,如果理论分析的产能比实际产能高,会导致生产节拍的混乱,计划下达的订单不能及时完成,延误交货期,降低客户的满意度,从而降低产品的市场份额;反之,又会导致开工率不足,设备闲置,应该能完成的订单被取消,失去市场机遇,同样也会失去市场份额. 在进行生产线平衡之前,产能分析主要是为了确定生产线的生产能力,找出瓶颈作业,以便在进行平衡的时候可以为该作业分配并行工作站,增加资源,降低作业时间,提高

12、生产能力.在进行生产线平衡以后,生产线的生产能力便确定下来,这时仍可以对已得到的生产能力进行调整,获得新的平衡方案,以满足柔性化生产的需要. 1.2 研究意义 计算机辅助生产线平衡与产能分析研究 第 3 页 共 52 页 入世后,我国制造业开始与国际接轨,正逐步成为世界制造中心,各类生产流水线都已经或将被大规模的采用.生产线平衡作为生产线设计中的一个重要方面,具有巨大的实用价值.在国外,这方面的研究文献较多,其计算机辅助软件也已面市,如Proplanner等,但其昂贵的价格也令很多国内企业望而却步;在国内也有这方面的研究和类似的软件问世,但多数都只能解决直线型的生产线平衡问题,对U型生产线平衡

13、的解决方案较少. 本文采用遗传算法,分别对生产线平衡的两类问题,按单一产品直线型,多种产品混合直线型,单一产品U型,多种产品混合U型四种生产形式提出了可行的平衡算法,并开发了生产线平衡应用软件系统. 1.3 章节安排 本文将在第二章对生产线平衡问题及其约束进行形式化描述,并给出其基本思路和平衡效果的评价指标,同时简要介绍常见的生产线平衡方法.第三章中详细描述生产线平衡问题的遗传算法设计过程,第四章将介绍软件系统的开发和设计过程,第五章将给出两个例子使用本软件进行平衡.第六章进行全文总结,并展望未来,提出存在的问题和今后继续研究的方向. 计算机辅助生产线平衡与产能分析研究 第 4 页 共 52

14、页 第二章 生产线平衡问题方法研究 2.1 生产线平衡的基本概念 生产线平衡的目的是将产品生产所需的一系列作业(task)(各项作业加工时间已知)按具体的生产顺序分组,分配到数个工作站(station)中,使得各个工作站的负荷满足生产节拍的要求并且空闲时间最小2. A. 作业(Task) 作业亦称为工序,是产品加工过程中全部工作内容的一部分,是完成某项操作所进行的最小工作单元,在进行生产线平衡时不能对作业再行拆分. B. 工作站(work station) 有时也称工位,是生产线的一个工作地.产品在此工作地完成一个或几个作业或工序的操作.如在汽车制造业中,我们可以将汽车在装配线上停留待装的部位

15、或者车位看作是一个工作站. C. 流程图 流程图是描述各作业加工次序的图.通常产品的作业之间存在某种技术上的先后顺序约束关系,某些作业必须在其他作业完成之后才能进行,我们将这种先后顺序关系称为作业先后关系,它决定了生产过程中作业完成的先后次序.实际上生产线的平衡问题很大程度上依赖于流程图,平衡的效率就取决于优先图的复杂程度.下图就是一张简单的优先图. 图2-1 产品加工流程图 在产品作业流程图中,圆表示作业,箭头表示作业之间的联系,圆中的数字表示作业的编号. D. 产品混合比例 它是指混合生产线上生产的各种产品之间的产量比例关系.在市场需求为主导的现代化制造业中,这一比例关系往往是变动的,它的

16、变化反映了产品需求量的变化,通常就是生产线动态调整与平衡的原动力. 2.2 术语,符号定义及假设 2.2.1术语定义 紧后作业: 某一作业的直接后继作业,不包括间接后续关系.如图2-1中,作业2的紧后作业包括作业6和作业7. 后继作业: 某一作业的所有后继作业,包括间接后续关系.如图2-1中,作业2的后续作业包括作业6,作业7,作业9和作业11. 计算机辅助生产线平衡与产能分析研究 第 5 页 共 52 页 紧前作业: 某一作业的直接先行作业,不包括间接先行关系.如图2-1中,作业7的紧前作业仅为作业2. 先行作业: 某一作业的所有先行作业,包括间接先行关系.如图2-1中,作业7的先行作业包括

17、作业2和作业1. 作业先后关系矩阵:在生产线平衡中,我们通常使用产品作业先后关系矩阵来描述产品作业间的先行约束关系.矩阵的行和列均代表相应编号的作业,矩阵中的0代表列作业可以在行作业之前进行,也可以在行作业之后进行;而1代表列作业一定要在行作业完成之后才能进行,即行作业为列作业的先行作业,从而列作业也为行作业的后续作业.对于图2-1中的产品加工流程图,其先后关系矩阵如图2.2所示. 图2-2 作业先后关系矩阵 2.2.2 符号定义 N 产品的作业总数 K 分配的工作站总数 Ti 产品的第i个作业 ti (i=1,2, ,N)表示产品的作业i的作业时间. PSi,j (i=1,2, ,N; j=

18、1,2, ,N),产品先后关系矩阵,当且仅当作业i必须领先于作业j时,PS(i,j)=1,否则等于0,包括了直接先后关系和间接先后关系. C 产品节拍时间,即生产单位产品耗时. Si= Tl , Tm , Tn . 作业i的紧后作业的集合. Mk = Tl , Tm , Tn . 为所有分配给工作站k的作业的集合 T = Ti , Tj , Tk . 产品所有作业的一个有序排列,产品的所有作业均在而且仅在序列中出现一次,作业排列次序满足作业先后关系的约束. 2.2.3 生产线平衡模型的假设 (1) 在同一条生产线上进行加工的产品总是相似的,即大部分的作业是相同; (2) 产品各道作业的加工时间

19、是已知且为定值; (3) 产品的作业的先后作业关系是已知的; (4) 对于多品种混合生产线,各产品作业的先后约束不会出现相互违背的情况,即若在产品A中作业i需在作业j完成后才能进行,那么在生产线上生产的其余产品中就不会出现要求作业j在作业i完成后才能进行的情况3; (5) 工作站之间没有在制品库存缓冲区,即生产线上生产的产品是一个连续流的; (6) 不同产品的相同作业必须分配到同一个工作站; (7) 生产线上生产的每个产品都从头至尾经过生产线上每一个工作站. 2.3 生产线平衡基本思路 生产线平衡需要满足的条件有二,一是在各工作站上进行加工的作业加工时间之和必须小于生产节拍,以满足生产能力的要

20、求,二是产品依次经过各工作站不违反作业的先后计算机辅助生产线平衡与产能分析研究 第 6 页 共 52 页 约束关系.因此平衡过程依照生产节拍来进行,同时要求分配的顺序满足作业的先后关系限制.传统的平衡思路如下: (1) 从工作站1开始,依顺序给工作站分配作业; (2) 确定任务元素清单,分离可行任务元素和不可行任务元素; (3) 去掉已分派的任务元素; (4) 去掉那些不能满足前后生产顺序关系的任务元素,即分配的作业的前向作业已全部分配; (5) 去掉那此工作站不能提供足够时间的任务元素,即该作业时间不超过该工作站的空闲时间,即生产节拍与以分配到该工作站的时间之差; (6) 确定一个能够指派的

21、任务元素.比如清单上的第1个任务元素或最后一个任务元素时间最长或最短的任务元素.也可以任意选择的任务元素,或按其他一些标准; (7) 改变任务元素以找到最佳平衡,选择标准可按照生产效率最高,或者空闲时间最小等. 对于生产线平衡的第二类问题,即给定工作站数,求满足生产要求的最小生产节拍,只需对上述步骤稍作改动. 给定工作站数为N,则理论最小生产周期可按下式计算: 1NiiTCN=理论 (2-1) 因为生产线上最长的作业时间决定了生产节拍的下限,因此最长作业时间的作业为瓶颈作业,故比较C理论与瓶颈作业时间.若C理论小,则取生产节拍等于C理论,否则取生产节拍等于瓶颈作业时间,即生产节拍的下限.然后采

22、用迭代法将作业分配到各工位,步骤如下: (1) 初始化节拍TT和迭代速率L; (2) 按前诉步骤分配作业; (3) 若已分配的工作站数超过N而仍有作业未分配,则停止分配,并令CT = CT + L,转入步骤2)重新分配. (4) 若所有作业都分配完毕时工作站数未超过N,则循环结束,输出最终的生产节拍. 2.4 生产线平衡的评价指标 2.4.1 生产线空闲时间 生产线空闲时间IdleTime为生产线流失的时间之和,即各工作站空闲时间之和. 1NiiIdleTime C K T= (2-2) 2.4.2 生产效率 生产效率E描述了生产线的相对生产率, 11KiiIdleTimeET= (2-3)

23、2.4.3 生产线平滑指数 生产线平滑指数SX,是生产线平衡状态的主要指标,描述了各工作站工作负荷的差异计算机辅助生产线平衡与产能分析研究 第 7 页 共 52 页 情况. 21ikKikTMCtK=SX (2-4) 其中it为作业i的作业时间,而作业i被分配至工作站k. 2.5生产线平衡问题算法概要 生产线平衡问题是也生产线问世之日同时出现的,但正式提出并着手解决这一问题的是美国人B.Bryton,他于1954年完成的硕士论文连续生产线的平衡,引起了企业界和学术界人士的极大兴趣.其后,许多人研究这个方面的问题,并发表了各种各样的方法,将研究成果直接用于生产实践活动中,取得了明显的经济效益.

24、生产线平衡是一个系统工程,其中涉及到生产的方方面面,目前在ALB 问题上国内外有许多相关的论文,他们中有许多是研究生产线平衡的数学建模和优化算法的.这中间包括了对于单种产品的研究和多种产品混线装配的研究,还有不少论文研究了生产线的改善问题,即通过各种途径缩短工序的周期时间,增加操作的效率,提高生产率,生产质量以及安全性等.就目前研究现状来说装配线平衡问题的求解方法大致可分为精确算法与近似算法两大类4. 精确算法(主要是运筹学中的各种算法) 图2-3 U型生产线布局图 如图2-3 所示,这条生产线上共配备4个操作工,当生产任务减半时,要求工人数也减半,这时生产线安排如图2-4所示. 图2-4 生

25、产任务减少后的U型作业人数安排 U 型布局的本质关键在于生产线的出口和入口在同一个位置, 我们正是利用这个特点灵活地增减作业现场的作业人员,同时这样也便于实现准时制生产的基本思想,即按后工序领取的数量进行生产.如图2-3和2-4所示,生产线的入口和出口都由一个工人负责,这样可以很方便的实现成品离开生产线和原料进入生产线的同步.既实现了生产线的平衡,也使生产线内待加工产品数维持恒定.通过明确规定每个工序可持有的标准待加工产品数,即使出现了不平衡现象,也能很快发现,有利于及时对各工序进行改善6. 另外,U型生产线上工作站间距离较近,工人可以操作更多的机器,能够充分发挥团队合作精神;同时还可以简化物

26、料搬运过程,降低库存. 在生产线平衡上,U型生产线分配作业到工作站时, 可以按照从前到后或者从后到前的顺序单方向进行, 也可以从两个方向同时进行. 在直线型的生产线上, 分配作业元素的顺序只能按照单方向进行. 因而, 在U 型生产线上, 分配作业元素时, 选择的范围更大. 在一些使用直线型布局不能得到满意结果的场合,可以得到更优的平衡方案. U-型生产线平衡算比直线型更为复杂,常见的算法有启发式算法,动态规划法,遗传算法,分支定界算法等.计算机辅助生产线平衡与产能分析研究 第 9 页 共 52 页 第三章 算法设计 3.1遗传算法概要介绍 在详细介绍求解ALB问题的基于可行作业序列的遗传算法之

27、前,本文先对传统的遗传算法进行一下简单的介绍. 遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法,和传统搜索算法不同,遗传算法从一组随机产生的初始解(称为种群Population)开始搜索过程.种群中的每个个体都是问题的一个可行解,称为染色体(chromosome).染色体数值化为一串符号,比如一个二进制字符串.这些染色体在后续迭代中不断进化,称为遗传.在每一代中用适应值(fitness)来测量染色体的好坏.生成的下一代染色体,称为后代(offSpring).后代是由前一代染色体通过交叉(crossover)或者变异(Mutahon)运算形成的.交叉是指选择群体中的两个个体,以这两个个体

28、为双亲,做基因链码的交叉,从而产生两个新的个体做它们的后代.最常用的简单交叉方法是随机选取一个截断点切开,并交换其后部基因,从而组合成两个新的个体.变异是指对于群体中的某个个体,即基因链码,随机选取某一位(某基因),将该位基因码翻转,1转为0,0转为1.新一代种群形成过程中,根据适值的高低选择部分后代,淘汰部分后代,从而保持种群大小是常数.适值高的染色体被选中的概率较高.这样,经过若干代之后,算法收敛于最好的染色体,它很可能就是问题的最优解或次优解.其基本程序结构如图3-1所示5. 图3-1 传统遗传算法基本程序结构图 遗传算法是人工智能领域中新兴的一种全局寻优算法,具有极强的并行搜索能力,寻

29、优速度快,能跳出局部最优,并且不需要任何先验知识和专家知识的指导. 3.2 单产品生产线平衡算法 在本节中我们先考虑ALB1型问题.基于可行作业序列的遗传算法首先需要构建可行作业序列集合.可行作业序列就是一个作业序列T = Ti , Tj , Tk .,这个序列是产品作业的一个全排列,并且所有作业的出现次序满足作业先后关系的约束.然后将可行作业序列用贪婪法组合分配入工作站,得到生产线平衡问题可行解,根据可行解构建遗传算法的基础种群. 3.2.1产品作业先后关系矩阵 计算机辅助生产线平衡与产能分析研究 第 10 页 共 52 页 由2.2中所述,我们使用产品作业先后关系矩阵描述产品作业的先后顺序

30、约束. 3.2.1.1产品作业先后关系矩阵的形态 很多关于生产线平衡的文献中都描述产品的先后关系矩阵是一个上三角矩阵.作为上三角矩阵,我们知道矩阵行和列所代表的作业的排序必定满足位于矩阵上端的行或矩阵左边的列所代表的作业先于矩阵下端的行或矩阵右边的列所代表的作业,例如,矩阵第一行第一列所代表的作业一定是该产品的首发作业.在这种情况下,产品作业间的先后关系已经是很清晰了,由先后关系矩阵绘制产品的先后关系图或产生可能的作业序列就十分方便. 但是仔细的研究发现,这一观点实际上仅对于手工编制的先后关系矩阵是成立的,对于计算机辅助设计而言,通常是由计算机根据紧后作业集合编制先后关系矩阵,因此计算机需要遍

31、历紧后作业集合组成的多叉树才能确定作业之间的完整先后关系.然而,要按照作业之间的先后关系安排作业在关系矩阵中的行列位置比较困难.一般情况下,作业与先后关系关系矩阵行列序号之间的关系就是作业在产品作业清单中的存放顺序,要求先后关系矩阵是一个上三角矩阵意味着作业清单的存放顺序满足作业先后关系的要求,则通常意味着从数据库中取出产品作业时也必须满足产品作业顺序的要求,更麻烦的是在多个产品混合的情况下,由于各产品所包含的作业不完全相同,为了保证混合后的先后关系矩阵是一个上三角矩阵,必须对原有的先后关系矩阵进行大量的插入和移动操作.综合以上的因素考虑,将先后关系矩阵定义为上三角矩阵带来的麻烦太多,造成软件

32、不同模块之间不必要的牵连,因此,必须提出与任意形状的先后关系矩阵相关的算法. 一个上三角矩阵的产品的先后关系矩阵隐含了作业间接先后关系的概念,即如果A作业的直接后继作业是B作业,B作业的直接后继作业是C作业,则C作业是A作业的间接后继作业,则A作业是C作业的间接先行作业.引入间接先后关系是为了在多产品混合时正确的创建混合产品的先后关系矩阵和紧前与紧后作业集合. 3.2.1.2产品作业先后关系矩阵的构造 用户在定义产品时,最直观的感受是一项作业的紧前作业,用一组紧后作业集后描述作业间的先后关系: S=S1 , S2 , ,Sni 而在计算机内部通过产品先后关系矩阵PSi,j来处理约束.由紧后作业

33、集合S集合变换到先后关系矩阵的算法分为2个阶段.首先,依据紧后作业集合,直接确定关系矩阵PSi,j的直接关系位;然后分析直接先后关系,确定各任务的间接先后关系. A. 算法思想: 如果PS(i,j)=1,说明Tj是Ti的紧后作业,如果PS(j,k)=1,则说明Tk是Tj的紧后作业,因此Ti是Tk 先行作业,进一步以此类推,如果PS(j,k)=1,PS(k,l)=1, ,PS(y,z)=1,则导出Ti是Tk,Tl, ,Tz的先行作业. B. 算法设计 (1) 将先后关系矩阵PSi,j的所有元素清零. (2) 遍历Si集合中的所有成员,如果Ti 在集合中,则置PS(i,j)=1. (3) 遍历S集

34、合,对S=S1 , S2 , ,Sni 执行第2步同样的操作. (4) 从先后关系矩阵PSi,j的第一行,第一列的元素PS(1,1)开始. (5) 如果某一元素等于1,不失一般性,设1=ijp,则检查第j行的所有元素,对第j行的所有等于1的元素,不失一般性,设1=jkp,则置PS(i,j)=1. (6) 重复进行5的步骤,直到遍历PSi,j的所有元素. 说明性程序如下: 计算机辅助生产线平衡与产能分析研究 第 11 页 共 52 页 For i = 1 To n For j = 1 To n If PS(i, j) = 1 Then For k = 1 Ton If PR(j, k) = 1

35、Then PR(i, k) = 1 End If Next End If Next Next 3.2.2 构建可行作业序列 A. 算法思想: 为了使作业的排列满足先后关系的约束,首先需要确定当前可以添加到序列中的作业,即该作业的先行作业都已放入这个作业序列,也即当前的最先行作业.在先后关系矩阵中,元素全为零的列所代表的作业就是当前的最先行作业,因为这些作业没有紧前作业.例如,对所有(i=1,2, ,N) ,均有PS(i,j)=0,则Tj是当前最先行作业.再从当前最先行作业中选择一个作业放入作业序列,该作业进入作业序列后,则他的紧后作业也将满足先后关系成为可以进行的作业. B. 算法设计: (1

36、) 设立一个缓冲数组,命名为buf (2) 搜索先后关系矩阵PSi,j,找出全为零的列,设为j,判断对应的作业Tj是否已经进入作业序列,如是,则将其丢弃,如否,则将其对应的列号j加入buf.继续寻找其他全为零的列,执行上述相同动作,直到所有PSi,j的所有列均已遍历. (3) 从buf中按照某种算法抽取一项(如随机抽取或抽取后续作业最多的作业),设为k,则将Tk 加入作业序列T.同时将先后关系矩阵PSi,j的第k行全部清为零. (4) 如buf不为空,或PSi,j不为零矩阵,则跳转到第2步继续执行,否则结束.作业序列T = Ti , Tj , Tk .已经生成. 图3-2 可行作业系列生成算法

37、流程 3.2.3 生成生产线平衡问题的可行解 对于某一给定的作业序列T = Ti , Tj , Tk .,将其作业分配给工作站的算法取决于生产线的布置形式.对于直线型生产线,由于作业顺序已经确定,分配工作站的算法计算机辅助生产线平衡与产能分析研究 第 12 页 共 52 页 非常简单,采用最大可能分配法,在不超过生产节拍的前提下,尽可能多的把作业分配给工作组.对于U型生产线,情况要复杂一些,文献3指出有6种可能的分配方法,即: (1)交替从作业序列头尾分配, (2)交替从头尾分配,但是序列尾部的作业优先分配, (3)先尽力从作业序列头分配,然后再从作业序列尾分配, (4)先尽力从作业序列尾分配

38、,然后再从作业序列头分配 (5) 交替从头尾分配,但是初始优先分配作业序列头的作业,分配下一个作业时,交换优先权,优先下一轮分配作业序列尾的作业. (6) 交替从头尾分配,但是初始优先分配作业序列尾的作业,分配下一个作业时,交换优先权,优先下一轮分配作业序列头的作业. 但是,根据文献11给出的大量计算结果分析,各种的算法的差别不大,限于时间关系,本设计仅实现了从作业序列头和尾尽力分配,即先从作业序列头开始,如果头部的作业可以分配给工作组,立即分配,如果作业序列尾部的作业可以分配,立即分配.直到作业序列头尾的作业均不能再分配为止. 3.2.4 遗传算法设计 遗传算法的基本步骤如下: (1) 根据

39、可行解,构造指定容量的初始种群染色体. (2) 计算种群中的所有染色体的目标优化函数值,并将染色体的目标优化函数值转换为适应度. (3) 采用启发式选择,优先从种群中挑选一定数量(如1/2种群数量)的具有最优目标优化函数值的染色体进入交配种群. (4) 随即生成0-1之间的随机数,采用轮盘赌算法和染色体适应度随机选择其余的染色体进入交配种群. (5) 采用有序双点交叉法,从交配种群中交配产生下一代种群. (6) 重复从第2步进行迭代计算,直到完成指定次数的迭代计算为止. 图3-3 遗传算法实现过程 在这里我们没有采用遗传算法中的变异操作,主要因为构成染色体的作业序列必须满足作业的先后顺序关系,

40、而由一条染色体自身通过交换其上某些作业的位置而得到的一个新的作业序列极其可能就会违反作业先后关系.另一方面,我们构建的个体选择方法和交叉方法在尽可能做到全局搜索的同时也注意了对优良个体的保护. 3.2.4.1 遗传算法的染色体构造方法 遗传算法染色体构造方法用于构造遗传算法所需要的初始种群.根据遗传算法的特点,初始种群由用户指定数量(称为种群数量)的染色体构成,每一条染色体为一种可能的平衡方案,满足平衡的全部约束.同时,为实现通过遗传算法全局寻优的目的,初始种群应计算机辅助生产线平衡与产能分析研究 第 13 页 共 52 页 该具有足够的代表性,尽可能多包括所有可能的作业排列,以避免寻优中收敛

41、于局部最优点,这类似于保证染色体的生物多样性,避免近亲繁殖.染色体构造分为两步,即基因编码和染色体的生成算法如下: (1) 基因编码,采用前述创建满足约束要求的作业序列的方法构建作业序列T = Ti , Tj , Tk .,作为基因编码.在构建作业序列算法的第3步,假设当前buf内的作业个数为M,则先生成一个1M之间的随机数i,然后,抽取buf内的第i个作业组成作业序列.通过这种方法来保证染色体的多样性. (2) 采用前述按照作业序列分配工作站的算法,为基因编码分配工作站. (3) 根据已经确定的工作站作业分配方案,计算染色体的平衡数据,如总空闲时间,空闲时间均方差,生产线效率等. 3.2.4

42、.2 有序双点交叉算子方法 有序双点交叉算子用于遗传算法的染色体交配,以便产生新一代的染色体.如前所述,用于生产线平衡问题的基因编码是约束要求的作业序列,有序双点交叉算子必须保证两条染色体交叉说形成的下一代染色体仍然具有满足生产线平衡问题约束要求的基因编码,为此算法设计如下. 设基因编码长度为N ,等于产品的作业个数.P表示种群数量. (1) 建立一个长度为P的数组,命名为index,index数组内依次存放1-P,即第一个单元存入1,第P个单元存入P. (2) 从第一个单元开始,依次进行P次以下动作. (3) 设当前操作的是index数组的第i个单元,生成一个1P之间的随机数point,然后

43、交换index数组当前单元和第point号单元. (4) 重复第3步操作,直到P个数组单元均已操作完毕,这是为了使index数组的序号具有随机性. (5) 设完成以下动作种群数量/2次. (6) 生成一个0-1之间的随机数,如果该数小于预先指定的交叉概率,则进行以下动作,否则,跳转到第12步. (7) 设当前进行的是第i次操作.从index数组中取出第i和第i+1单元,假设其内容分别为l和m,在从当前运算的染色体种群取出第l和第m条染色体分别作为母本和父本. (8) 生成两个1N之间的随机数,分别命名为first和second,如果first大于second,则二者交换;如果二者相等,则令se

44、cond=first+1;如果二者相等且都等于N,则令first=first-1. (9) 设立两个将缓冲数组,命名为buf1和buf2,分别将母本和父本的作业序列中第first到second的作业移入buf1和buf2. (10) 对buf1中作业,按照该作业在父本作业序列中的次序,调整buf1中作业的次序,同理,对buf2中作业,按照该作业在母本作业序列中的次序,调整buf2中作业的次序.如: 母本: 4 2 | 1 3 | 6 5 父本: 2 3 | 1 4 | 5 6 buf1: 1 3 buf2: 1 4 buf1中的作业3 在父本中领先作业1,因此按照调整父本中的作业顺序进行调整.

45、同理调整buf1. buf1: 3 1 计算机辅助生产线平衡与产能分析研究 第 14 页 共 52 页 buf2: 4 1 (11) 用调整以后的buf1和buf2替代原母本和父本作业序列中first和second之间的作业的内容.交换操作后的染色体为 后代1: 4 2 3 1 6 5 后代2: 2 3 4 1 5 6 (12) 跳转到第6步,直到对种群中所有染色体均完成上述操作. 显然,交配概率决定了每次迭代中染色体交配的对数. 3.2.4.3 优化目标函数 优化目标函数确定了遗传算法的优化方向.不同的应用目的有不同的目标函数.通常单一产品生产线平衡第一类问题为给定节拍时间,希望平衡结果具有

46、最小的工作站空闲时间,即目标函数为下式的最小化 )()(11= KkkKkikMiPctc (3-3) 式中ikt为在工作站k上完成的作业iT 的时间,kP为工作站k的负荷时间.等价于 tconsKcPKcPKcPcKkkKkkKkktan)(111= = = =(3-4) 并且有 tconscKtconsKctconsKctconsKctan)min(tan)min(tan)min()tanmin(显然,节拍时间一经给定即为常数,因此最小空闲时间等价于最小工作站数量.对于第二类问题,给定工作站数量,求最小化节拍时间,根据上式,其目标函数是等价的.文献3提出了三种优化目标函数形式,即 =Kki

47、kMitKcf11 (3-5) KctfKkMiik212)( = (3-6) 313fbaff+= (3-7) 本设计采用了1f作为优化目标函数,但是同时计算了2f数值和KctKkikMi=1作为平衡结果数据提交,由用户判断优劣,其中,对一批方案中的2f进行了比较,并将2f最小的方案称为最优方案,将2f最大的方案称为最差方案. 3.2.4.4 优化目标函数转换为适应度函数的算法 基因算法要求适应度大的染色体具有较大的生存概率,因此隐含了最大值优化原则.而生产线平衡算法普遍是目标函数的最小值优化,因此需要建立优化目标函数到适应度函数的数学变换.本设计采用的线性变换方法,设种群中的染色体数为N,

48、计算机辅助生产线平衡与产能分析研究 第 15 页 共 52 页 ,.,2,1)(Nkkf=第k个染色体的优化目标函数值.为每一染色体计算 =Nkkfkfkg1)()()( (3-8) 显然,1)(0kg. 定义染色体的适应度为 = =NkkfkfkgkA1)()(1)(1)( (3-9) 这实际上是在0,1区间上的累积概率分布函数,所有染色体的优化目标函数值,.,2,1)(Nkkf=转换为0,1区间上的一段区间,染色体的优化目标函数值越小,其所占据的区间相对越大,在利用轮盘赌算法抽取下一代种群的母本和父本,就具有较大的几率.从而在迭代计算中,实现逐步寻优的目的. 3.2.5 ALB2型问题遗传算法设计 ALB2型问题与ALB1型问题的不同之处在于他们的求解目标和求解条件正好相反.ALB2是给定工作站数K,要求找到一种最优的作业分配方案使节拍时间最小.根据2.3中讲述的基本思路,我们从最小生产节拍1NiitK=开始进行迭代,使用3.2中介绍的ALB1型平衡遗传算法进行计算,如果得到的平衡方案工作站数小于或等于K,则结束计算过程.否则,将生产节拍延长一个固定值,在进行计算,直到满足工作站数K的要求为止. 3.3 混合产品生产线平衡算法 3.3.1 由多个产品紧后作业集合构造混合生产线先后关系矩阵 由多个产品的紧后作业集合构造