TY - CHAP
T1 - Job Shop Scheduling with Unit Length Tasks
T2 - Bounds and Algorithms
AU - Hromkovic, Juraj
AU - Steinhofel, Kathleen
AU - Widmayer, Peter
PY - 2001
Y1 - 2001
N2 - 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.
AB - 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.
U2 - 10.1007/3-540-45446-2_6
DO - 10.1007/3-540-45446-2_6
M3 - Conference paper
SN - 9783540426721
VL - N/A
T3 - Lecture Notes in Computer Science
SP - 90
EP - 106
BT - Theoretical Computer Science
A2 - Restivo, Antonio
A2 - Roversi, Luca
A2 - Ronchi Della Rocca, S
PB - Springer Finance
CY - Berlin ; London ; New York
ER -