一个批处理机随机E/T调度问题研究  

An Earliness and Tardiness Stochastic Scheduling Problem on a Batch Processor

作　　者：张丽华[1] 涂菶生[1] 

机构地区：[1]南开大学信息学院,天津300071

出　　处：《系统工程理论与实践》2005年第10期114-119,共6页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(69674013);国家攀登计划(970211017)

摘　　要：对批处理机随机E/T(earliness and tardiness)调度问题,假设各批的加工时间独立同分布;各工件的交付期相互独立,并与加工时间独立;目标是极小化所有工件的提前与延迟时间和的均值.在加工时间和工件的交付期都服从指数分布的条件下,得到了最优调度的几个性质,基于这些性质用动态规划给出了一个求问题最优解的算法,此算法的时间复杂度为O(n2B2)(B<n),从而知此时问题是多项式可解的.To an earliness and tardiness stochastic scheduling problem on a batch processor, let processing time of various batches be i. i. d （ independent identical distributed） ; the due dates of various jobs be independent, and independent with the processing time of various batches ; the objective is to minimize the expected total earliness and tardiness of jobs. When processing times and due dates are random variables exponentially distributed with known rates, several properties of the optimal schedule are found; based on these properties, an algorithm using dynamic programming to find the optimal solution is proposed, the time complexity of the algorithm is 0 （ n^2 B^2 ） （ B 〈 n ）, thus the problem under such condition is polynomially solvable.

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

分 类 号：O22[理学—运筹学与控制论]