Denis Trystram
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Denis Trystram has a total of 32 co-authors. Here are the top co-authors by number of shared publications:
- Benjamin Moseley
Carnegie Mellon University, Pittsburgh, PA, USA
5 shared publications - Erwin Pesch
Faculty III, University of Siegen, Siegen, Germany
5 shared publications - Jacek Blazewicz
Poznań University of Technology, Poland
5 shared publications - Guochuan Zhang
Zhejiang University
4 shared publications - Abhinav Srivastav
LAMSADE Université Paris Dauphine
2 shared publications - Giorgio Lucarelli
Université de Lorraine
2 shared publications
Latest Publications
- Open Access
- 19 November 2023
- Published by Springer Nature in Journal of Scheduling
- Vol. 26 (6) , 519-521
Mathematical challenges in scheduling theory
- 19 November 2023
- Published by Springer Nature in Journal of Scheduling
- Vol. 26 (6) , 519-521
Open AccessMathematical challenges in scheduling theory
- 24 August 2021
- Published by Springer Nature in Journal of Scheduling
- Vol. 24 (5) , 455-457
New Perspectives in Scheduling Theory
- 24 August 2021
- Published by Springer Nature in Journal of Scheduling
- Vol. 24 (5) , 455-457
New Perspectives in Scheduling Theory
- 4 July 2018
- Published by Springer Nature in Journal of Scheduling
- Vol. 21 (6) , 581-582
New challenges in scheduling theory
- 4 July 2018
- Published by Springer Nature in Journal of Scheduling
- Vol. 21 (6) , 581-582
New challenges in scheduling theory
- Open Access
Online Non-Preemptive Scheduling to Minimize Weighted Flow-time on Unrelated Machines
In this paper, we consider the online problem of scheduling independent jobs \emph{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. %Using the speed augmentation model, Anand et al. showed that the greedy algorithm is $O\left(\frac{1}{\epsilon}\right)$-competitive in the preemptive setting. In the non-preemptive setting, Lucarelli et al. showed that there exists a strong lower bound for minimizing weighted flow-time even on a single machine. However, the problem in the non-preemptive setting admits a strong lower bound. Recently, Lucarelli et al. presented an algorithm that achieves a $O\left(\frac{1}{\epsilon^2}\right)$-competitive ratio when the algorithm is allowed to reject $\epsilon$-fraction of total weight of jobs and $\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\left(\frac{1}{\epsilon^3}\right)$-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.
Open AccessOnline Non-Preemptive Scheduling to Minimize Weighted Flow-time on Unrelated Machines
In this paper, we consider the online problem of scheduling independent jobs \emph{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. %Using the speed augmentation model, Anand et al. showed that the greedy algorithm is $O\left(\frac{1}{\epsilon}\right)$-competitive in the preemptive setting. In the non-preemptive setting, Lucarelli et al. showed that there exists a strong lower bound for minimizing weighted flow-time even on a single machine. However, the problem in the non-preemptive setting admits a strong lower bound. Recently, Lucarelli et al. presented an algorithm that achieves a $O\left(\frac{1}{\epsilon^2}\right)$-competitive ratio when the algorithm is allowed to reject $\epsilon$-fraction of total weight of jobs and $\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\left(\frac{1}{\epsilon^3}\right)$-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.
- Open Access
Online Non-preemptive Scheduling on Unrelated Machines with Rejections
When a computer system schedules jobs there is typically a significant cost associated with preempting a job during execution. This cost can be from the expensive task of saving the memory's state and loading data into and out of memory. It is desirable to schedule jobs non-preemptively to avoid the costs of preemption. There is a need for non-preemptive system schedulers on desktops, servers and data centers. Despite this need, there is a gap between theory and practice. Indeed, few non-preemptive \emph{online} schedulers are known to have strong foundational guarantees. This gap is likely due to strong lower bounds on any online algorithm for popular objectives. Indeed, typical worst case analysis approaches, and even resource augmented approaches such as speed augmentation, result in all algorithms having poor performance guarantees. This paper considers on-line non-preemptive scheduling problems in the worst-case rejection model where the algorithm is allowed to reject a small fraction of jobs. By rejecting only a few jobs, this paper shows that the strong lower bounds can be circumvented. This approach can be used to discover algorithmic scheduling policies with desirable worst-case guarantees. Specifically, the paper presents algorithms for the following two objectives: minimizing the total flow-time and minimizing the total weighted flow-time plus energy under the speed-scaling mechanism. The algorithms have a small constant competitive ratio while rejecting only a constant fraction of jobs. Beyond specific results, the paper asserts that alternative models beyond speed augmentation should be explored to aid in the discovery of good schedulers in the face of the requirement of being online and non-preemptive.
Open AccessOnline Non-preemptive Scheduling on Unrelated Machines with Rejections
When a computer system schedules jobs there is typically a significant cost associated with preempting a job during execution. This cost can be from the expensive task of saving the memory's state and loading data into and out of memory. It is desirable to schedule jobs non-preemptively to avoid the costs of preemption. There is a need for non-preemptive system schedulers on desktops, servers and data centers. Despite this need, there is a gap between theory and practice. Indeed, few non-preemptive \emph{online} schedulers are known to have strong foundational guarantees. This gap is likely due to strong lower bounds on any online algorithm for popular objectives. Indeed, typical worst case analysis approaches, and even resource augmented approaches such as speed augmentation, result in all algorithms having poor performance guarantees. This paper considers on-line non-preemptive scheduling problems in the worst-case rejection model where the algorithm is allowed to reject a small fraction of jobs. By rejecting only a few jobs, this paper shows that the strong lower bounds can be circumvented. This approach can be used to discover algorithmic scheduling policies with desirable worst-case guarantees. Specifically, the paper presents algorithms for the following two objectives: minimizing the total flow-time and minimizing the total weighted flow-time plus energy under the speed-scaling mechanism. The algorithms have a small constant competitive ratio while rejecting only a constant fraction of jobs. Beyond specific results, the paper asserts that alternative models beyond speed augmentation should be explored to aid in the discovery of good schedulers in the face of the requirement of being online and non-preemptive.
- 30 November 2016
- Published by Springer Nature in Journal of Scheduling
- Vol. 19 (6) , 617-618
New challenges in scheduling theory
- 30 November 2016
- Published by Springer Nature in Journal of Scheduling
- Vol. 19 (6) , 617-618
New challenges in scheduling theory
- 19 January 2015
- Published by EDP Sciences in RAIRO - Operations Research
- Vol. 49 (2) , 369-381
Scheduling 2-dimensional grids with large communication delays
- 19 January 2015
- Published by EDP Sciences in RAIRO - Operations Research
- Vol. 49 (2) , 369-381
Scheduling 2-dimensional grids with large communication delays
- 19 January 2015
- Published by EDP Sciences in RAIRO - Operations Research
- Vol. 49 (2) , 335-337
New challenges in scheduling theory
RO : RAIRO - Operations Research, an international journal on operations research, exploring high level pure and applied aspects
- 19 January 2015
- Published by EDP Sciences in RAIRO - Operations Research
- Vol. 49 (2) , 335-337
New challenges in scheduling theory
RO : RAIRO - Operations Research, an international journal on operations research, exploring high level pure and applied aspects
- Open Access
Total stretch minimization on single and identical parallel machines
We consider the classical problem of scheduling $n$ jobs with release dates on both single and identical parallel machines. We measure the quality of service provided to each job by its stretch, which is defined as the ratio of its response time to processing time. Our objective is to schedule these jobs non-preemptively so as to minimize sum stretch. So far, there have been very few results for sum stretch minimization especially for the non-preemptive case. For the preemptive version, the Shortest remaining processing time (SRPT) algorithm is known to give $2$-competitive for sum stretch on single machine while its is $13$-competitive on identical parallel machines. Leonardi and Kellerer provided the strong lower bound for the more general problem of \textit{sum (weighted) flow time} in single machine and identical parallel machines, respectively . Therefore, we study this problem with some additional assumptions and present two new competitive ratio for existing algorithms. We show that the Shortest processing time (SPT) algorithm is $\Delta - \frac{1}{\Delta}+1$-competitive for non-preemptive sum stretch minimization on single machine and it is $\Delta - \frac{1}{\Delta}+ \frac{3}{2} -\frac{1}{2m}$ on $m$ identical parallel machines, where $\Delta$ is the upper bound on the ratio between the maximum and the minimum processing time of the jobs.Open AccessTotal stretch minimization on single and identical parallel machines
We consider the classical problem of scheduling $n$ jobs with release dates on both single and identical parallel machines. We measure the quality of service provided to each job by its stretch, which is defined as the ratio of its response time to processing time. Our objective is to schedule these jobs non-preemptively so as to minimize sum stretch. So far, there have been very few results for sum stretch minimization especially for the non-preemptive case. For the preemptive version, the Shortest remaining processing time (SRPT) algorithm is known to give $2$-competitive for sum stretch on single machine while its is $13$-competitive on identical parallel machines. Leonardi and Kellerer provided the strong lower bound for the more general problem of \textit{sum (weighted) flow time} in single machine and identical parallel machines, respectively . Therefore, we study this problem with some additional assumptions and present two new competitive ratio for existing algorithms. We show that the Shortest processing time (SPT) algorithm is $\Delta - \frac{1}{\Delta}+1$-competitive for non-preemptive sum stretch minimization on single machine and it is $\Delta - \frac{1}{\Delta}+ \frac{3}{2} -\frac{1}{2m}$ on $m$ identical parallel machines, where $\Delta$ is the upper bound on the ratio between the maximum and the minimum processing time of the jobs. - 1 January 2010
- Published by European Alliance for Innovation n.o.
Random graph generation for scheduling simulations
- 1 January 2010
- Published by European Alliance for Innovation n.o.
Random graph generation for scheduling simulations