---
_id: '79'
abstract:
- lang: eng
text: Consider a problem in which $n$ jobs that are classified into $k$ types arrive
over time at their release times and are to be scheduled on a single machine so
as to minimize the maximum flow time.The machine requires a setup taking $s$ time
units whenever it switches from processing jobs of one type to jobs of a different
type.We consider the problem as an online problem where each job is only known
to the scheduler as soon as it arrives and where the processing time of a job
only becomes known upon its completion (non-clairvoyance).We are interested in
the potential of simple ``greedy-like'' algorithms.We analyze a modification of
the FIFO strategy and show its competitiveness to be $\Theta(\sqrt{n})$, which
is optimal for the considered class of algorithms.For $k=2$ types it achieves
a constant competitiveness.Our main insight is obtained by an analysis of the
smoothed competitiveness.If processing times $p_j$ are independently perturbed
to $\hat p_j = (1+X_j)p_j$, we obtain a competitiveness of $O(\sigma^{-2} \log^2
n)$ when $X_j$ is drawn from a uniform or a (truncated) normal distribution with
standard deviation $\sigma$.The result proves that bad instances are fragile and
``practically'' one might expect a much better performance than given by the $\Omega(\sqrt{n})$-bound.
accept: '1'
author:
- first_name: Alexander
full_name: Mäcker, Alexander
id: '13536'
last_name: Mäcker
- first_name: Manuel
full_name: Malatyali, Manuel
last_name: Malatyali
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Sören
full_name: Riechers, Sören
last_name: Riechers
citation:
ama: 'Mäcker A, Malatyali M, Meyer auf der Heide F, Riechers S. Non-Clairvoyant
Scheduling to Minimize Max Flow Time on a Machine with Setup Times. In: *Proceedings
of the 15th Workshop on Approximation and Online Algorithms (WAOA)*. Vol 10787.
Lecture Notes in Computer Science. Springer; 2017:207-222. doi:10.1007/978-3-319-89441-6'
apa: Mäcker, A., Malatyali, M., Meyer auf der Heide, F., & Riechers, S. (2017).
Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times.
In *Proceedings of the 15th Workshop on Approximation and Online Algorithms
(WAOA)* (Vol. 10787, pp. 207–222). Springer. https://doi.org/10.1007/978-3-319-89441-6
bibtex: '@inproceedings{Mäcker_Malatyali_Meyer auf der Heide_Riechers_2017, series={Lecture
Notes in Computer Science}, title={Non-Clairvoyant Scheduling to Minimize Max
Flow Time on a Machine with Setup Times}, volume={10787}, DOI={10.1007/978-3-319-89441-6},
booktitle={Proceedings of the 15th Workshop on Approximation and Online Algorithms
(WAOA)}, publisher={Springer}, author={Mäcker, Alexander and Malatyali, Manuel
and Meyer auf der Heide, Friedhelm and Riechers, Sören}, year={2017}, pages={207–222},
collection={Lecture Notes in Computer Science} }'
chicago: Mäcker, Alexander, Manuel Malatyali, Friedhelm Meyer auf der Heide, and
Sören Riechers. “Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine
with Setup Times.” In *Proceedings of the 15th Workshop on Approximation and
Online Algorithms (WAOA)*, 10787:207–22. Lecture Notes in Computer Science.
Springer, 2017. https://doi.org/10.1007/978-3-319-89441-6.
ieee: A. Mäcker, M. Malatyali, F. Meyer auf der Heide, and S. Riechers, “Non-Clairvoyant
Scheduling to Minimize Max Flow Time on a Machine with Setup Times,” in *Proceedings
of the 15th Workshop on Approximation and Online Algorithms (WAOA)*, 2017,
vol. 10787, pp. 207–222.
mla: Mäcker, Alexander, et al. “Non-Clairvoyant Scheduling to Minimize Max Flow
Time on a Machine with Setup Times.” *Proceedings of the 15th Workshop on Approximation
and Online Algorithms (WAOA)*, vol. 10787, Springer, 2017, pp. 207–22, doi:10.1007/978-3-319-89441-6.
short: 'A. Mäcker, M. Malatyali, F. Meyer auf der Heide, S. Riechers, in: Proceedings
of the 15th Workshop on Approximation and Online Algorithms (WAOA), Springer,
2017, pp. 207–222.'
date_created: 2017-10-17T12:41:06Z
date_updated: 2019-01-03T13:18:36Z
ddc:
- '000'
department:
- _id: '63'
doi: 10.1007/978-3-319-89441-6
file:
- access_level: closed
content_type: application/pdf
creator: ups
date_created: 2018-11-02T14:59:22Z
date_updated: 2018-11-02T14:59:22Z
file_id: '5289'
file_name: Non-clairvoyantSchedulingToMin.pdf
file_size: 380629
open_access: 1
relation: main_file
success: 1
file_date_updated: 2018-11-02T14:59:22Z
intvolume: ' 10787'
language:
- iso: eng
page: 207-222
project:
- _id: '1'
name: SFB 901
- _id: '16'
name: SFB 901 - Subprojekt C4
- _id: '4'
name: SFB 901 - Project Area C
publication: Proceedings of the 15th Workshop on Approximation and Online Algorithms
(WAOA)
publisher: Springer
series_title: Lecture Notes in Computer Science
status: public
title: Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup
Times
type: conference
user_id: '477'
volume: 10787
year: '2017'
...