Worst-case bound performance of the preemptive WSPT heuristic for the problem 1, h1|pre|ΣwiCi
Abstract
In this paper we study the single machine scheduling problem, with the aim of minimizing the weighted flowtime. The machine is unavailable during a given period and the preemption of jobs is allowed. We propose new properties of the worst-case performance of the WSPT heuristic. We give a tighter approximation of the worst-case error, and we show that the worst-case bound is equal to 2 under some conditions. The obtained results in this paper improve the previous one proposed by Lee