Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times
Mäcker, Alexander
Malatyali, Manuel
Meyer auf der Heide, Friedhelm
Riechers, Sören
ddc:000
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.
Springer
2017
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
https://ris.uni-paderborn.de/record/79
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: <i>Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA)</i>. Vol 10787. Lecture Notes in Computer Science. Springer; 2017:207-222. doi:<a href="https://doi.org/10.1007/978-3-319-89441-6">10.1007/978-3-319-89441-6</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-319-89441-6
info:eu-repo/semantics/closedAccess