Change search

Cite
Citation style
• apa
• 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
Job Shop Scheduling with Unit Length Tasks: Bounds and Algorithms
ETH Zurich.
King's College London.
ETH Zurich.
2007 (English)In: Algorithmic Operations Research, ISSN 1718-3235, Vol. 2, p. 1-14Article in journal (Refereed) Published
##### Abstract [en]

We consider the job shop scheduling problem unit-J_m, where each job is processed once on each of m given machines. Every job consists of a permutation of tasks for all machines. The execution of any task on its corresponding machine takes exactly one time unit. The objective is to minimize the overall completion time, called makespan. The contributionof this paper are the following results: (i) For any input instance ofunit-J_m with d jobs, the makespan of an optimum schedule is at most m + o(m), for d = o(m^{1/2}). This improves on the upper bound O(m + d) given in [LMR99] where O hides a constant equal to two as shown in [S98].  For d=2 the upper bound is improved to m + \lceil \sqrt{m} \rceil. (ii) There exist input instances of unit-J_m with d = 2 such that themakespan of an optimum schedule is at least m+ \lceil  \sqrt{m} \rceil, i.e., our upper bound for d=2, see result (i), cannot be improved. (iii) We present a randomized on-line approximation algorithm for unit-J_m with the best known approximation ratio for d = o(m^{1/2}). (iv) There is no deterministic on-line algorithm with a competitive ratiobetter than 4/3 for unit-J_m with two jobs, and for three or more jobs,there is no deterministic on-line algorithm which is better than 1.5competitive. Compared with the expected competitive ratio of (iii) whichtends to 1, this shows that for unit-J_m randomization is very powerfulcompared with determinism. For two and three jobs, deterministic on-linealgorithms with competitive ratios tending to 4/3 and 1.5 respectivelyare presented. (v) A deterministic approximation algorithm for unit-J_mis described that works in quadratic time for constant $d$ and has anapproximation ratio of 1 + 2^d/\lfloor \sqrt{m} \rfloor for d \leq 2 \log_2 m.

##### Place, publisher, year, edition, pages
Preeminent Academic Facets Inc. , 2007. Vol. 2, p. 1-14
##### Keyword [en]
job shop scheduling, online algorithms
##### National Category
Computer Sciences
##### Identifiers
OAI: oai:DiVA.org:kth-41939DiVA, id: diva2:445405
##### Note
QC 20101005Available from: 2011-10-05 Created: 2011-10-03 Last updated: 2018-01-12Bibliographically approved

#### Open Access in DiVA

##### File information
File name FULLTEXT01.pdfFile size 268 kBChecksum SHA-512
52af4c218e69f535284fe39be7b5b7eb03a125ac630364728ff8c932770b7f3630c65dd1ba12eb13c10d0f6b4b6850e8c14c4537d2bf97f1339157333e81d961
Type fulltextMimetype application/pdf

http://journals.hil.unb.ca/index.php/AOR/article/view/2729

#### Search in DiVA

Mömke, Tobias
##### On the subject
Computer Sciences

#### Search outside of DiVA

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
urn-nbn

#### Altmetric score

urn-nbn
Total: 93 hits

Cite
Citation style
• apa
• 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
v. 2.33.0
|