多人共站装配线2025作业分配方案优化

多人共站装配线2025作业分配方案优化

安装过程平衡（albp）是制造领域的一个重要问题，直接关系到安装效率和生产效率。同时，albp是典型的非模型优化问题。因此,对ALBP的研究具有重要意义。传统ALBP假设每个工作站分配一个工人进行操作,适用于自动化程度较高的装配线。然而手工或半手工生产的产品,往往因其体积较小,同一工作站内可能由几名工人同时独立地对各自负责的在制品进行一系列相同的作业,之后将操作完成的在制品通过传送装置送至下一工作站。相比单人工作站的装配线,多人共站装配线可有效平衡工作站之间工作负荷,提高工时的使用效率;提高装配线的可靠性,减小断线率。相比于ALBP,多人共站装配线平衡问题(Multi-MannedAssemblyLineBalancingProblem,MM-ALBP)不仅考虑作业的分配,而且考虑工人的分配,增加了问题求解的难度。按照传统的ABLP分类方法,将MM-ALBP分为两类:第一类(MM-ALBPI)是给定节拍时间(CycleTime,CT),最小化工人数;第二类(MM-ALBPII)是给定工人数,最小化节拍时间。目前,对MM-ALBP的研究相对较少,Simaria和Vilarinho将工作站负荷达到最小工位时间作为引入并行工作站的标准,求解MM-ALBP。Bukchin和Rubinovitz根据并行操作成本的不同情形,构建了以最小化总成本为优化目标的MM-ALBPI模型,并将人员分配问题转化成设备选择问题,从而简化模型。Ege等设定并行工作站的上限,最小化设备成本,构建了两种分支定界法分别得到最优解和似优解。Akpinar和Bayhan研究了一种同时考虑区域约束和并行工作站的混流装配线平衡问题,在给定节拍下最小化工作站数,最大化工作站负荷平衡指数以及工作站内并行工作站之间的负荷平衡指数,并构建一种混合遗传算法求解模型。钱雄文构建了MM-ALBPII的数学模型,并利用遗传算法求解。Kellegöz和Toklu研究了多人共站负责不同作业的MM-ALBP,并设计了一种高效的分支定界算法求解问题。本文主要研究MM-ALBPII,以最小化装配线节拍为主要目标,最小化平行操作工人数为第一辅助目标,最小化工人负荷标准差为第二辅助目标,构建数学模型,提出一种基于两阶段结构式译码算法的结构式译码遗传算法求解该模型。1多作业任务1MM-ALBPII可以描述为给定工人数和各工序作业时间,以及工作站能分配到的最大工人数,在满足加工优先次序关系的条件下,考虑多人共站,确定作业和人员的分配方案,以最优化目标函数。文中将使用的变量如下:N作业总数,i,g,h=1,2,…,N;J工作站数的估计上限,j=1,2,…,J;W给定工人数;K工作站能分配到的最大工人数,k=1,2,…,K;ti作业i的操作时间;C节拍时间;决策变量:根据上述变量定义,建立MM-ALBPII的数学模型:其中:ε是一个很小的数,作为惩罚因子。式(1)表示以最小化装配线节拍为主要目标,以最小化平行操作工人数为第一辅助目标,以最小化工人负荷标准差为第二辅助目标。式(2)表示装配线上分配的所有工人数等于给定工人数。式(3)表示作业之间的优先次序约束。式(4)表示工作站所分配到的作业时间总和不能超过该工作站的容量。式(5)表示一个作业只能被分配到一个工作站上。式(6)表示工作站所分配到的工人数惟一。2翻译代码的遗传计算方法设计基于文献设计一种结构式译码遗传算法,该算法在运行过程中始终只对可行作业序列子空间进行搜索,以减小搜索范围,提高搜索效率。2.1作业元素排成一列本文采用序列编码方式:按作业元素被分派至工作站的先后顺序,将作业元素排成一列,每个作业元素对应一个基因位。序列编码对目标函数和操作算子具有较强的适应性。2.2合并工作站的构建阶段1按单人工作站得到最优分配方案(1)按公式计算初始过渡节拍Cavg。(2)按基因排序分别将作业分配至当前工作站,若该工作站已含有的作业时间总和超过Cavg,则将当前工序分配到当前工作站,并进行下一工作站的分配,直至分配完所有作业,令Cavg等于该方案最大工作站工时。(3)令Cavg=Cavg-step(step为节拍下降步长),按基因排序分配至当前工作站,若该工作站已含有的作业时间总和超过Cavg,则将该工序分配至下一工作站,并开始下一工作站的分配,直至分配完所有作业,计算分配方案的工人总数WT,最大工作站工时为WLmax。(4)若WT大于给定工人数,输出最优分配方案,退出;否则令Cavg=WLmax,转(3)。阶段2合并工作站使得节拍最小化(1)找出等效工时(工作站总工时/工作站分配人数)最大的瓶颈工作站(若存在多个,则随机选择一个),记为W0,其等效工时记为ETmax。(2)分别计算瓶颈工作站与其上游和下游工作站合并之后的等效工时,较小的记为ETless,相应的工作站记为W1,较大的记为ETmore,相应的工作站则记为W2。(3)若WLless≥ETmax,则退出;否则,转(4)。(4)若瓶颈工作站与工作站W1的工人总数不超过K,则合并这两个工作站,并转(1),否则,转(5)。(5)WLmore≥ETmax,则退出;否则,转(6)。(6)若瓶颈工作站与工作站W2的工人总数不超过K,则合并这两个工作站,并转(1),否则,退出。2.3生成当前特征采用随机拓扑排序算法生成初始种群,使得初始种群中的所有作业序列都是可行作业序列,其步骤如下:(1)置当前序列为空。(2)从当前优先次序图中随机选取一个入度为0的节点插入当前序列的尾部。(3)删去当前优先次序图中该节点以及与它直接相连的边;若当前顺序图中已无节点,转(4),否则转(2)。(4)输出当前作业序列。2.4变异算子的生成交叉算子的主要思想是,首先随机在两个体内确定一个交叉片断,并通过交换两交叉片断中的相同元素子序列,生成满足作业顺序约束的新个体。具体步骤如下:(1)生成两个不同的随机数,利用它们确定交叉片断,并进而得到两交叉片断的相同元素子序列和不同元素子序列。(2)交换两交叉片断的相同元素子序列,并与原来的不同元素子序列进行归并排序,从而生成新的交叉片断,将新的交叉片断替换原交叉片断,形成新染色体。变异算子的主要思想是,使变异元素在序列中可移动范围内的前后移动实现。具体步骤如下:(1)生成一个随机整数,确定变异元素的位置,并计算该变异元素的可移动范围(即在可行序列中,变异作业的直接序前作业集中位置下标最大值,与直接序后作业集中位置下标最小值之间的范围)。(2)将该作业在可移动范围内进行随机移动。2.5初始种群p0记N(p)为种群大小,P(t)为第t代种群,Pc为交叉概率,Pm为变异概率,éxù为不超过实数x的最大整数。结构式译码遗传算法总流程如下:步骤1初始化种群,令t=0,产生初始种群P(0),其规模设为N(p)。步骤2适应度值计算,计算第t代种群P(t)中每个个体的适应度值。步骤3选择,从P(t)中选择N(p)个个体复制到P(t+1)。步骤4交叉,从P(t+1)中随机选取对个体进行交叉,产生的r对子代个体取代原来的r对父代个体。步骤5变异,从P(t+1)中随机选择个个体进行变异,生成的新个体替换原来的父代个体。步骤6精英策略,P(t)中适应度值最高的个体取代P(t+1)中适应度值最低的个体。步骤7令t=t+1,若最优值保持max＿iter次不变,则输出最优方案,结束;否则,转步骤2。3算法有效性比较为验证结构式译码遗传算法的有效性以及多人共站的优势,本文采用MATLAB实现算法,并分别针对Jackson(如图1)和Buxey(如图2)问题进行实验分析。用结构式译码遗传算法对Jackson问题进行求解。令K=2,Pc=0.8,Pm=0.2,N(p)=40,max＿iter=300,给定工人数分别为4、5、6时,分别给出其作业分配方案和人员分配方案,如表1所示。比较表1中结构式译码遗传算法与分支定界法的结果发现,两种方法得到的节拍时间、并行操作工人数、工人负荷标准差均相同,表明该算法的有效性,同时也说明本文的两阶段结构式译码算法的高效性,能将工作站上的工人进行有效合理的安排,以使节拍时间下降,同时又最小化并行操作工人数,降低并行成本。对Buxey问题,当工作站分别取8～14时,各随机运行算法10次(Pc=0.8,Pm=0.2,N(p)=100,max＿iter=3000),取得最优结果,并与文献进行比较,结果如表2所示。由表2中的求解结果可以发现:(1)当K=1,即不考虑多人共站时,结构式译码遗传算法和文献中算法得到的节拍时间均相等,但本文算法的负荷标准差更优。(2)当K=2、3时,即在多人共站条件下,结构式译码遗传算法的节拍时间、工人负荷标准差同时下降,可见多人共站可有效缩短生产节拍同时使工人间的负荷更加均衡。4结构式译码遗传算法求解匹配方案优化在多人共站装配线平衡问题中,考虑了最小节拍时间、并行操作工人数和工人负荷标准差的综合影响,以比较最小节拍时间相同的