Change search
ReferencesLink to record
Permanent link

Direct link
On the power of randomization for job shop scheduling with k -units length tasks
Department of Informatics, ETH Zurich.
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)
Abstract [en]

 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 [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(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.
Keyword [en]
Competitive ratio, On-line algorithms, Randomization, Scheduling
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-60840ISBN: 80-214-3287-XOAI: diva2:478018
2nd Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2006), Mikulov 27.-29.10.2006, Czech Republic
QC 20120119Available from: 2012-01-15 Created: 2012-01-15 Last updated: 2012-01-19Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Mömke, Tobias
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 18 hits
ReferencesLink to record
Permanent link

Direct link