An asymptotically optimal algorithm for job shop scheduling

摘要

We propose asymptotically optimal algorithms for job shop scheduling. We propose a fluid relaxation for the job shop scheduling problem, in which we replace discrete jobs with the flow of a continuous fluid. We compute an optimal solution of the fluid relaxation in closed form, obtain a lower bound C/sub max/ to the job shop scheduling problem, and construct a feasible schedule from the fluid relaxation with objective value at most C/sub max/+O(/spl radic/C/sub max/), where the constant in the O(/spl middot/) notation is independent of the number of jobs. However, it depends on the processing times of the jobs, thus producing an asymptotically optimal schedule as the total number of jobs tends to infinity. If the initially present jobs increase proportionally, then our algorithm produces a schedule with value at most C/sub max/+O(1). In computational experiments our algorithms produce schedules which are within 1% of optimality even for moderately sized problems.