FixedOrder Scheduling on Parallel Machines We consider the following natural scheduling problem: Given a sequence of jobs with weights and processing times, one needs to assign each job to one of m identical machines in order to minimize the sum of weighted completion times. The twist is that for machine the jobs assigned to it must obey the order of the input sequence, as is the case in multiserver queuing systems. We establish a constant factor approximation algorithm for this (strongly NPhard) problem. Our approach is necessarily very different from what has been used for similar scheduling problems without the fixedorder assumption. We also give a QPTAS for the special case of unit processing times.

Simple NearOptimal Scheduling for the MG1. We consider the problem of preemptively scheduling jobs to minimize mean response time of an MG1 queue. When the scheduler knows each jobu0027s size, the shortest remaining processing time (SRPT) policy is optimal. Unfortunately, in many settings we do not have access to each jobu0027s size. Instead, we know only the job size distribution. In this setting, the Gittins policy is known to minimize mean response time, but its complex priority structure can be computationally intractable. A much simpler alternative to Gittins is the shortest expected remaining processing time (SERPT) policy. While SERPT is a natural extension of SRPT to unknown job sizes, it is unknown how close SERPT is to optimal.  :112,present a new variant of SERPT called monotonic SERPT (MSERPT) which is as simple as SERPT but has provably nearoptimal mean response time at all loads for any job size distribution. Specifically, we prove the mean response time ratio between MSERPT and Gittins is at most 3 for load rho leq 89 and at most 5 for any load. This makes MSERPT the only scheduling policy known to be a constantfactor approximation of Gittins.