Title Job shop scheduling with unit length tasks: Bounds and algorithms
Authors Juraj Hromkovic, RWTH Aachen
Kathleen Steinhöfel, GMD Berlin
Peter Widmayer, ETH Zürich
Main Fields 1. analysis of algorithms
7. design of algorithms
Other Main Fields
Abstract + Keywords
We consider the job shop scheduling problem \J,
where each job is processed once on each of $m$ given machines. The
execution of any task on its corresponding machine takes
exactly one time unit. The objective is to minimize the overall
completion time, called makespan. The following four results are
the main contributions of this paper:

(i) For any input instance of \J with $d$ jobs, the makespan of an
optimum schedule is at most $ m+ o(m)$, for $d = o(m^{1/2})$.
For $d = o(m^{1/2})$, this improves on the upper bound $O(m + d)$
given in \cite{LMR99} with a constant equal to two as shown in
\cite{S98}. For $d=2$ the upper bound is improved to $m +
\lceil \; \sqrt{m} \; \rceil$.

(ii) There exist input instances of \J with $d = 2$ such that the
makespan of an optimum schedule is at least $m+\lceil \; \sqrt{m} \; \rceil$, i.e., the
result (i) cannot be improved for $d=2$.

(iii) We present a randomized on-line approximation
algorithm for \J with the best known approximation ratio for
$d = o(m^{1/2})$.

(iv) A deterministic approximation algorithm for \J is described
that works in quadratic time for constant $d$ and has an
approximation ratio of $1 + 2^d/\lfloor \sqrt{m} \, \rfloor$.