Job Shop Scheduling with Unit Length Tasks: Bounds and Algorithms

Juraj Hromkovic, Kathleen Steinhofel, Peter Widmayer

Research output: Chapter in Book/Report/Conference proceedingConference paper

4 Citations (Scopus)


We consider the job shop scheduling problem unit-J m, where each job is processed once on each of m given 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 contribution of this paper are the following results: (i) For any input instance of unit-J m with d jobs, the makespan of an optimum schedule is at most m+o(m), for d = o(m 1/2). For d = o(m 1/2), this improves on the upper bound O(m+d) given in [LMR99] with a constant equal to two as shown in [S98]. For d = 2 the upper bound is improved to m+|√m| . (ii) There exist input instances of unit-J m with d = 2 such that the makespan of an optimum schedule is at least m+|√m| , i.e., the result (i) cannot be improved for d = 2. (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) A deterministic approximation algorizhm for unit-J m is described that works in quadratic time for constant d and has an approximation ratio of 1+2d/⌊√m⌋ for d ≤ 2 log2 m.

Original languageEnglish
Title of host publicationTheoretical Computer Science
Subtitle of host publication7th Italian Conference, ICTCS 2001 Torino, Italy, October 4–6, 2001 Proceedings
EditorsAntonio Restivo, Luca Roversi, S Ronchi Della Rocca
Place of PublicationBerlin ; London ; New York
PublisherSpringer Finance
Number of pages17
ISBN (Print)9783540426721
Publication statusPublished - 2001

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743


Dive into the research topics of 'Job Shop Scheduling with Unit Length Tasks: Bounds and Algorithms'. Together they form a unique fingerprint.

Cite this