Worst-case bound performance of the preemptive WSPT heuristic for the problem 1, h₁|pre|Σw_iC_i

I. Kacem (1) , Chengbin Chu (1)

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels

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

Keywords: Job shop scheduling; Single machine scheduling; Dynamic programming; Parallel machines; Heuristic algorithms; Laboratories; Availability; Machinery production industries; H infinity control; Mixed integer linear programming

Domains: Computer Science [cs]; Operations Research [cs.RO]

I. Kacem, Chengbin Chu. Worst-case bound performance of the preemptive WSPT heuristic for the problem 1, h₁|pre|Σw_iC_i. 2006 International Conference on Service Systems and Service Management, Oct 2006, Troyes, France. pp.1183-1187, ⟨10.1109/ICSSSM.2006.320676⟩. ⟨hal-02525626⟩