  We study a class of scheduling problems, where each job is divided into a
batch of unit-size tasks and these tasks can be executed in parallel on
multiple servers with New-Better-than-Used (NBU) service time distributions.
While many delay optimality results are available for single-server queueing
systems, generalizing these results to the multi-server case has been
challenging. This motivated us to investigate near delay-optimal scheduling of
batch jobs in multi-server queueing systems. We consider three lowcomplexity
scheduling policies: the Fewest Unassigned Tasks first (FUT) policy, the
Earliest Due Date first (EDD) policy, and the First-Come, First-Served (FCFS)
policy. We prove that for arbitrary number, batch sizes, arrival times, and due
times of the jobs, these scheduling policies are near delay-optimal in
stochastic ordering for minimizing three classes of delay metrics among all
causal and non-preemptive policies. In particular, the FUT policy is within a
constant additive delay gap from the optimum for minimizing the mean average
delay, and the FCFS policy within twice of the optimum for minimizing the mean
maximum delay and the mean p-norm of delay. The key proof tools are several
novel samplepath orderings, which can be used to compare the sample-path delay
of different policies in a near-optimal sense.
