Dispatching Problem to Parallel Queues:
The dispatching problem, or the task assignment problem, is a commonly
encountered dynamic decision problem, where upon an arrival of a new job,
one has to dispatch the job to one of the available servers (parallel queues).
Some examples include
manufacturing sites, batch jobs in supercomputing,
web server farms and other distributed server systems.
The objective can be the minimization of the mean sojourn time,
i.e., the mean response time.
This is achieved by an appropriate
between the servers.
The optimal dispatching policy depends on the available information, i.e.,
what is known about the new job and the state of the servers.
It is often assumed that the servers process the jobs in
although other service disciplines such as
processor sharing (PS),
can also be relevant.
- Two single server queues with FCFS, LCFS or SRPT.
- Poisson arrival process with rate λ=1.5.
- Constant, Uniform, Exponential or Pareto distributed
job sizes with mean E[X]=1.
- Hence, the offered load ρ=1.5.
- Random (RND) chooses the queue uniformly in random.
- Round-Robin (RR) alternates between the queues in
some predefined order.
- Join-the-Shortest-Queue (JSQ) chooses the queue with
the least number of jobs.
- Least-Work-Left (LWL) chooses the queue with
the smallest workload.
- Size-Interval-Task-Assignment (SITA-E) assigns jobs
shorter than d to Queue 1, and the rest to Queue 2,
with d chosen to balance the load.
See a page on SITA.
Key metrics (right):
- Mean number of jobs E[N],
- Mean number of busy servers E[B],
- Mean response time E[T],
- Mean job size E[X] and its variance V[X].
Some interesting phenomena
- Random (RND) is a stateless policy, while
Round-robin (RR) needs a state at the dispatcher.
- Round-robin (RR) "regulates" the arrival process and achieves a lower
mean response time than RND.
- JSQ assumes that the current occupation in the queues is available,
LWL that all job sizes are known,
and SITA that the size of the current job is available.
- With light-tailed distributions (e.g., constant and uniform)
and Poisson arrivals (cf. RND),
the FCFS discipline is better than LCFS.
heavy-tailed distributions, such as Pareto, the situation
is the opposite.
- My page on the dispatching problem.
- Back to Java applet list.
Esa Hyytiä. Created on December 2010. Last update on May 2011