On-line production order scheduling with preemption penalties

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(Δ²) and (4Δ + 2Δ√4 + 1/Δ + 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 (3Δ + o(Δ))-competitive for Δ > 9. Furthermore, two lower bounds for deterministic strategies, (1.366Δ + 0.366) and 6.33, are given for the cases of nonuniform and uniform length respectively.