On-line production order scheduling with preemption penalties

被引:12
作者
Zheng, Feifeng [1 ]
Xu, Yinfeng [1 ,2 ]
Zhang, E. [3 ]
机构
[1] Xi An Jiao Tong Univ, Sch Management, Xian 710049, Shaanxi, Peoples R China
[2] State Key Lab Mfg Syst Engn, Xian 710049, Shaanxi, Peoples R China
[3] Shanghai Univ Finance & Econ, Sch Informat Managment & Engn, Shanghai 200433, Peoples R China
基金
美国国家科学基金会;
关键词
on-line scheduling; preemption penalty; competitive strategy; competitive ratio;
D O I
10.1007/s10878-006-9027-3
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
This paper studies the on-line production order scheduling problem where each preemption causes a penalty, and the objective is to maximize the net profit, i.e., the total weights of completed orders minus the total penalties caused by preemptions. Two greedy strategies are shown to be at best O(Delta(2)) and (4 Delta + 2 Delta root 4+1/Delta + 1)-competitive respectively, where Delta is the ratio between the longest and shortest length of order. After that we mainly present an improved strategy, named WAL, which takes advantage of the knowledge of Delta and is proved to be (3 Delta + o(Delta))-competitive for Delta>9. Furthermore, two lower bounds for deterministic strategies, (1.366 Delta + 0.366) and 6.33, are given for the cases of nonuniform and uniform length respectively.
引用
收藏
页码:189 / 204
页数:16
相关论文
共 15 条