Skip to Main content Skip to Navigation
Conference papers

Worst-case bound performance of the preemptive WSPT heuristic for the problem 1, h1|pre|ΣwiCi

I. Kacem 1 Chengbin Chu 1
1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels
ICD - Institut Charles Delaunay
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 : Job shop scheduling Single machine scheduling Dynamic programming Parallel machines Heuristic algorithms Laboratories Availability Machinery production industries H infinity control Mixed integer linear programming
Document type :
Conference papers
Complete list of metadata
https://hal-utt.archives-ouvertes.fr/hal-02525626
Contributor : Daniel Gavrysiak Connect in order to contact the contributor
Submitted on : Tuesday, March 31, 2020 - 8:13:55 AM
Last modification on : Friday, August 27, 2021 - 3:14:08 PM

Identifiers

Collections

UTT | CNRS

Citation

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

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

16