Online Strategy and Competitive Analysis in Order Scheduling Problem with Threshold Bound
Yinfeng Xu, Yu Sheng · Journal of systems management · 2010
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).