摘要：对批处理机随机E/T(csrliness and tardiness)调度问题,假设各批的加工时间独立同分布;各工件的交付期相互独立,并与加工时间独立;目标是极小化所有工件的提前与延迟时间和的均值.在加工时间和工件的交付期都服从指数分布的条件下,得到了最优调度的几个性质,基于这些性质用动态规划给出了一个求问题最优解的算法,此算法的时间复杂度为O(n2B2)(B＜n),从而知此时问题是多项式可解的.

关键词：调度问题 批处理机调度问题 随机调度 动态规划 

单位：南开大学信息学院; 天津300071