\input zb-basic
\input zb-ioport
\iteman{io-port 01775452}
\itemau{Feige, Uriel; Scheideler, Christian}
\itemti{Improved bounds for acyclic job shop scheduling (extended abstract).}
\itemso{STOC '98. Proceedings of the 30th annual ACM symposium on theory of computing, Dallas, TX, USA, May 23-26, 1998. New York, NY: ACM, Association for Computing Machinery. 624-633 (1998).}
\itemab
Summary: In acyclic job shop scheduling problems there are $n$ jobs and $m$ machines. Each job is composed of a sequence of operations to be performed on different machines. A legal schedule is one in which within each job, operations are carried out in order, and each machine performs at most one operation in any unit of time. If $D$ denotes the length of the longest job, and $C$ denotes the number of time units requested by all jobs on the most loaded machine, then clearly $lb=\max[C,D]$ is a lower bound on the length of the shortest legal schedule. A celebrated result of Leighton, Maggs and Rao shows that if all operations are of unit length, then there always is a legal schedule of length $O(lb)$, independent of $n$ and $m$. For the case that operations may have different lengths, Shmoys, Stein and Wein showed that there always is a legal schedule of length $\widetilde O(lb(\log lb)^2)$, where $(\widetilde O)$ notation is used to suppress $\log\log(lb)$ terms. We improve the upper bound to $\widetilde O(lb\log lb)$. We also show that our new upper bound is essentially best possible, by proving the existence of instances of acyclic job shop scheduling for which the shortest legal schedule is of length $\widetilde \Omega (lb\log lb)$. This resolves (negatively) a known open problem of whether the linear upper bound of Leighton, Maggs and Rao applies to arbitrary job shop scheduling instances (without the restriction to acyclicity and unit length operations).
\itemrv{~}
\itemcc{C.4 D.4.1 B.8.2}
\itemut{acyclic job shop scheduling problems}
\itemli{}
\end