基于产品族排序实现最小总完工时间的批调度方法

摘要

一种用于可重入生产线的基于产品族排序实现最小总完工时间的批调度方法，目标函数是所调度批的最小总完工时间，通过模型分解，先以可重入批处理机前的缓冲器里不同产品族为研究对象，再以优先权最高的产品族中工件为研究对象，利用产品族加权最短加工时间优先规则，最大重入次数优先规则，先到先服务规则和满批规则分步骤实施，在滚动时域策略下完成实施全部调度周期任务。本发明不需要实施常规情况下的不同产品族中工件的组批和批排序，极大地降低算法的时间复杂度，且使用精确算法实现可重入下批处理机的实时最优调度，满足半导体行业最小总完工时间为目标的生产需求，它概念简单，实现方便，利于半导体等可重入的行业推广应用。

主权项

一种基于产品族排序实现最小总完工时间的批调度方法，其特征在于，目标函数是所调度批的最小总完工时间，通过模型分解，先以可重入批处理机前的缓冲器里不同产品族为研究对象，再以优先权最高的产品族中工件为研究对象，利用产品族加权最短加工时间优先规则，最大重入次数优先规则，先到先服务规则和满批规则分步骤实施，在滚动时域策略下完成实施全部调度周期任务；模型分解是将通用的批处理调度模型“单处理机|不同工件j到达时间，批调度，可重入，产品族之间不能混合组批|最小总完工时间目标”分解成模型“单处理机|批调度，可重入，产品族之间不能混合组批|最小总完工时间目标”和模型“单处理机|不同工件j到达时间，产品族f中所有工件j加工时间相同|最小总完工时间目标”；产品族加权最短加工时间优先规则是令p_f表示产品族f的加工时间，n_f表示产品族f中包含工件数量，计算所有的产品族的加工时间和该产品族所包含工件数量的比值(p_f/n_f)，所有的产品族优先按比值(p_f/n_f)的不减原则进行排序；最大重入次数优先规则是指在产品族加权最短加工时间优先规则实施中出现相等产品族的加工时间和该产品族所包含工件数量的比值(p_f/n_f)时，按在产品族重入次数的不减原则进行排序；满批规则是指进行工件组批时，除最后一个批中的工件数量大于或等于批的最小容量外，其余各批中工件数量必须等于批的最大容量；基于产品族排序实现最小总完工时间的批调度方法的具体流程如下：步骤1，产生触发事件：一台可重入批处理机处于空闲可用状态；步骤2，根据可重入批处理机前的缓冲期里的不同产品族的工件数量信息，基于“产品族加权最短加工时间优先规则”和“最大重入次数优先规则”对批处理机前缓冲器里的产品族工件排序，即首先计算所有的产品族的加工时间和该产品族所包含工件数量的比值(p_f/n_f)，所有的产品族优先按比值(p_f/n_f)的不减原则进行排序，当实施产品族加权最短加工时间优先规则排序中出现相等产品族的加工时间和该产品族所包含工件数量的比值(p_f/n_f)时，再按“最大重入次数优先规则”排序；步骤3，根据步骤2的产品族的排序结果，选取优先权最高的产品族；步骤4，对优先权最高的产品族中的工件，基于“先到先服务规则” 排序；步骤5，根据步骤4的排序工件结果，基于“满批规则”组建该排序工件的第一个批；步骤6，将步骤5组建的第一个批的工件分配到步骤1的空闲可用的批处理机；步骤7，“调度终止条件”判断：如果不符合“调度终止条件”，根据滚动时域策略，跳转到步骤1，否则往下执行；步骤8，基于产品族排序实现最小总完工时间的批调度方法终止。