一种解决改机问题的限定分配调度方法

摘要

本发明涉及一种解决改机问题的限定分配调度方法，具体针对半导体后段制造过程中出现的由于不同封装外型可选设备相同、加工材料不同或者工夹具不同而导致的改机现象或者换产现象。本发明包括：步骤1：初始化；步骤2：未分配设备集不为空，转到步骤3；未分配设备集为空，转到步骤4；步骤3：统计与加工条件δ

说明书

技术领域

本发明涉及一种解决改机问题的限定分配调度方法，具体针对半导体后段制造过程中出现的由于不同封装外型可选设备相同、加工材料不同或者工夹具不同而导致的改机现象或者换产现象。

背景技术

随着制造业自动化信息程度的提高，实施信息化的生产组织管理和优化决策成了制造业迅速发展的迫切需要。生产调度作为生产组织管理的一个关键模块，其安排的是否有效与合理直接影响企业的经济效益。目前，有关生产调度方面的研究在理论界已经达到鼎盛时期，尤其是近几年来，智能算法在排产调度过程中的应用，通过合理优化的调度方案能够使多个排产性能指标的实现。然而，由于实际企业中的产品种类多、设备数量大、生产约束规则复杂等原因往往导致理论上的这些所谓的先进算法不可行。

根据企业的实际生产场景来进行调度方法的研究是实施可行排产系统调度的关键。本发明就是针对半导体生产过程中的特定调度环境进行方法研究。在半导体生产计划与调度的研究方面，目前国内的研究单位主要有同济大学和清华大学。尤其是同济大学的吴启迪、乔飞、李莉等人对半导体制造系统调度的研究颇深，发表或出版相关方面的期刊文献、发明专利、书籍很多。通过阅读其成果可知，他们主要是针对半导体前段制造系统的调度方法进行的研究。半导体前段制造指的是晶圆处理部分，后段指的是封装测试部分，这两个阶段一般在不同的企业生产。前道制造系统存在可重入调度问题，被理论界公认属于不同于Job-shop、Flow-shop系统调度的第三类调度问题。目前半导体后段制造过程相对比较简单。但是其也具有自己的生产特点，如生产过程中加工任务的流动形式发生变化，由于不同的封装外型可共用设备而导致许多工序的设备存在换产现象等等。这些问题的存在也使半导体后段制造调度不同于一般的调度问题。目前，专门针对半导体后段制造系统调度方面的研究，无论是期刊文献还是发明专利都基本没有。本发明着重针对半导体后段制造过程中“改机现象”而描述一种调度方法。这里的“改机现象”又称为“换产现象”，指同一设备上更换加工品种的现象，这种现象常会导致设备上加工材料或者工夹具的更换，从而引起一定的时间及成本代价的产生。

在文献“生产调度决策模型研究”中，卢向南提出采用与前一任务性质相近者优先的加工规则以降低换产成本。文献中并没有对该方法做详细的介绍，同时该方法也仅是以降低换产成本这个单一目标作为性能评价指标，并未考虑到资源利用均衡的问题。如果仅是考虑降低换产成本，则很可能导致严重的生产不平衡问题产生。

在实际半导体生产运行中，由于加工半导体的设备价格昂贵，企业一般不允许设备空闲。为了提高设备利用率，现场调度人员一般不考虑改机成本问题，改机频率很高，从而造成生产时间和生产成本代价的大量产生。

发明内容

针对现有技术的不足，本发明提供一种能够解决由于改机不合理而造成的时间、成本等代价的损失和设备利用不均衡问题，避免改机频繁现象的发生，同时又提高了设备整体利用率限定分配调度方法。

本发明为实现上述目的所采用的技术方案是：一种解决改机问题的限定分配调度方法，，用于调度半导体后段制造过程中的多个加工任务在多个加工设备中的工序，其特征在于，包括以下步骤：

步骤1：将待加工任务集初始化为途经本道工序的所有加工任务的集合，将未分配设备集初始化为本道工序的所有加工设备的集合；所述未分配设备集是未分配任何加工任务的设备；

步骤2：从待加工任务集中，选择前道工序最早完工的加工任务π_i，其加工条件为δ_h，未分配设备集不为空，转到步骤3；未分配设备集为空，转到步骤4；

步骤3：统计与加工条件δ_h相同的设备总计数量

计算加工条件为δ_h的允许最大设备分配数量：

式中，M_j为第j道工序的设备总数，表示满足加工条件δ_h的加工任务i在第j道工序的加工时间，表示f(x)的向上取整；如果则从未分配设备集中选择一台设备分配给加工任务π_i进行加工，将该设备的加工条件设置为δ_h，同时将该设备从未分配设备集中删除；如果则从已分配加工条件δ_h的设备中选择最早完工的设备分配给加工任务π_i，从待加工任务集中删除加工任务π_i，转至步骤5；

步骤4：在满足加工条件δ_h的设备集中选择最早结束加工任务的设备；

在满足另一加工条件δ_other的设备集中选择最早结束加工任务的设备；

如果满足

$>{\mathrm{ME}}_{M_k,{\delta }_{\mathrm{other}}}+f*R_{\delta ,j}>{\mathrm{ME}}_{M_k,{\delta }_h}---\left(2\right)$>

则将加工任务π_i分配给满足加工条件δ_h的设备集中最早结束加工任务的设备；

否则，将加工任务π_i分配给满足加工条件δ_other的设备集中的最早结束加工任务的设备，进行改机生产，从待加工任务集中删除加工任务π_i，转至步骤5；

公式(2)中，表示已分配加工条件δ_h的所有加工设备的最早结束时间；表示已分配加工条件δ_other的所有加工设备的最早结束时间；R_δ，j为工序j的改机时间；f表示代价因子，是将成本代价折合为时间代价的因子，f≥1，同样改机时间情况下，当改机成本代价较高时，则f较大；

步骤5：检查待加工任务集是否为空，如果为空，则结束本道工序的分配，进入下一道工序的分配；否则，返回到步骤2。

所述步骤3中如果则加工任务π_i在含有改机问题的工序j中的起始加工时间和结束加工时间为

$>S_{{\pi }_i,j}=E_{{\pi }_i,j-1}$>$>\left(3\right)$>

$>{E_{{\pi }_i,j}=S}_{{\pi }_i,j}+t_{{\pi }_i,j}$>

式中，表示加工任务π_i在工序j的开始加工时间；表示加工任务π_i在工序j的结束加工时间；表示加工任务π_i在工序j的加工时间；

如果则加工任务π_i在含有改机问题的工序j中的起始加工时间和结束加工时间为

$>S_{{\pi }_i,j}=\max \left\{\min \right\{E_{M_k,{\delta }_h}\},E_{{\pi }_i,j-1}\},$>$>k=\mathrm{1,2},...N_{{\delta }_h}---\left(4\right)$>

$>{E_{{\pi }_i,j}=S}_{{\pi }_i,j}+t_{{\pi }_i,j}$>

式中，表示已分配加工条件为δ_h的设备M_k完成所有已分配加工任务的结束时间。

所述步骤4中，如果满足公式(2)，则加工任务π_i在含有改机问题的工序j中的起始加工时间和结束加工时间为公式(4)所示；

如果不满足公式(2)，则加工任务π_i在含有改机问题的工序j中的起始加工时间和结束加工时间为：

$>\left(\begin{array}{cc}{S}_{{\pi }_i,j}=\min \left\{E_{M_k,{\delta }_{\mathrm{other}}}\right\}+R_{\delta ,j},& \mathrm{if}\min \left\{E_{M_k,{\delta }_{\mathrm{other}}}\right\}+R_{\delta ,j}>E_{{\pi }_i,j-1}\\ S_{{\pi }_i,j}=E_{{\pi }_i,j-1},& \mathrm{else}\end{array}\right)---\left(5\right)$>

$>{E_{{\pi }_i,j}=S}_{{\pi }_i,j}+t_{{\pi }_i,j}$>other≠h；$>k=\mathrm{1,2},...N_{{\delta }_{\mathrm{other}}}$>

式中，表示已分配加工条件不为δ_h的设备M_k完成所有已分配加工任务的结束时间；other表示加工条件不为δ_h的任意加工条件；R_δ，j为工序j中的设备的改机时间，即更换材料或者工夹具的时间。

所述在含有改机问题的工序j的设备M_k上的各个加工任务的起始加工时间和结束加工时间为：

$>S_{{\pi }_{M_k,1},j}=E_{{\pi }_{M_k,1},j-1}$>

$>S_{{\pi }_{M_k,1},j}=E_{{\pi }_{M_k,1},j-1}+\underset{i}{\Sigma }{t}_{{\pi }_{M_k,i},j}+\Sigma R_{{\delta }_h,j}---\left(6\right)$>

$>S_{{\pi }_{M_k,i},j}=E_{{\pi }_{M_k,i-1},j}+R_{{\delta }_h,j}$>

式中，表示设备M_k上第i个加工的加工任务；表示第j道工序设备M_k上第i个加工任务的起始加工时间，则表示第一个加工任务的开始加工时间；表示第j道工序设备M_k上第i个加工任务的结束时间；表示加工时间；表示改机时间，当加工条件相同，不产生改机时，

还包括改机提前预测，通过步骤4判断是否进行改机，当判断得知设备M_k需要进行改机时，则当设备M_k完成已分配的加工任务后就可以开始进行改机，无需等到下一加工任务到达后才开始改机，计算改机的开始时间为：

$>\left(\begin{array}{cc}{S}_R=\min \left\{E_{M_k,{\delta }_{\mathrm{other}}}\right\}& \mathrm{if}\min \left\{E_{M_k,{\delta }_{\mathrm{other}}}\right\}+R_{\delta ,j}>E_{{\pi }_i,j-1}\\ \min \left\{E_{M_k,{\delta }_{\mathrm{other}}}\right\}\le S_R\le E_{{\pi }_i,j-1}-R_{\delta ,j}& \mathrm{else}\end{array}\right)---\left(7\right)$>

式中S_R为最晚改机开始时间。

本发明具有以下有益效果及优点：

1.能够解决由于改机不合理而造成的时间、成本等代价的损失和设备利用不均衡问题；

2.避免了改机频繁现象的发生；

3.提高了设备整体利用率。

附图说明

图1是本发明的总体流程图；

图2是不进行设备限定分配和改机的调度实例图；

图3是不进行设备限定分配和任意改机的调度实例图；

图4是本发明提出的限定分配调度实例图。

具体实施方式

下面结合附图及实施例对本发明做进一步的详细说明。

本发明的针对改机问题而发明的限定分配调度方法的整体流程图如图1所示。以半导体后段制造过程中键合工序为例进行实例说明，图2、图3、图4为不同调度方法的结果图。其中，图2为不进行设备限定分配和改机的调度实例图；图3为不进行设备限定分配和任意改机的调度实例图；图4为本发明提出的限定分配调度实例图。对比这三个图可知，使用本发明的限定分配调度算法后，不仅减少了改机次数，降低了改机成本；同时整体设备利用率得到提高。

表1是描述了半导体后段制造过程中的键合工序的前道工序的结束加工时间以及键合工序的加工时间、加工材料等情况。

表1

根据表1中的数据信息，对整个调度方法的实施过程进行描述。对各加工任务按前道工序结束时间进行排序为：B、C、A、E、D、F、G、H、I。键合工序的设备总数为4，分别为键合机1、键合机2、键合机3、键合机4，前道工序与本道工序之间的中间运输时间不进行考虑。

初始设备分配数量限定情况如下：

利用公式(1)计算得：

分配过程进行如下：

1)根据前道工序的结束时间，首先选择加工任务B进行分配，统计已分配加工条件为金丝的设备数量n_金＝0，n_金＜N_金，将其分配给键合机1，置键合机1的加工材料为金丝。根据公式(3)计算得，加工任务B的开始加工时间和结束加工时间分别为0:15和0:28.5。

2)选择加工任务C进行分配，统计已分配加工条件为金丝的设备数量n_金＝1，n_金＝N_金，则不进行空闲设备的分配，将其分配给已分配有加工任务的设备-键合机1，利用公式(4)计算得，加工任务C的开始加工时间和结束加工时间分别为0:28.5和0:37.5。

3)选择加工任务A进行分配，统计已分配加工条件为铝丝的设备数量n_铝＝0，n_铝＜N_铝，则将加工任务A分配给键合机2，置键合机2的加工材料为铝丝。根据公式(3)计算得，加工任务A的开始加工时间和结束加工时间分别为0:23和0:48。

4)选择加工任务E进行分配，统计已分配加工条件为铜丝的设备数量n_铜＝0，n_铜＜N_铜，则将加工任务E分配给键合机3，置键合机3的加工材料为铜丝。根据公式(3)计算得，加工任务E的开始加工时间和结束加工时间分别为0:27和0:42。

5)选择加工任务D进行分配，统计已分配加工条件为铝丝的设备数量n_铝＝1，n_铝＜N_铝，则将加工任务D分配给键合机4，置键合机4的加工材料为铝丝。根据公式(3)计算得，加工任务D的开始加工时间和结束加工时间分别为0:30和0:50。

6)此时，所有空闲设备已分配完。选择加工任务F进行设备分配。利用公式(6)计算搜索得，加工条件为铝丝且最早完成已分配任务加工的设备为键合机2，结束时间为0:48；加工条件不为铝丝且最早完成已分配任务加工的设备为键合机1，结束时间为0:37.5。将各个数据代入不等式(2)中进行计算比较：0:37.5+1.6*7.5＞0:48，满足不等式(2)，则将加工任务F分配给键合机2。根据公式(4)计算得，加工任务F的开始加工时间和结束加工时间分别为0:48和1:03。

7)选择加工任务G进行分配。利用公式(6)计算搜索得，加工条件为金丝且最早完成已分配任务加工的设备为键合机1，结束时间为0:37.5；加工条件不为金丝且最早完成已分配任务加工的设备为键合机3，结束时间为0:42。将各个数据代入不等式(2)中进行计算比较：0:42+1.6*7.5＞0:37.5，满足不等式(2)，则将加工任务G分配给键合机1。根据公式(4)计算得，加工任务G的开始加工时间和结束加工时间分别为0:38和0:47。

8)选择加工任务H进行分配。利用公式(6)计算搜索得，加工条件为铝丝且最早完成已分配任务加工的设备为键合机4，结束时间为0:50；加工条件不为铝丝且最早完成已分配任务加工的设备为键合机3，结束时间为0:42。将各个数据代入不等式(2)中进行计算比较：0:42+1.6*7.5＞0:50，满足不等式(2)，则将加工任务H分配给键合机4。根据公式(4)计算得，加工任务H的开始加工时间和结束加工时间分别为0:50和1:06。

9)选择加工任务I进行分配。利用公式(6)计算搜索得，加工条件为铝丝且最早完成已分配任务加工的设备为键合机2，结束时间为1:03；加工条件不为铝丝且最早完成已分配任务加工的设备为键合机3，结束时间为0:42。将各个数据代入不等式(2)中进行计算比较：0:42+1.6*7.5＜1:03，不满足不等式(2)，则将加工任务分配给键合机3，进行改机生产。利用公式(6)计算得知改机时间S_R为0:42；利用公式(5)计算得，加工任务I的开始加工时间和结束加工时间分别为0:49.5和1:04.5。分配后的整个分配结果如附图4所示。