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
(ii) There exist input instances of
\J with $d = 2$ such that the
(iii) We present a randomized online
approximation
(iv) A deterministic approximation algorithm
for \J is described
