Search

Your search keyword '"Sitters, René"' showing total 7 results
Start Over Author "Sitters, René" Topic scheduling
Sorry, I don't understand your search. ×
7 results on '"Sitters, René"'

4. Preemptive Scheduling of Independent Jobs on Identical Parallel Machines Subject to Migration Delays

Author

Fishkin, Aleksei V., Jansen, Klaus, Sevastyanov, Sergey V., Sitters, René, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Brodal, Gerth Stølting, editor, and Leonardi, Stefano, editor

Published
2005
Full Text
View/download PDF

6. A (2+ϵ)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective

Author

Sitters, René, Yang, Liya, Econometrics and Operations Research, Amsterdam Business Research Institute, and Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands

Subjects
Scheduling, Total weighted completion time, Precedence constraints, SDG 7 - Affordable and Clean Energy, Approximation algorithm
Abstract

We give a (2+ϵ)-approximation algorithm for minimizing total weighted completion time on a single machine under release time and precedence constraints. This settles a recent conjecture on the approximability of this scheduling problem (Skutella, 2016).

Published
2018

7. Complexity of preemptive minsum scheduling on unrelated parallel machines

Author

Sitters, René

Subjects
*ALGORITHMS, *PARALLEL computers, *MACHINE theory, *APPROXIMATION theory
Abstract

Abstract: We show that the problems of minimizing total completion time and of minimizing the number of late jobs on unrelated parallel machines, when preemption is allowed, are both NP-hard in the strong sense. The former result settles a long-standing open question and is remarkable since the non-preemptive version is known to be solvable in polynomial time. A special case of the unrelated machine model is the identical machine model with the restriction that a job can only be processed on a specific subset of the machines. We show that in this model the problem of minimizing total completion time, when preemption is allowed, can be solved in polynomial time by proving that the use of preemption is redundant. [Copyright &y& Elsevier]

Published
2005
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results