Asymptotically Optimal Algorithms for Job Shop Scheduling and Packet Routing

摘要

We propose asymptotically optimal algorithms for the job shop scheduling and packet routing problems. 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_(max) to the job shop scheduling problem, and construct a feasible schedule from the fluid relaxation with objective value at most C_(max)+ O((C_(max))~(1/2)), where the constant in the O(centre dot) notation is 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 proportionally, then our algorithm produces a schedule with value at most C_(max) + O(1). For the packet routing problem with fixed paths the previous algorithm applies directly. For the general packet routing problem we propose a linear programming relaxation that provides a lower bound C_(max) and an asymptotically optimal algorithm that uses the optimal solution of the relaxation with objective value at most C _(max) + O(sp root C_(max)). Unlike asymptotically optimal algorithms that rely on probabilistic assumptions, our proposed algorithms make no probabilistic assumptions and they are asymptotically optimal for all instances with a large number of jobs (packets). In computational experiments our algorithms produce schedules which are within 1% of optimality even for moderately sized problems.