有阈值约束的占线订单加工策略及竞争分析  

Online Strategy and Competitive Analysis in Order Scheduling Problem with Threshold Bound

作　　者：徐寅峰[1,2] 余昇[1] 郑斐峰[1] 

机构地区：[1]西安交通大学管理学院,西安710049 [2]西安交通大学机械制造系统工程国家重点实验室,西安710049

出　　处：《系统管理学报》2010年第5期571-576,共6页Journal of Systems & Management

基　　金：国家杰出青年基金资助项目(70525004);国家自然科学基金资助项目(70702030;70602031);教育部博士点新教师基金资助项目(20070698053)

摘　　要：结合生产订单管理的实际情形,将服务质量(QOS)的概念引入订单排序加工问题,并运用占线理论与竞争分析方法对此问题进行建模与剖析。在有QOS要求的模型中,订单收益与订单完成百分比成正比;在实际情况下,只有当订单完成百分比超过一定量时才是有效加工并获得相应收益。因此,构建了具有完成度阈值限制的可中断占线订单加工模型;其次,运用贪婪设计思想给出一个确定性占线策略并证明其具有竞争比(1+3α)/(1+α),其中,α∈[2/3,1)是订单完成度阈值参数。Combining actual situations in order processing management,we introduce the concept of quality of service（QOS） to order scheduling,and adopt online theory and the method of competitive analysis in problem modeling and analysis.In QOS online model,the revenue of an order to be obtained by an online strategy increases in the length of time to process the order,and we further consider the case where no revenue can be obtained from an preempted order unless the percentage to be processed is large enough,i.e.,no less than the threshold bound α∈（0,1）.We first establish an online order processing model with threshold bound of completion degree of order.A greedy strategy is then put forward and proved to be（（1＋3α）/（1＋α））-competitive,where α∈[2/3,1）.

关 键 词：订单排序 完成度阈值 竞争比 占线策略 

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