On the power of randomization for job shop scheduling with k-units length tasks

Issue		RAIRO-Theor. Inf. Appl. Volume 43, Number 2, April-June 2009


Page(s)		189 - 207
DOI		10.1051/ita:2008024
Published online		05 June 2008

RAIRO-Theor. Inf. Appl. 43, 189-207 (2009)
DOI: 10.1051/ita:2008024

On the power of randomization for job shop scheduling with k-units length tasks

Tobias Mömke

Department of Informatics, ETH Zurich, ETH Zentrum, 8092 Zürich, Switzerland; tobias.moemke@inf.ethz.ch

Received August 28, 2007. Accepted April 24, 2008. Published online 5 June 2008

Abstract
In the job shop scheduling problem k-units-J_m, there are m machines and each machine has an integer processing time of at most k time units. Each job consists of a permutation of m tasks corresponding to all machines and thus all jobs have an identical dilation D. The contribution of this paper are the following results; (i) for $d=o(\sqrt{D})$ jobs and every fixed k, the makespan of an optimal schedule is at most D+ o(D), which extends the result of [3] for k=1; (ii) a randomized on-line approximation algorithm for k-units-J_m is presented. This is the on-line algorithm with the best known competitive ratio against an oblivious adversary for $d=o(\sqrt{D})$ and k > 1; (iii) different processing times yield harder instances than identical processing times. There is no 5/3 competitive deterministic on-line algorithm for k-units-J_m, whereas the competitive ratio of the randomized on-line algorithm of (ii) still tends to 1 for $d=o(\sqrt{D})$ .

Mathematics Subject Classification. 68W20, 68W25

Key words: On-line algorithms -- randomization -- competitive ratio -- scheduling

© EDP Sciences 2008

What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.

If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.