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

Tobias Mömke

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

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

Abstract

top
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 ( 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 ( 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 ( D ) .

How to cite

top

Mö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 &gt; 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 &gt; 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. [1] P. Brucker, An efficient algorithm for the job shop problem with two jobs. Computing 40 (1988) 353–359. Zbl0654.90036MR969653
  2. [2] U. Feige and C. Scheideler, Improved bounds for acyclic job shop scheduling. Combinatorica 22 (2002) 361–399. MR1932059
  3. [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. [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. [5] F.A. Leighton, B.M. Maggs and S.B. Rao, Packet routing and job shop scheduling in O ( congestion + dilition ) steps. Combinatorica 14 (1994) 167–186. Zbl0811.68062MR1289071
  6. [6] F.A. Leighton, B.M. Maggs and A.W. Richa, Fast algorithms for finding O ( congestion + dilation ) packet routing schedules. Combinatorica 19 (1999) 375–401. Zbl0932.68005MR1723254
  7. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.