We propose asymptotically optimal algorithms for the job shop scheduling an
d packet routing problems. We propose a fluid relaxation for the job shop s
cheduling problem in which we replace discrete jobs with the flow of a cont
inuous fluid. We compute an optimal solution of the fluid relaxation in clo
sed form, obtain a lower bound C-max to the job shop scheduling problem, an
d construct a feasible schedule from the fluid relaxation with objective va
lue at most C-max + O(root C-max) where the constant in the O(.) notation i
s independent of the number of jobs, but it depends on the processing time
of the jobs, thus producing an asymptotically optimal schedule as the total
number of jobs tends to infinity. If the initially present jobs increase p
roportionally, then our algorithm produces a schedule with value at most C-
max + O(1). For the packet routing problem with fixed paths the previous al
gorithm applies directly. For the general packet routing problem we propose
a linear programming relaxation that provides a lower bound C-max and an a
symptotically optimal algorithm that uses the optimal solution of the relax
ation with objective value at most C-max + O(root C-max). Unlike asymptotic
ally optimal algorithms that rely on probabilistic assumptions, our propose
d algorithms make no probabilistic assumptions and they are asymptotically
optimal for all instances with a large number of jobs (packets). In computa
tional experiments our algorithms produce schedules which are within 1% of
optimality even for moderately sized problems. (C) 1999 Academic Press.