---
res:
bibo_abstract:
- 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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Alexander
foaf_name: Mäcker, Alexander
foaf_surname: Mäcker
foaf_workInfoHomepage: http://www.librecat.org/personId=13536
- foaf_Person:
foaf_givenName: Manuel
foaf_name: Malatyali, Manuel
foaf_surname: Malatyali
- foaf_Person:
foaf_givenName: Friedhelm
foaf_name: Meyer auf der Heide, Friedhelm
foaf_surname: Meyer auf der Heide
foaf_workInfoHomepage: http://www.librecat.org/personId=15523
- foaf_Person:
foaf_givenName: Sören
foaf_name: Riechers, Sören
foaf_surname: Riechers
bibo_doi: 10.1007/978-3-319-89441-6
bibo_volume: 10787
dct_date: 2017^xs_gYear
dct_language: eng
dct_publisher: Springer@
dct_title: Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with
Setup Times@
...