CN103105837B - 基于可变时间窗实施两级混合优化批处理调度的方法 - Google Patents

Abstract

一种基于可变时间窗实施两级混合优化批处理调度的方法，利用复杂问题的分解法则，目标是最小总的加权拖延时间，实施两阶段混合控制：第一阶段基于多规则组合自适应原理建立实时控制平台，采用可变时间窗滚动时域法获得批组合的实时参数等；第二阶段基于松弛方法，建立松弛化的线性整数数学模型，通过.NET和ILOG CPLEX商业化软件联合引擎求解，实现获得批排序的优化顺序。两个阶段分别解决批调度问题中组批和将所组批排序，并考虑批处理机的多重入性质，通过可变时间窗滚动时域法，满足被加工的工件批的动态实时调度特性。本发明综合考虑调度精度和CPU运行时间，实现可重入下批处理机的实时最优调度，利于半导体行业等推广应用。

Description

基于可变时间窗实施两级混合优化批处理调度的方法

所属技术领域

本发明涉及批处理生产过程调度的控制方法，尤其是指一种基于可变时间窗实施两级混合优化批处理调度的方法。

背景技术

在半导体芯片制造中，炉管区等批处理机调度是调度与控制中的一个典型的NP-hard问题，它制约着半导体制造系统的整体绩效，开展批处理机处的合理调度控制研究对改善半导体芯片生产线的性能具有重要意义。

目前，对于批处理生产过程调度，存在调度的精度和调度算法的运行时间矛盾，如启发式算法可解大规模NP-hard问题，能在合理时间内获得可行解，但解的精度有时很难达到要求；线性整数数学精确建模求解方法在求解大规模NP-hard问题，由于CPU运行时间限制，在一定限制时间得不到最优解；另外半导体行业的多重入特性进一步增加批处理生产过程调度的难度。

发明内容

针对上述现有技术中存在的技术问题，本发明提供一种基于可变时间窗实施两级混合优化批处理调度的方法，克服了多重入半导体批处理机生产过程调度的要么精度低，要么调度算法的运行时间长等的不足，以及多重入特性增加调度难度的问题。

本发明具体解决其技术问题所采用的技术方案如下：

一种基于可变时间窗实施两级混合优化批处理调度的方法，利用复杂问题的分解法原则，即基于时间序列模型分解，分解成若干个连续的可变时间窗，基于滚动时域策略实时控制，在每个时间窗内以最小总的加权拖延时间为目标，实施两阶段混合优化控制。这里“时间窗”定义为相邻两次空闲可用批处理机的装载时间间隔为一个时间窗，因平行批处理机出现空闲时间不固定，导致被装载的时刻不固定，所以时间窗的长度不是定值，即是可变时间窗。第一阶段基于多规则组合自适应原理建立实时控制平台，采用可变时间窗下的滚动时域法获得被加工的工件批具体的工序加工时间、工序剩余时间、产品交货期，产品批的优先级以及按照一定的组批原则形成的批组合等实时参数，形成数据库链接到第二阶段；第二阶段基于松弛方法，建立松弛化的线性整数数学模型，通过.NET和ILOGCPLEX商业化软件联合引擎求解，实现获得批排序的优化顺序，并将结果反馈给第一阶段，以便第一阶段装载优先级最高的批到空闲可用的批处理机上。两个阶段分别解决批调度问题中如何组批和如何将所组批排序，多重入性质被考虑，通过可变时间窗下的滚动时域法，满足被加工的工件批的动态实时调度特性。

第一阶段可获得被加工的工件批具体的工序加工时间、工序剩余时间、产品交货期，产品批的优先级以及按照一定的组批原则形成的批组合等实时参数，形成数据库，提供给第二阶段进行求解，其循环执行的具体步骤：

步骤1，上一个空闲可用的批处理机刚被装载完毕，初始化时间窗，第一阶段策略开始运行；

步骤2，获取被调度批处理机运行状态，获取被调度批处理机前缓冲器里的工件数量和所属产品族信息；

步骤3，当有一台批处理机空闲可用，产生触发事件，该空闲可用批处理机处于等待，第一阶段的实时控制平台立即组批，输出当前被加工的工件批具体的工序加工时间、工序剩余时间、产品交货期，产品批的优先级，并建立数据库，提供给第二阶段；当第二阶段将所有待加工批中优先级最高的批反馈给第一阶段时，第一阶段将该批装载到等待的空闲可用批处理机上，一个时间窗调度完毕；

步骤4，终止条件是总计划生产过程调度周期完毕，如果满足终止条件，立即停止，否则迭代返回到步骤1。

建立松弛化的线性整数数学模型并求解具体步骤：

步骤1，建立外部编程语言.NET与ILOG CPLEX商业化软件的连接，在外部编程语言引入ILOG.CPLEX.dll和ILOG.Concert.dll两个空间；

步骤2，在最小总的加权拖延时间为目标下，建立基于松弛的线性混合整数数学模型：

目标

$\mathrm{\ΣT}=\underset{i=1}{\overset{h}{\mathrm{\Σ}}}{w}_i*\max [(C_i-d_i),0]$

约束条件

$C_i=t+(\mathrm{Positionarray}\left(i\right)-1)\×\stackrel{\‾}{P_h}+P_i+{\mathrm{RP}}_i;\∀i\∈\{\mathrm{1,2},\·\·\·,h\}$

$\stackrel{\‾}{P_h}=\left(\underset{i=1}{\overset{h}{\mathrm{\Σ}}}{P}_i\right)/h$

${\mathrm{RP}}_i=\underset{q=r_i+1}{\overset{S_j}{\mathrm{\Σ}}}{P}_{\mathrm{qj}};$ $\∀i\∈\{\mathrm{1,2},\·\·\·,h\};$ $\∀j\∈\{\mathrm{1,2},\·\·\·,J\}$

Positionarray(i)∈{1,2,…,h};

Ifi≠lthen Positionarray(i)≠Positionarray(l);

这里t表示当前调度时刻；h表示在重入批处理机处等待调度的总批量数；w_i表示第i个批权重；C_i表示第i批的完成时间；d_i表示第i个批交货期；RP_i表示第i批在批处理后面的剩余加工时间；P_i表示第i个批在批处理机上的加工时间；S_j表示第j个产品的工艺总步数；r_i表示在重入批处理机上产品j的工艺数；P_qj表示第j个产品的的第q工艺所需的工艺时间；J表示在可重入批处理机上不同产品数量；表示在重入批处理机处等待调度的总批量数h的平均工序时间；优化序列位置为一维数组，可表示为：Positionarray(1),Positionarray(2),…,Positionarray(i),…,Positionarray(h)；

步骤3，从数据库读取数据，即可变时间窗下的滚动时域法下第一阶段提供的数据库；

步骤4，通过.NET和ILOG CPLEX商业化软件联合引擎求解，获得最优调度排序，运行结果反馈给第一阶段。

本发明的有益效果是，采用可变时间窗实施两级混合优化的算法将大规模NP-hard问题进行分解，批调度问题中如何组批和如何将所组批排序分别通过两个阶段来求解达到简化问题，通过可变时间窗下的滚动时域法，满足被加工的工件批的动态实时调度特性，综合考虑调度的精度和调度算法的CPU运行时间，实现多重入下可重入批处理机的实时最优调度。

附图说明

下面结合附图和实施例对本发明专利作进一步地说明。

图1为本发明重入批处理机虚拟模型图；

图中，1.输入，2.产品族一，3.缓冲器二，4.设备组三，5.输出，6.设备组四，7.缓冲器三，8.产品族j，9.设备组二，10.缓冲器一，11.设备组一；

图2为本发明基于可变时间窗实施两级混合优化批处理调度的方法中的可变时间窗下的流程图；

图3为本发明第一阶段的滚动时域策略下的流程图；

图4为本发明示例实施虚拟模型图；

图5为本发明示例实施模型的运行结果图。

具体实施方式

参见图1，具有重入特性的批处理典型虚拟模型，主要包括四个设备组：设备组一11，设备组二9，设备组三4和设备组四6，其中设备组一11是设备组二9上游设备组；设备组二9是所研究的批处理机，为多机平行（图中虚线框内，未标出）；设备组三4和设备组四6是设备组二9下游设备组。产品流向是从设备组一11进入，从设备组四6输出。设备组一11，设备组二9和设备组三4之间有缓冲器一10，设备组二9和设备组三4之间有缓冲器二3，设备组二9和设备组4之间有缓冲器三7。缓冲器一10中的工件来自设备组一11和设备组二9的重入流，缓冲器一10中的工件流向设备组二9。缓冲器二3中的工件来自设备组二9，缓冲器二3中的工件流向设备组三4。缓冲器三7中的工件来自设备组二9，缓冲器三7中的工件流向设备组四6。另外要求：设备组二9中的每个平行设备组只能加工一种产品族，如产品族一2，……，产品族j8，当某个产品批被加工时，该批不允许停止或增加工件，即抢占不允许；平行设备组二9不会同时空闲可用；设备组二9不会出现饥饿。

参见图2和图3，本发明所提供的基于可变时间窗实施两级混合优化批处理调度的方法的具体实施过程如下：

第一阶段基于多规则组合自适应原理建立实时控制平台，第二阶段基于松弛方法，建立松弛化的线性化整数数学模型，通过.NET和ILOG CPLEX商业化软件联合引擎求解。

可变时间窗下的滚动时域法从第一阶段获得被加工的工件批具体的工序加工时间、工序剩余时间、产品交货期，产品批的优先级别以及按照一定的组批原则形成的批组合等实时参数，建立数据库，提供给第二阶段进行求解，其循环执行的具体步骤：

步骤1，上一个空闲可用的批处理机刚被装载完毕，初始化时间窗，第一阶段策略开始运行；

步骤2，获取被调度批处理机运行状态，获取被调度批处理机前缓冲器里的工件数量和所属产品族信息；

步骤3，当有一台批处理机空闲可用，产生触发事件，该空闲可用批处理机处于等待，第一阶段的实时控制平台立即组批，输出当前被加工的工件批具有工序加工时间、工序剩余时间、产品交货期，产品批的优先级别等实时参数，并建立数据库，提供给第二阶段；当第二阶段将所有待加工批中优先级最高的批反馈给第一阶段（第二阶段运行时间极其短暂，一般在2分钟以下，如第二阶段在对有16个批排序只需98秒）时，第一阶段将该批装载到等待的空闲可用批处理机上，一个时间窗调度完毕；

步骤4，终止条件是总计划生产过程调度周期完毕，如果满足终止条件，立即停止，否则迭代返回到步骤1。

建立松弛化的线性整数数学模型并求解具体步骤：

步骤1，建立外部编程语言.NET与ILOG CPLEX商业化软件的连接，在外部编程语言引入ILOG.CPLEX.dll和ILOG.Concert.dll两个空间；

步骤2，在最小总的加权拖延时间为目标下，建立基于松弛的线性混合整数数学模型：

目标

$\mathrm{\ΣT}=\underset{i=1}{\overset{h}{\mathrm{\Σ}}}{w}_i*\max [(C_i-d_i),0]$

约束条件

$C_i=t+(\mathrm{Positionarray}\left(i\right)-1)\×\stackrel{\‾}{P_h}+P_i+{\mathrm{RP}}_i;\∀i\∈\{\mathrm{1,2},\·\·\·,h\}$

$\stackrel{\‾}{P_h}=\left(\underset{i=1}{\overset{h}{\mathrm{\Σ}}}{P}_i\right)/h$

${\mathrm{RP}}_i=\underset{q=r_i+1}{\overset{S_j}{\mathrm{\Σ}}}{P}_{\mathrm{qj}};$ $\∀i\∈\{\mathrm{1,2},\·\·\·,h\};$ $\∀j\∈\{\mathrm{1,2},\·\·\·,J\}$

Positionarray(i)∈{1,2,…,h};

Ifi≠lthen Positionarray(i)≠Positionarray(l);

这里t表示当前调度时刻；h表示在重入批处理机处等待调度的总批量数；w_i表示第i个批权重；C_i表示第i批的完成时间；d_i表示第i个批交货期；RP_i表示第i批在批处理后面的剩余加工时间；P_i表示第i个批在批处理机上的加工时间；S_j表示第j个产品的工艺总步数；r_i表示在重入批处理机上产品j的工艺数；P_qj表示第j个产品的的第q工艺所需的工艺时间；J表示在可重入批处理机上不同产品数量；表示在重入批处理机处等待调度的总批量数h的平均工序时间；优化序列位置为一维数组，可表示为：Positionarray(1),Positionarray(2),…,Positionarray(i),…,Positionarray(h)；

步骤3，从数据库读取数据，即可变时间窗下的滚动时域法下第一阶段提供的数据库；

步骤4，通过.NET和ILOG CPLEX商业化软件联合引擎求解，获得最优调度排序，运行结果反馈给第一阶段。

参见附图4给出一种虚拟的可重入批处理机示例模型，具有8种不同类型的设备组区域：PAN,AAN,SAN,ASI,MRH,DIK,GON和LPC，其中DIK设备组区域是研究对象，下面的视图是上面的视图的展开图。图5是基于可变时间窗实施两级混合优化批处理调度的方法，在某个时间窗下基于松弛线性整数模型在ILOG CPLEX下有10个待调度批的具体总运行时间，目标值和最优调度排序信息。

Claims (3)

1.一种基于可变时间窗实施两级混合优化批处理调度的方法，其特征在于，包括实施两阶段混合优化控制：第一阶段建立实时控制平台，第二阶段建立松弛化的线性整数数学模型，采用可变时间窗下的滚动时域法循环执行实时调度控制，其中：第一阶段基于多规则组合自适应原理建立实时控制平台，提供第二阶段所需的相关数据，第二阶段基于松弛方法，建立松弛化的线性整数数学模型，将第一阶段获得被加工的工件批具有工序加工时间、工序剩余时间、产品交货期，产品批的优先级别以及按照一定的组批原则形成的批组合实时参数，通过.NET和ILOG CPLEX商业化软件建立引擎求解，实现获得批排序的优化顺序，将运行结果中优先级最高批反馈给第一阶段，并立即装载到空闲可用的批处理机上，循环往复执行，直至终止条件满足。

2.根据权利要求1所述的基于可变时间窗实施两级混合优化批处理调度的方法，其特征在于，所述采用可变时间窗下的滚动时域法循环执行的具体步骤如下：

步骤1，上一个空闲可用的批处理机刚被装载完毕，初始化时间窗，第一阶段策略开始运行；

步骤2，获取被调度批处理机运行状态，获取被调度批处理机前缓冲器里的工件数量和所属产品族；

步骤3，当有一台批处理机空闲可用，产生触发事件，该空闲可用批处理机处于等待，第一阶段的实时控制平台立即组批，输出当前被加工的工件批具体的工序加工时间、工序剩余时间、产品交货期，产品批的优先级别实时参数，并建立数据库，提供给第二阶段；当第二阶段将所有待加工批中优先级最高的批反馈给第一阶段时，第一阶段将该批装载到等待的空闲可用批处理机上，一个时间窗调度完毕；

步骤4，终止条件是总计划生产过程调度周期完毕，如果满足终止条件，立即停止，否则迭代返回到步骤1。

3.根据权利要求1所述的基于可变时间窗实施两级混合优化批处理调度的方法，其特征在于，所述第二阶段建立松弛化的线性整数数学模型并求解的具体步骤如下：

步骤1，建立外部编程语言.NET与ILOG CPLEX商业化软件的连接，在外部编程语言引入ILOG.CPLEX.dll和ILOG.Concert.dll两个空间；

步骤2，在最小总的加权拖延时间为目标下，建立基于松弛的线性混合整数数学模型：

目标

$\mathrm{\ΣT}=\underset{i=1}{\overset{h}{\mathrm{\Σ}}}{w}_i*\max [(C_i-d_i),0]$

约束条件

$C_i=t+(\mathrm{Positionarray}\left(i\right)-1)\×\stackrel{\‾}{P_h}+P_i+{\mathrm{RP}}_i;$ $\∀i\∈\{\mathrm{1,2},\·\·\·,h\}$

$\stackrel{\‾}{P_h}=\left(\underset{i=1}{\overset{h}{\mathrm{\Σ}}}{P}_i\right)/h$

${\mathrm{RP}}_i=\underset{q=r_i+1}{\overset{S_j}{\mathrm{\Σ}}}{P}_{\mathrm{qj}};$ $\∀i\∈\{\mathrm{1,2},\·\·\·,h\};$ $\∀j\∈\{\mathrm{1,2},\·\·\·,J\}$

Positionarray(i)∈{1,2,…,h};

Ifi≠lthen Positionarray(i)≠Positionarray(l);

这里t表示当前调度时刻；h表示在重入批处理机处等待调度的总批量数；w_i表示第i个批权重；C_i表示第i批的完成时间；d_i表示第i个批交货期；RP_i表示第i批在批处理后面的剩余加工时间；P_i表示第i个批在批处理机上的加工时间；S_j表示第j个产品的工艺总步数；r_i表示在重入批处理机上产品j的工艺数；P_qj表示第j个产品的的第q工艺所需的工艺时间；J表示在可重入批处理机上不同产品数量；表示在重入批处理机处等待调度的总批量数h的平均工序时间；优化序列位置为一维数组，可表示为：Positionarray(1),Positionarray(2),…,Positionarray(i),…,Positionarray(h)；

步骤3，从数据库读取数据，即可变时间窗下的滚动时域法下第一阶段提供的数据库；

步骤4，通过.NET和ILOG CPLEX商业化软件联合引擎求解，获得最优调度排序，运行结果反馈给第一阶段。