摘要
对批处理机随机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.
出处
《系统工程理论与实践》
EI
CSCD
北大核心
2005年第10期114-119,共6页
Systems Engineering-Theory & Practice
基金
国家自然科学基金(69674013)
国家攀登计划(970211017)
关键词
调度问题
批处理机调度问题
随机调度
E/T调度
动态规划
scheduling problem
batch processor scheduling problem
stochastic scheduling
E/T scheduling
dynamic programming
