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

RAIRO - Theoretical Informatics and Applications (2008)

- Volume: 43, Issue: 2, page 189-207
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topMömke, Tobias. "On the power of randomization for job shop scheduling with k-units length tasks." RAIRO - Theoretical Informatics and Applications 43.2 (2008): 189-207. <http://eudml.org/doc/92911>.

@article{Mömke2008,

abstract = {
In the job shop scheduling problem k-units-Jm, 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-Jm 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-Jm, whereas the competitive ratio of the randomized
on-line algorithm of (ii) still tends to 1 for $d = o(\sqrt\{D\})$.
},

author = {Mömke, Tobias},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {On-line algorithms; randomization; competitive ratio; scheduling; on-line algorithms},

language = {eng},

month = {6},

number = {2},

pages = {189-207},

publisher = {EDP Sciences},

title = {On the power of randomization for job shop scheduling with k-units length tasks},

url = {http://eudml.org/doc/92911},

volume = {43},

year = {2008},

}

TY - JOUR

AU - Mömke, Tobias

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

JO - RAIRO - Theoretical Informatics and Applications

DA - 2008/6//

PB - EDP Sciences

VL - 43

IS - 2

SP - 189

EP - 207

AB -
In the job shop scheduling problem k-units-Jm, 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-Jm 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-Jm, whereas the competitive ratio of the randomized
on-line algorithm of (ii) still tends to 1 for $d = o(\sqrt{D})$.

LA - eng

KW - On-line algorithms; randomization; competitive ratio; scheduling; on-line algorithms

UR - http://eudml.org/doc/92911

ER -

## References

top- P. Brucker, An efficient algorithm for the job shop problem with two jobs. Computing40 (1988) 353–359. Zbl0654.90036
- U. Feige and C. Scheideler, Improved bounds for acyclic job shop scheduling. Combinatorica22 (2002) 361–399. Zbl1027.68512
- J. Hromkovič, K. Steinhöfel and P. Widmayer, Job shop scheduling with unit length tasks: bounds and algorithms. ICTCS '01: Proceedings of the 7th Italian Conference on Theoretical Computer Science. Lect. Notes Comput. Sci.2202 (2001) 90–106. Zbl1042.90020
- J. Hromkovič, T. Mömke, K. Steinhöfel and P. Widmayer, Job shop scheduling with unit length tasks: bounds and algorithms. Algorithmic Operations Research2 (2007) 1–14. Zbl1186.90051
- F.A. Leighton, B.M. Maggs and S.B. Rao, Packet routing and job shop scheduling in O(congestion + dilition) steps. Combinatorica14 (1994) 167–186. Zbl0811.68062
- F.A. Leighton, B.M. Maggs and A.W. Richa, Fast algorithms for finding O(congestion + dilation) packet routing schedules. Combinatorica19 (1999) 375–401. Zbl0932.68005
- J.K. Lenstra and A.H.G. Rinnooy Kan, Computational complexity of discrete optimization problems. Annals of Discrete Mathematics4 (1979) 121–140. Zbl0411.68042
- D.P. Willamson, L.A. Hall, C.A.J. Hurkens, J.K. Lenstra, S.V. Sevast'janov and D.B. Shmoys, Short shop schedules. Operations Research45 (1997) 288–294.

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.