考虑平衡和调度的时间问题

【热点导读】：三相异步电动机电机启动常见故障  机电一体化技术现状和发展趋势  数控技术和装备发展趋势及对策
考虑平衡和调度的时间问题 更多内容源自 幼 儿
    平衡与调度一直是针对混流装配线研究的两个重要方面,它们是互相影响的。尤其是工作站已定的混流装配线平衡问题(Mixed-modelassemblylinebalancingproblem,MALBP),如MALBP-II,关注的是生产过程中的调整以及订单变化引起的装配线重设计,与混流装配线的调度同属于混流装配线设计的中短期决策问题。Kim[1]采用稳态遗传算法的思想,建立起一种局部进化的共生进化算法模型,优化了作业负荷绝对偏差。Miltenburg[2]提出一种混合编码的遗传算法,通过目标加权法优化了最小化作业负荷绝对偏差和平顺化生产过程各环节生产率这两个目标函数。Yakup[3]用模拟退火算法同时优化了作业负荷绝对偏差,零部件消耗率,设备更换成本3个目标函数。在这些文献中,大部分以U型混流装配线作为研究的对象,针对直线型混流装配线平衡调度问题的文献很少。最小化临时工工作时间不仅能降低雇佣成本而且能降低停线的危险。很多文献将最小化临时工雇佣成本作为优化指标[4~7]。在这些文献中,混流装配线的调度优化问题都是在假定生产线已经完全平衡的前提下进行的。但在实际生产过程中经常会出现订单改变等情况,原先的平衡结果也许不再能满足生产优化的要求。作为计算临时工工作时间的重要变量之一,生产模型在工作站的加工时间是由工序分配决定的,不同生产模型可能需要不同的工序集合,且不同生产模型的相同工序可能需要不同的时间。这就导致平衡与调度之间互有影响,不能再被单独考虑。本文中研究了直线型混流装配线的平衡调度问题,以最小化混流装配线临时工工作时间为优化目标,研究工序分配和产品排序对临时工工作时间的共同影响。因为混流装配线的平衡与调度问题均为NP难的组合优化问题,考虑到算法效果及运行时间,本文提出了一种基于免疫克隆选择算法的混合策略(hybridstrategyforbalancingandsequencing,HS_BS):第一步单独考虑平衡问题:依据产品比率,以可行工序序列编码,采用克隆选择算法(clonalselectionalgorithmforbalancingproblem,CSA_BP)获得平衡问题初始解。第二步同时考虑平衡与调度,优化目标函数:以产品投放序列编码,解码时调用工序局域搜索(tasksequencelocalsearch,TSLS)算法调整已得的平衡初始解,以获得针对特定产品序列的最佳工序分配。最后用实例及仿真验证比较了本文算法。
    1问题描述与数学模型
    本文中以最小化直线型混流装配线的临时工工作时间为目标函数。工序分配需满足优先级约束,产品投产顺序满足MPS(minimumpartset)准则。以下数学模型由HyunCJ[5]改进而得JI
    2算法设计
    2.1求解初始工序分配的CSA_BP算法本文算法在寻找最优产品投放序列时,需对工序分配做出调整,因此平衡初始解的质量很重要。由于此时并不考虑生产模型排序的影响,可利用联合工序优先图及MPS比率法,将MALBP转化为SALBP(simpleassemblylinebalancingproblem)解决。但SALBP问题仍为NP难问题,而克隆选择算法依靠抗体高频变异产生抗体多样性,能有效的避开遗传算法的早熟收敛问题[8],适用于此类NP难问题的求解。本文采用单目标的克隆免疫算法求解初始工序分配问题,算法关键操作说明如下:1)编码算法选择基于可行工序序列的编码方式,抗体长度为工序总数K。2)解码解码过程分为两步。第一步将抗体编码所表示的工序序列分配至J个工作站。第二步,依据算法目标函数值计算抗体亲和度。这两步操作联系非常紧密,如何分配工序将直接影响目标函数值的计算。因此,应依据同一个准则,据其先将工序分配完毕,再根据每个工作站的工序时间计算与选取准则的偏差,并以此作为抗体优劣的评判依据。这里采用理论最小生产节拍minct作为这两步操作的准则,并以负荷均衡偏差作为CSA_BP算法的目标函数。工序分配步骤如下:(1)设已知可行工序序列为T1T2T3…TK。对工作站1,按照工序序列依次分配工序,并计算已分配工序加工时间之和,直至时间之和大于minct,记此时最后一个分配的工序为Ti。式中:R为一个MPS循环中生产的产品总数。以式(9)做目标函数可以平顺化工作负荷,使装配线在不考虑混流排序的情况下让工序尽可能平均的分配至各个工作站。因为临时工加工时间是由于额定的工作站时间不能满足某产品在此工作站的工序总加工时间而产生的,所以与工作站的工作负荷有很大关系。采用CSA_BP算法得到的平衡初始解有利于算法对工序分配做进一步的优化。3)克隆比率种群内某抗体Ai的克隆比率定义为Milternberg[9]在研究中指出:对于不同产品模型,加工时间差异较大的工序更容易引起工作站生产的不平衡;交换相关性为正的工序对比相关性为负的工序对更容易引起工作站生产的不平衡。因此
    2.2调整工序分配的TSLS算法在调用CSA_BP算法得到平衡初始解后,混合策略调用TSLS算法,用于对平衡初始解作局部调整,以便算法在寻找最佳产品排序时,可以针对每一种排序方式得到最合适的工序分配。首先给出以可交换域的数学表达:设从工序k到其被分配的工作站的映射为f(k),定义逻辑功能函数l(k,j):如果工序k可以从工作站f(k)调至工作站j,则l(k,j)为1;否则,l(k,j)为0。判断条件如下2.3混合算法HS_BS混合策略的主体框架仍然采用克隆选择算法以调度问题作为主问题,采用产品序列直接编码算法开始先调用CSA_BP算法,得到平衡初始解,作为后续算法的基本参数。HS_BS算法的关键操作与CSA_BP大体类似,但有以下两点不同:1)以式(1)作为目标函数,解码时调用TSLS算法;2)生产模型的顺序不存在约束,因此在变异后不需要做出调整。HS_BS算法结构如图1所示。
    3算法比较及实例仿真
    某底盘装配线共生产5种车型,装配线上共完成25道工序,联合工序优先图如图2所示。实际生产中,装配线运行速度为2m/min。为计算及表示方便,这里假设装配线速度为1,则相应的投产间隔为100。每种车型的工序完成时间见表1。共有13个有效工位,工位间距为150。
    3.1与协同进化算法的比较为与本文提出的混合策略比较,针对最小化直线型混流装配线的临时工工作时间这个目标函数,本文设计了一种以免疫克隆选择算法为子种群进化流程的单目标协同进化算法(co-evolutionclonalse-lectionalgorithm,CECSA)。平衡与调度子种群分别编码,对目标函数联合解码,具体算法流程为文献[10]算法略作改动所得。本文算法均用C++编写,各组实验运行环境均为Pentium4CPU3.00GHz,1.00G内存。CSA_BP种群大小100,迭代次数为50。HS_BS种群大小100,迭代次数30,可调系数α取为5,变异率0.1。以上参数由多次实验获得。相应地,协同进化算法子种群大小均为100,迭代次数取80。为更好评价算法性能,本文采取不同的MPS比例共产生10组实验,MPS循环模型总数分布在15~20之间,具体比例值见表2。针对每组实验,两种算法都运行10次并取平均结果。图中数据可以看出,HS_BS的运行所需时间远少于CECSA算法,且算法运行时间随问题规模大小的变化更为明显。图4为两种算法10组实验所得的目标函数平均值。图中数据说明,在MPS序列包含较少的生产模型时,HS_BS优势并不显着。但生产模型较多时,HS_BS与CECSA结果之间的差距变大,体现出较大的优势。这是因为这两种算法的寻解空间不同。如果可行工序分配共有M个可行解,模型生产序列共有N个组合。HS_BS算法首先是在M个工序分配解上寻找最优解,而后在N空间大小的生产序列上寻优。解空间的大小为M+N。而对于CECSA,解空间的大小为两者向量积M×N。随着N的增加,HS_BS的解空间增长速度远小于CECSA。因此在大规模问题求解时,HS_BS的算法结果的优势更为明显。
    3.2eM-PLANT仿真采用eM-PLANT软件对实验结果进行仿真,以证实同时从工序分配及产品排序两个方面对混流装配线进行优化,是否能进一步降低临时工工作时间。选取比例2∶6∶3∶5∶4为仿真算例的MPS比例。为生成对比结果,采用完整算法和不调用TSLS的算法各产生一组解(分别为解I和解II)。解II可以认为是单独考虑平衡及调度所得的混流装配线优化结果。两组解的工序分配与产品排序如表3所示。eM-PLANT软件中,一般用SingleProc物流对象对工作站进行仿真。很多文献也是采用这种方法。但是在混流装配线中使用这个对象,是将有长度的工位虚拟成一个只有加工时间属性的节点。而本文所要优化的目标函数需要在空间上进行计算,因此使用SingleProc控件是不合适的。本文利用eM-PLANT软件中的另一个物流对象line来对装配线进行仿真,并在产品进入和离开工作站时对其进行方法控制,以获取产品的加工状态,从而可以得到每一个工作站在任何时刻的临时工加工时间。仿真界面如图5所示。图中UtilityWork变量记录了仿真运行时各个工位的临时工工作时间之和。图6为表3两组解仿真时UtilityWork变量随时间变化对比图(用eM-PLANT中Chart对象记录数据并绘制)。从图中曲线可以看出,解I的临时工加工时间产生较晚,而且在一个MPS生产周期结束时的总值明显小于解II所得。这说明在混流装配线生产中,同时从平衡和调度两个方面优化的确可以进一步降低直线型混流装配线的临时工加工时间。
    4结论
    针对直线型混流装配线的平衡调度问题,提出了一种基于克隆选择算法的混合策略,以对最小化临时工工作时间这一目标函数进行优化。以协同进化算法作为本文算法的比较算法,选取不同MPS比例进行10组实验。结果证明本文提出的混合算法在运行时间上优于协同进化算法,在大规模问题上的算法结果也体现出较大优势。并用eM-PLANT软件对算法结果进行仿真。仿真结果证明,相对于先平衡再调度的优化策略,同时对直线型混流装配线进行工序分配和产品投放顺序的优化可以得到更小的临时工加工时间,从而得到更低的雇佣成本及进一步减小装配线停线危险。