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$.