基于有约束的最小生成树的半导体封装测试细日投料控制方法

摘要

半导体封装测试生产是一个流程高度复杂，资金高度密集的加工过程，相对于其它制造业来说，其产品种类繁多，工序复杂，对设备的利用率要求较高，因而日细投料控制对于提高生产系统瓶颈设备的利用率起着重要的作用。本发明针对瓶颈设备，将要解决的问题建模为图论中求解有约束的最小生成树的问题，通过得到一个有约束的最小生成树，从而得到各个产品的具体的投料顺序和投料的具体时刻。该方法解决了盲目投料导致的瓶颈问题，最后，通过应用研究验证了该方法的有效性和优越性，所提出的方法能够降低改机代价，缩短生产周期，提高生产效益。

主权项

1.一种基于有约束的最小生成树的半导体封装测试细日投料控制方法，其特征在于，包括以下步骤：步骤1：从当前的日粗投料控制表中获取某一天的要投料的产品的种类数量n，初始化为日细投料计划的所有要加工产品的集合；并且从当前的日粗投料控制表中获取各个产品的生产数量C_i；步骤2：对步骤1中的产品集合，得到这n种产品两两之间的改机代价；步骤3：对于产品集合内的n种产品，则构成一个图的n个顶点，并且任何两种产品之间的改机代价构成了条边的权值；这样得到一个完全无向连通图G=(V,E)，图的顶点集合V是各种投料产品的集合，边的集合E是投料产品之间两两转换所有可能的集合；给每条边赋给一个权值(u,v)，表示投料产品之间的改机代价；步骤4：初始化一个上述刚刚转化后的含有n个顶点的完全无向图G=(V,E)的每个顶点的度，即给每个顶点k∈V赋予新的度数D_k=0；步骤5：初始化目标树的顶点的集合Vnew={x}，其中x为顶点集合V中的任一节点即起始点，初始化目标树的边的集合Enew={}；步骤6：重复下列1）和2）两个操作，直到Vnew=V；1）.在集合E中选取权值最小的边(u,v)，其中u为集合Vnew中的元素，且顶点u的度D_u≤1；而v则不是Vnew中的元素，如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一；2）.将顶点v加入集合Vnew中，将权值最小的边(u,v)加入集合Enew中，并将D_v++;D_u++，即顶点u和v的度数加1；步骤7：输出由集合Vnew和Enew得到的最小生成树T；步骤8：从得到的最小生成树T中的任意一个度为1的顶点开始，沿着它所连接的边访问一遍该树所有的顶点，即可得到产品的生产顺序；步骤9：根据产品的生产顺序以及各个产品的生产数量C_i，通过该设备的产能采用下列公式（1）和公式（2）获得每个产品的具体的投料时刻；先计算各产品的加工时间：$t_i=\frac{C_i}{V_i}---\left(1\right)$式（1）中，C_i=产品i的生产数量，V_i=设备对于产品i的产能然后得到各个产品的具体的投料时刻：T_i+1=T_i+t_i+x_i,i+1        （2）式（2）中，x_i,i+1=产品i到产品i+1的改机代价。