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

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2009)

- 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 - Informatique Théorique et Applications 43.2 (2009): 189-207. <http://eudml.org/doc/246058>.

@article{Mömke2009,

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\})$.},

author = {Mömke, Tobias},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

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

language = {eng},

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/246058},

volume = {43},

year = {2009},

}

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 - Informatique Théorique et Applications

PY - 2009

PB - EDP-Sciences

VL - 43

IS - 2

SP - 189

EP - 207

AB - 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})$.

LA - eng

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

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

ER -

## References

top- [1] P. Brucker, An efficient algorithm for the job shop problem with two jobs. Computing 40 (1988) 353–359. Zbl0654.90036MR969653
- [2] U. Feige and C. Scheideler, Improved bounds for acyclic job shop scheduling. Combinatorica 22 (2002) 361–399. MR1932059
- [3] 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.90020MR1915409
- [4] J. Hromkovič, T. Mömke, K. Steinhöfel and P. Widmayer, Job shop scheduling with unit length tasks: bounds and algorithms. Algorithmic Operations Research 2 (2007) 1–14. Zbl1186.90051MR2302153
- [5] F.A. Leighton, B.M. Maggs and S.B. Rao, Packet routing and job shop scheduling in $O(\text{congestion}+\text{dilition})$ steps. Combinatorica 14 (1994) 167–186. Zbl0811.68062MR1289071
- [6] F.A. Leighton, B.M. Maggs and A.W. Richa, Fast algorithms for finding $O(\text{congestion}+\text{dilation})$ packet routing schedules. Combinatorica 19 (1999) 375–401. Zbl0932.68005MR1723254
- [7] J.K. Lenstra and A.H.G. Rinnooy Kan, Computational complexity of discrete optimization problems. Annals of Discrete Mathematics 4 (1979) 121–140. Zbl0411.68042MR558557
- [8] 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 Research 45 (1997) 288–294. Zbl0890.90112MR1644998

## NotesEmbed ?

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