Search Results

Documents authored by Trystram, Denis

Document
DOI: 10.4230/LIPIcs.FSTTCS.2019.24
Online Non-Preemptive Scheduling to Minimize Maximum Weighted Flow-Time on Related Machines

Authors: Giorgio Lucarelli, Benjamin Moseley, Nguyen Kim Thang, Abhinav Srivastav, and Denis Trystram

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

Abstract
We consider the problem of scheduling jobs to minimize the maximum weighted flow-time on a set of related machines. When jobs can be preempted this problem is well-understood; for example, there exists a constant competitive algorithm using speed augmentation. When jobs must be scheduled non-preemptively, only hardness results are known. In this paper, we present the first online guarantees for the non-preemptive variant. We present the first constant competitive algorithm for minimizing the maximum weighted flow-time on related machines by relaxing the problem and assuming that the online algorithm can reject a small fraction of the total weight of jobs. This is essentially the best result possible given the strong lower bounds on the non-preemptive problem without rejection.
Cite as

Giorgio Lucarelli, Benjamin Moseley, Nguyen Kim Thang, Abhinav Srivastav, and Denis Trystram. Online Non-Preemptive Scheduling to Minimize Maximum Weighted Flow-Time on Related Machines. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 24:1-24:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{lucarelli_et_al:LIPIcs.FSTTCS.2019.24,
  author =	{Lucarelli, Giorgio and Moseley, Benjamin and Thang, Nguyen Kim and Srivastav, Abhinav and Trystram, Denis},
  title =	{{Online Non-Preemptive Scheduling to Minimize Maximum Weighted Flow-Time on Related Machines}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{24:1--24:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.24},
  URN =		{urn:nbn:de:0030-drops-115867},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.24},
  annote =	{Keywords: Online Algorithms, Scheduling, Resource Augmentation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.59
Online Non-Preemptive Scheduling to Minimize Weighted Flow-time on Unrelated Machines

Authors: Giorgio Lucarelli, Benjamin Moseley, Nguyen Kim Thang, Abhinav Srivastav, and Denis Trystram

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
In this paper, we consider the online problem of scheduling independent jobs non-preemptively so as to minimize the weighted flow-time on a set of unrelated machines. There has been a considerable amount of work on this problem in the preemptive setting where several competitive algorithms are known in the classical competitive model. However, the problem in the non-preemptive setting admits a strong lower bound. Recently, Lucarelli et al. presented an algorithm that achieves a O(1/epsilon^2)-competitive ratio when the algorithm is allowed to reject epsilon-fraction of total weight of jobs and has an epsilon-speed augmentation. They further showed that speed augmentation alone is insufficient to derive any competitive algorithm. An intriguing open question is whether there exists a scalable competitive algorithm that rejects a small fraction of total weights. In this paper, we affirmatively answer this question. Specifically, we show that there exists a O(1/epsilon^3)-competitive algorithm for minimizing weighted flow-time on a set of unrelated machine that rejects at most O(epsilon)-fraction of total weight of jobs. The design and analysis of the algorithm is based on the primal-dual technique. Our result asserts that alternative models beyond speed augmentation should be explored when designing online schedulers in the non-preemptive setting in an effort to find provably good algorithms.
Cite as

Giorgio Lucarelli, Benjamin Moseley, Nguyen Kim Thang, Abhinav Srivastav, and Denis Trystram. Online Non-Preemptive Scheduling to Minimize Weighted Flow-time on Unrelated Machines. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 59:1-59:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{lucarelli_et_al:LIPIcs.ESA.2018.59,
  author =	{Lucarelli, Giorgio and Moseley, Benjamin and Thang, Nguyen Kim and Srivastav, Abhinav and Trystram, Denis},
  title =	{{Online Non-Preemptive Scheduling to Minimize Weighted Flow-time on Unrelated Machines}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{59:1--59:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.59},
  URN =		{urn:nbn:de:0030-drops-95226},
  doi =		{10.4230/LIPIcs.ESA.2018.59},
  annote =	{Keywords: Online Algorithms, Scheduling, Resource Augmentation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.63
Online Non-Preemptive Scheduling in a Resource Augmentation Model Based on Duality

Authors: Giorgio Lucarelli, Nguyen Kim Thang, Abhinav Srivastav, and Denis Trystram

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
Resource augmentation is a well-established model for analyzing algorithms, particularly in the online setting. It has been successfully used for providing theoretical evidence for several heuristics in scheduling with good performance in practice. According to this model, the algorithm is applied to a more powerful environment than that of the adversary. Several types of resource augmentation for scheduling problems have been proposed up to now, including speed augmentation, machine augmentation and more recently rejection. In this paper, we present a framework that unifies the various types of resource augmentation. Moreover, it allows generalize the notion of resource augmentation for other types of resources. Our framework is based on mathematical programming and it consists of extending the domain of feasible solutions for the algorithm with respect to the domain of the adversary. This, in turn allows the natural concept of duality for mathematical programming to be used as a tool for the analysis of the algorithm's performance. As an illustration of the above ideas, we apply this framework and we propose a primal-dual algorithm for the online scheduling problem of minimizing the total weighted flow time of jobs on unrelated machines when the preemption of jobs is not allowed. This is a well representative problem for which no online algorithm with performance guarantee is known. Specifically, a strong lower bound of Omega(sqrt{n}) exists even for the offline unweighted version of the problem on a single machine. In this paper, we first show a strong negative result even when speed augmentation is used in the online setting. Then, using the generalized framework for resource augmentation and by combining speed augmentation and rejection, we present an (1+epsilon_s)-speed O(1/(epsilon_s epsilon_r))-competitive algorithm if we are allowed to reject jobs whose total weight is an epsilon_r-fraction of the weights of all jobs, for any epsilon_s > 0 and epsilon_r in (0,1). Furthermore, we extend the idea for analysis of the above problem and we propose an (1+\epsilon_s)-speed epsilon_r-rejection O({k^{(k+3)/k}}/{epsilon_{r}^{1/k}*epsilon_{s}^{(k+2)/k}})-competitive algorithm for the more general objective of minimizing the weighted l_k-norm of the flow times of jobs.
Cite as

Giorgio Lucarelli, Nguyen Kim Thang, Abhinav Srivastav, and Denis Trystram. Online Non-Preemptive Scheduling in a Resource Augmentation Model Based on Duality. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 63:1-63:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{lucarelli_et_al:LIPIcs.ESA.2016.63,
  author =	{Lucarelli, Giorgio and Kim Thang, Nguyen and Srivastav, Abhinav and Trystram, Denis},
  title =	{{Online Non-Preemptive Scheduling in a Resource Augmentation Model Based on Duality}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{63:1--63:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.63},
  URN =		{urn:nbn:de:0030-drops-64047},
  doi =		{10.4230/LIPIcs.ESA.2016.63},
  annote =	{Keywords: Online algorithms, Non-preemptive scheduling, Resource augmentation, Primal-dual}
}
Document
DOI: 10.4230/DagSemProc.04231.1
04231 Abstracts Collection – Scheduling in Computer and Manufacturing Systems

Authors: Jacek Blazewicz, Klaus Ecker, Erwin Pesch, and Denis Trystram

Published in: Dagstuhl Seminar Proceedings, Volume 4231, Scheduling in Computer and Manufacturing Systems (2004)

Abstract
During 31.05.-04.06.04, the Dagstuhl Seminar 04231 "Scheduling in Computer and Manufacturing Systems" was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Jacek Blazewicz, Klaus Ecker, Erwin Pesch, and Denis Trystram. 04231 Abstracts Collection – Scheduling in Computer and Manufacturing Systems. In Scheduling in Computer and Manufacturing Systems. Dagstuhl Seminar Proceedings, Volume 4231, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2004)

Copy BibTex To Clipboard

@InProceedings{blazewicz_et_al:DagSemProc.04231.1,
  author =	{Blazewicz, Jacek and Ecker, Klaus and Pesch, Erwin and Trystram, Denis},
  title =	{{04231 Abstracts Collection – Scheduling in Computer and Manufacturing Systems}},
  booktitle =	{Scheduling in Computer and Manufacturing Systems},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2004},
  volume =	{4231},
  editor =	{Jacek Blazewicz and Klaus Ecker and Erwin Pesch and Denis Trystram},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04231.1},
  URN =		{urn:nbn:de:0030-drops-81},
  doi =		{10.4230/DagSemProc.04231.1},
  annote =	{Keywords: Scheduling}
}
Document
DOI: 10.4230/DagSemRep.343
Scheduling in Computer and Manufacturing Systems (Dagstuhl Seminar 02231)

Authors: Jacek Blazewicz, Ed G. Coffman Jr., Klaus Ecker, and Denis Trystram

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Jacek Blazewicz, Ed G. Coffman Jr., Klaus Ecker, and Denis Trystram. Scheduling in Computer and Manufacturing Systems (Dagstuhl Seminar 02231). Dagstuhl Seminar Report 343, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)

Copy BibTex To Clipboard

@TechReport{blazewicz_et_al:DagSemRep.343,
  author =	{Blazewicz, Jacek and Coffman Jr., Ed G. and Ecker, Klaus and Trystram, Denis},
  title =	{{Scheduling in Computer and Manufacturing Systems (Dagstuhl Seminar 02231)}},
  pages =	{1--16},
  ISSN =	{1619-0203},
  year =	{2002},
  type = 	{Dagstuhl Seminar Report},
  number =	{343},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.343},
  URN =		{urn:nbn:de:0030-drops-152249},
  doi =		{10.4230/DagSemRep.343},
}
Document
DOI: 10.4230/DagSemRep.180
Scheduling in Computer and Manufacturing Systems (Dagstuhl Seminar 9723)

Authors: Jacek Blazewicz, Klaus H. Ecker, Wieslaw Kubiak, and Denis Trystram

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Jacek Blazewicz, Klaus H. Ecker, Wieslaw Kubiak, and Denis Trystram. Scheduling in Computer and Manufacturing Systems (Dagstuhl Seminar 9723). Dagstuhl Seminar Report 180, pp. 1-26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1997)

Copy BibTex To Clipboard

@TechReport{blazewicz_et_al:DagSemRep.180,
  author =	{Blazewicz, Jacek and Ecker, Klaus H. and Kubiak, Wieslaw and Trystram, Denis},
  title =	{{Scheduling in Computer and Manufacturing Systems (Dagstuhl Seminar 9723)}},
  pages =	{1--26},
  ISSN =	{1619-0203},
  year =	{1997},
  type = 	{Dagstuhl Seminar Report},
  number =	{180},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.180},
  URN =		{urn:nbn:de:0030-drops-150672},
  doi =		{10.4230/DagSemRep.180},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact