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

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 -