期望按期完工工件数最大化算法研究

A Heuristic Algorithm for Maximize the Expectation of Early Jobs

该文讨论工件加工时间为随机变量的单台机排序极大化期望按期完工工件数问题。在确定性排序问题中,Moore算法给出问题的最优解,但事实上Moore算法的期望值版本不能给出期望按期完工工件数最大化问题的最优解。文章从研究排序中工件的按期完工置信系数入手,结合Moore算法,提出了一个启发式算法,有效地解决了该随机排序问题的实际计算。

This paper discusses stochastic single machine scheduling problem to maximize the expectation of early jobs when the processing times are random variables. The Moore Algorithm gives the optional solution for the problem of deterministic model, but not leads an optional algorithm for stochastic version to maximize the expectation of early jobs. Combine the Moore Algorithm with the probability of being finished processing in time of each job, we propose a heuristic algorithm for the stochastic problem, which is very effective in the practical calculation.