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

A Heuristic Algorithm for Maximize the Expectation of Early Jobs

作　　者：吴明[1] 沈灏[1] 

机构地区：[1]杭州电子科技大学理学院,浙江杭州310018

出　　处：《杭州电子工业学院学报》2004年第4期15-18,共4页Journal of Hangzhou Institute of Electronic Engineering

基　　金：国家自然科学基金(10371028);省教育厅重点项目(20030622)

摘　　要：该文讨论工件加工时间为随机变量的单台机排序极大化期望按期完工工件数问题。在确定性排序问题中,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.

关 键 词：随机排序 启发式算法 时间复杂性 

分 类 号：O212[理学—概率论与数理统计]