基于规则学习的差异工件随机批调度策略

杨子豪，谭 琦，夏田林，戴 飞

（合肥工业大学 电气与自动化工程学院，合肥 230009）

0 引言

批处理机是一类在满足约束的前提下可以同时处理多个工件的设备，目前已广泛应用于制造业中，例如金属加工、半导体生产、纺织品染整作业等相关领域[1]。同时批处理问题也引起了众多学者的关注。Dupont等[2]研究了一类差异工件单机批调度问题，提出了两种启发式算法SKP（Successive Knapsack Problem）和BFLPT（Best-Fit Longest Processing Time）。Chen等[3]对于单机批调度问题，提出浪费比的概念，并以此为基础定义了批间距离度量，设计了一种分批约束聚类算法。Li等[4]针对不相容工件族的批调度问题设计了启发式算法来优化系统的最大延期时间。

在实际的制造系统中，加工制造过程存在很多不确定的随机因素，例如上游系统故障，加工订单随机到达等。调度过程中的随机事件往往使得原有静态调度方法具有不可预测性，无法达到理想效果。因此，考虑随机因素的调度模型是一种更贴近实际加工环境的调度模型。随机调度问题近年来引起众多学者的关注，然而基于随机批调度问题的研究目前还不多。Germs等[5]使用马尔科夫决策过程对一类订单随机到达的单机调度问题进行了研究，给出了最佳订单接受策略和批调度方案。Duenyas等[6]研究了不相容工件族随机到达的批调度问题，提出了一种启发式算法对平均单位时间成本进行优化。John等[7]利用动态规划的方法对工件到达时间随机的相容工件族批调度问题的进行求解，并给出一种启发式算法。……