Change search
ReferencesLink to record
Permanent link

Direct link
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, 1-14 p.Article 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, 1-14 p.
Keyword [en]
job shop scheduling, online algorithms
National Category
Computer Science
URN: urn:nbn:se:kth:diva-41939OAI: diva2:445405
QC 20101005Available from: 2011-10-05 Created: 2011-10-03 Last updated: 2011-10-05Bibliographically approved

Open Access in DiVA

fulltext(268 kB)51 downloads
File information
File name FULLTEXT01.pdfFile size 268 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Search in DiVA

By author/editor
Mömke, Tobias
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 51 downloads
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: 60 hits
ReferencesLink to record
Permanent link

Direct link