On the power of randomization for job shop scheduling with k -units length tasks
2006 (English)In: Proceedings of MEMICS 2006, 2nd Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, 2006, 121-128 p.Conference paper (Refereed)
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(root D) 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-J(m) is presented. This is the on-line algorithm with the best known competitive ratio against an oblivious adversary for d = o(root 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(root D).
Place, publisher, year, edition, pages
2006. 121-128 p.
Competitive ratio, On-line algorithms, Randomization, Scheduling
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-60840ISBN: 80-214-3287-XOAI: oai:DiVA.org:kth-60840DiVA: diva2:478018
2nd Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2006), Mikulov 27.-29.10.2006, Czech Republic
QC 201201192012-01-152012-01-152012-01-19Bibliographically approved