On the power of randomization for job shop scheduling with k-units length tasks
Department of Informatics,
ETH Zurich, ETH Zentrum, 8092 Zürich, Switzerland; email@example.com
Accepted: 24 April 2008
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 jobs and every fixed k, the makespan of an optimal schedule is at most D+ o(D), which extends the result of  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 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 .
Mathematics Subject Classification: 68W20 / 68W25
Key words: On-line algorithms / randomization / competitive ratio / scheduling
© EDP Sciences, 2008