Approximate Deadline-Scheduling with precedence constraints

Hossein Efsandiari; Mohammad Taghi Hajiaghyi; Jochen Könemann; Hamid Mahini; David Malec; Laura Sanit À

doi:10.1007/978-3-662-48350-3_41

Approximate Deadline-Scheduling with precedence constraints

Hossein Efsandiari, Mohammad Taghi Hajiaghyi, Jochen Könemann, Hamid Mahini, David Malec, Laura Sanit À

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

2 Citaten (Scopus)

Samenvatting

We consider the classic problem of scheduling a set of n jobs non-preemptively on a single machine. Each job j has non-negative processing time, weight, and deadline, and a feasible schedule needs to be consistent with chain-like precedence constraints. The goal is to compute a feasible schedule that minimizes the sum of penalties of late jobs. Lenstra and Rinnoy Kan [Annals of Disc. Math., 1977] in their seminal work introduced this problem and showed that it is strongly NP-hard, even when all processing times and weights are 1. We study the approximability of the problem and our main result is an O(log k)- approximation algorithm for instances with k distinct job deadlines.

Originele taal-2	Engels
Titel	Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings
Redacteuren	Nikhil Bansal, Irene Finocchi
Uitgeverij	Springer
Pagina's	483-495
Aantal pagina's	13
ISBN van geprinte versie	9783662483497
DOI's	https://doi.org/10.1007/978-3-662-48350-3_41
Status	Gepubliceerd - 2015
Extern gepubliceerd	Ja
Evenement	23rd European Symposium on Algorithms, ESA 2015 - Patras, Griekenland Duur: 14 sep. 2015 → 16 sep. 2015

Publicatie series

Naam	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9294
ISSN van geprinte versie	0302-9743
ISSN van elektronische versie	1611-3349

Congres

Congres	23rd European Symposium on Algorithms, ESA 2015
Land/Regio	Griekenland
Stad	Patras
Periode	14/09/15 → 16/09/15

Toegang tot document

10.1007/978-3-662-48350-3_41

Andere bestanden en links

Link to publication in Scopus

Citeer dit

Efsandiari, H., Hajiaghyi, M. T., Könemann, J., Mahini, H., Malec, D., & Sanit À, L. (2015). Approximate Deadline-Scheduling with precedence constraints. In N. Bansal, & I. Finocchi (editors), Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings (blz. 483-495). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9294). Springer. https://doi.org/10.1007/978-3-662-48350-3_41

Efsandiari, Hossein ; Hajiaghyi, Mohammad Taghi ; Könemann, Jochen et al. / Approximate Deadline-Scheduling with precedence constraints. Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings. redacteur / Nikhil Bansal ; Irene Finocchi. Springer, 2015. blz. 483-495 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{4dd1b3b85b1b494aac7e088eb42bac50,

title = "Approximate Deadline-Scheduling with precedence constraints",

abstract = "We consider the classic problem of scheduling a set of n jobs non-preemptively on a single machine. Each job j has non-negative processing time, weight, and deadline, and a feasible schedule needs to be consistent with chain-like precedence constraints. The goal is to compute a feasible schedule that minimizes the sum of penalties of late jobs. Lenstra and Rinnoy Kan [Annals of Disc. Math., 1977] in their seminal work introduced this problem and showed that it is strongly NP-hard, even when all processing times and weights are 1. We study the approximability of the problem and our main result is an O(log k)- approximation algorithm for instances with k distinct job deadlines.",

author = "Hossein Efsandiari and Hajiaghyi, {Mohammad Taghi} and Jochen K{\"o}nemann and Hamid Mahini and David Malec and {Sanit {\`A}}, Laura",

year = "2015",

doi = "10.1007/978-3-662-48350-3_41",

language = "English",

isbn = "9783662483497",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "483--495",

editor = "Nikhil Bansal and Irene Finocchi",

booktitle = "Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings",

address = "Germany",

note = "23rd European Symposium on Algorithms, ESA 2015 ; Conference date: 14-09-2015 Through 16-09-2015",

}

Efsandiari, H, Hajiaghyi, MT, Könemann, J, Mahini, H, Malec, D & Sanit À, L 2015, Approximate Deadline-Scheduling with precedence constraints. in N Bansal & I Finocchi (uitgave), Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9294, Springer, blz. 483-495, 23rd European Symposium on Algorithms, ESA 2015, Patras, Griekenland, 14/09/15. https://doi.org/10.1007/978-3-662-48350-3_41

Approximate Deadline-Scheduling with precedence constraints. / Efsandiari, Hossein; Hajiaghyi, Mohammad Taghi; Könemann, Jochen et al.
Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings. uitgave / Nikhil Bansal; Irene Finocchi. Springer, 2015. blz. 483-495 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9294).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

TY - GEN

T1 - Approximate Deadline-Scheduling with precedence constraints

AU - Efsandiari, Hossein

AU - Hajiaghyi, Mohammad Taghi

AU - Könemann, Jochen

AU - Mahini, Hamid

AU - Malec, David

AU - Sanit À, Laura

PY - 2015

Y1 - 2015

N2 - We consider the classic problem of scheduling a set of n jobs non-preemptively on a single machine. Each job j has non-negative processing time, weight, and deadline, and a feasible schedule needs to be consistent with chain-like precedence constraints. The goal is to compute a feasible schedule that minimizes the sum of penalties of late jobs. Lenstra and Rinnoy Kan [Annals of Disc. Math., 1977] in their seminal work introduced this problem and showed that it is strongly NP-hard, even when all processing times and weights are 1. We study the approximability of the problem and our main result is an O(log k)- approximation algorithm for instances with k distinct job deadlines.

AB - We consider the classic problem of scheduling a set of n jobs non-preemptively on a single machine. Each job j has non-negative processing time, weight, and deadline, and a feasible schedule needs to be consistent with chain-like precedence constraints. The goal is to compute a feasible schedule that minimizes the sum of penalties of late jobs. Lenstra and Rinnoy Kan [Annals of Disc. Math., 1977] in their seminal work introduced this problem and showed that it is strongly NP-hard, even when all processing times and weights are 1. We study the approximability of the problem and our main result is an O(log k)- approximation algorithm for instances with k distinct job deadlines.

UR - http://www.scopus.com/inward/record.url?scp=84945537681&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-48350-3_41

DO - 10.1007/978-3-662-48350-3_41

M3 - Conference contribution

AN - SCOPUS:84945537681

SN - 9783662483497

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 483

EP - 495

BT - Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings

A2 - Bansal, Nikhil

A2 - Finocchi, Irene

PB - Springer

T2 - 23rd European Symposium on Algorithms, ESA 2015

Y2 - 14 September 2015 through 16 September 2015

ER -

Efsandiari H, Hajiaghyi MT, Könemann J, Mahini H, Malec D, Sanit À L. Approximate Deadline-Scheduling with precedence constraints. In Bansal N, Finocchi I, redacteurs, Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings. Springer. 2015. blz. 483-495. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-48350-3_41

Approximate Deadline-Scheduling with precedence constraints

Samenvatting

Publicatie series

Congres

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit