Title :
Worst-case bound performance of the preemptive WSPT heuristic for the problem 1, h1|pre|ΣwiCi
Author :
Kacem, Imed ; Chu, Chengbin
Author_Institution :
Inst. Charles Delaunay, Univ. of Technol. of Troyes
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
Keywords :
minimisation; single machine scheduling; minimization; preemptive WSPT heuristic; single machine scheduling problem; worst-case bound performance; Availability; Dynamic programming; H infinity control; Heuristic algorithms; Job shop scheduling; Laboratories; Machinery production industries; Mixed integer linear programming; Parallel machines; Single machine scheduling; Scheduling; availability constraint; heuristic; worst-case analysis;
Conference_Titel :
Service Systems and Service Management, 2006 International Conference on
Conference_Location :
Troyes
Print_ISBN :
1-4244-0450-9
Electronic_ISBN :
1-4244-0451-7
DOI :
10.1109/ICSSSM.2006.320676
