单机随机排序问题的WSEPT规则近似  

Approximate with WSEPT Rule of Single Stochastic Scheduling Problems

作　　者：王艳红[1] 雷松泽[2] 张文娟[1] 李蕊[1] WANG Yanhong;LEI Songze;ZHANG Wenjuan;LI Rui(School of Science,Xi'an Technological University,Xi'an 710021;School of Computer Science and Engineering,Xi'an Technological University,Xi'an 710021)

机构地区：[1]西安工业大学理学院,西安710021 [2]西安工业大学计算机科学与工程学院,西安710021

出　　处：《计算机与数字工程》2020年第2期333-337,共5页Computer & Digital Engineering

基　　金：陕西省教育厅专项科研计划项目(编号:17JK0364);西安工业大学校长基金(编号:XAGDXJJ17027)资助。

摘　　要：为研究单机随机排序问题的近似,论文对WSEPT规则在期望值角度给以新的更深入的分析。该分析对开始期限及完工期限模型均适用,之后,通过由WSEPT的期望值与最优适应性策略排序的期望值的关系来修正上下界。从而给出WSEPT规则下的近似程度分析。In order to study the approximate of single stochastic scheduling problems,this paper gives a much stronger analysis for the expected value obtained by WSEPT rule. The analysis applies to both the start deadline and completion deadline models.Then,the upper and lower bounds are modified by the realtion between the expected value of WSEPT and the expected value of the optimal adaptive strategy ranking,thus analysis of the degree of approximation under the WSEPT rule is given.

关 键 词：单机随机排序 开始期限模型 完工期限模型 最优适应性策略 

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