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

Tobias Mömke

RAIRO - Theoretical Informatics and Applications (2008)

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

Abstract

top
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 ( 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 ( 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 ( 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 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
  1. P. Brucker, An efficient algorithm for the job shop problem with two jobs. Computing40 (1988) 353–359.  Zbl0654.90036
  2. U. Feige and C. Scheideler, Improved bounds for acyclic job shop scheduling. Combinatorica22 (2002) 361–399.  Zbl1027.68512
  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.90020
  4. 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
  5. 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
  6. 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
  7. J.K. Lenstra and A.H.G. Rinnooy Kan, Computational complexity of discrete optimization problems. Annals of Discrete Mathematics4 (1979) 121–140.  Zbl0411.68042
  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 Research45 (1997) 288–294.  

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.