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(D2)O(\Delta^2) and
(4D+2DÖ{4+1/D}+1)(4\Delta+2\Delta\sqrt{4+1/\Delta}+1)-competitive respectively, where Δ 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 Δ and is proved to be
(3D+ o(D))\left(3\Delta + o(\Delta)\right)-competitive for Δ > 9. Furthermore, two lower bounds for deterministic strategies,
(1.366D+ 0.366)(1.366\Delta + 0.366) and 6.33, are given for the cases of nonuniform and uniform length respectively.
Keywords On-line scheduling - Preemption penalty - Competitive strategy - Competitive ratio
This research is supported by NSF of China under Grants 70471035, 70525004, 70121001 and 70602031.