home/Java applets/Dispatching Problem

Dispatching Problem to Parallel Queues:

(Dispatching applet requires Java support.)

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 load balancing 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 the first-come-first-served (FCFS) order, although other service disciplines such as last-come-first-served (LCFS), shortest-remaining-processing-time (SRPT) and processor sharing (PS), can also be relevant.

Arrival process:

  • 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.

Dispatching policies:

  • 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.
  • With heavy-tailed distributions, such as Pareto, the situation is the opposite.

Links

  1. References
  2. My page on the dispatching problem.
  3. Back to Java applet list.
Valid HTML 4.01 Transitional

Esa Hyytiä. Created on December 2010. Last update on May 2011.