Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On the power of randomization for job shop scheduling with k-units length tasks
Department of Informatics, ETH Zurich.
2009 (English)In: Informatique théorique et applications (Imprimé), ISSN 0988-3754, E-ISSN 1290-385X, Vol. 43, no 2, 189-207 p.Article in journal (Refereed) Published
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
2009. Vol. 43, no 2, 189-207 p.
Keyword [en]
On-line algorithms, randomization, competitive ratio, scheduling
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-60837DOI: 10.1051/ita:2008024ISI: 000264879300002OAI: oai:DiVA.org:kth-60837DiVA: diva2:478006
Note
QC 20120119Available from: 2012-01-15 Created: 2012-01-15 Last updated: 2017-12-08Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Mömke, Tobias
In the same journal
Informatique théorique et applications (Imprimé)
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 31 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf