We consider a system of parallel queues where tasks are assigned (dispatched) to one of the available servers upon arrival. The dispatching decision is based on the full state information, i.e., on the sizes of the new and existing jobs. We are interested in minimizing the so-called mean slowdown criterion corresponding to the mean of the sojourn time divided by the processing time. Assuming no new jobs arrive, the shortest-processing-time-product (SPTP) schedule is known to minimize the slowdown of the existing jobs. The main contribution of this paper is three-fold: 1) To show the optimality of SPTP with respect to slowdown in a single server queue under Poisson arrivals; 2) to derive the so-called size-aware value functions for M G 1-FIFO LIFO SPTP SPT SRPT with general holding costs of which the slowdown criterion is a special case; and 3) to utilize the value functions to derive efficient dispatching policies so as to minimize the mean slowdown in a heterogeneous server system. The derived policies offer a significantly better performance than e.g., the size-aware-task-assignment with equal load (SITA-E) and least-work-left (LWL) policies.
@cite_14: In this paper we consider the problem of routing customers to identical servers, each with its own infinite capacity queue. Under the assumptions that the service times form a sequence of independent and identically distributed random variables with increasing failure rate distribution and state information is not available, we establish that the round robin policy minimizes, in the sense of a separable increasing convex ordering, the customer response times and the numbers of customers in the queues. This work was supported in part by the National Science Foundation under grant ASC 88-8802764 and NCR-9116183. ******************************
@cite_22: Abstract We consider the problem of task assignment in a distributed system (such as a distributed Web server) in which task sizes are drawn from a heavy-tailed distribution. Many task assignment algorithms are based on the heuristic that balancing the load at the server hosts will result in optimal performance. We show this conventional wisdom is less true when the task size distribution is heavy-tailed (as is the case for Web file sizes). We introduce a new task assignment policy, called Size Interval Task Assignment with Variable Load (SITA-V). SITA-V purposely operates the server hosts at different loads, and directs smaller tasks to the lighter-loaded hosts. The result is that SITA-V provably decreases the mean task slowdown by significant factors (up to 1000 or more) where the more heavy-tailed the workload, the greater the improvement factor. We evaluate the tradeoff between improvement in slowdown and increase in waiting time in a system using SITA-V, and show conditions under which SITA-V represents a particularly appealing policy. We conclude with a discussion of the use of SITA-V in a distributed Web server, and show that it is attractive because it has a simple implementation which requires no communication from the server hosts back to the task router.
@cite_8: We consider a cluster of heterogeneous servers, modeled as M G 1 first-come first-serve queues with different processing speeds. A dispatcher that assigns jobs to the servers takes as input only the size of the arriving job and the overall job-size distribution. This general model captures the behavior of a variety of real systems, such as web server clusters. Our goal is to identify assignment strategies that the dispatcher can perform to minimize expected completion time and waiting time. We show that there exist optimal strategies that are deterministic, fixing the server to which jobs of particular sizes are always sent. We prove that the optimal strategy for systems with identical servers assigns a non-overlapping interval range of job sizes to each server. We then prove that when server processing speeds differ, it is necessary to assign each server a distinct set of intervals of job sizes in order to minimize expected waiting or response times.
@cite_29: We consider a queuing system consisting of a finite number of identical exponential servers. Each server has its own queue, and upon arrival each customer must be assigned to some server's queue. Under the assumption that no jockeying between queues is permitted, it is shown that the intuitively satisfying rule of assigning each arrival to the shortest line maximizes, with respect to stochastic order, the discounted number of customers to complete their service in any time t. QUEUING; SHORTEST LINE; STOCHASTIC ORDER; MARKOV DECISION PROCESSES
@cite_9: We consider a distributed server system in which each host processes tasks in First-Come-First-Served order and each task's service demand is known immediately upon task arrival. We consider four task assignment policies commonly proposed for such distributed server systems: Round Robin; Random; Size-Based, in which all tasks within a given size range are assigned to a particular host; and Dynamic-Least-Work-Remaining, in which a task is assigned to the host with the least outstanding work. Using analysis and simulation, we explore the influence of task size variability on which task assignment policy is best. Surprisingly, we find that not one of the above task assignment policies is best. In particular, we find that when the task sizes are not highly variable, the Dynamic policy is preferable. However, when task sizes show the degree of variability more characteristic of empirically measured workloads, the size-based policy is the best choice. We use the resulting observations to argue in favor of a specific size-based policy, SITA-E, that shows very good performance for realistic task size distributions.
@cite_6: 
@cite_24: As jobs arrive they have to be routed to one of two similar exponential servers. It is shown that if the queue lengths at both servers are observed then the Optimal decision is to route jobs to the shorter queue, whereas if the queue lenths are not observed then it is best to alternate between queues, provided the initial distribution of the two queue sizes is the same. The optimality of these routing strategies is independent of the statistics of the job arrivals.
@cite_17: We consider optimal load balancing in a distributed computing environment consisting of homogeneous unreliable processors. Each processor receives its own sequence of tasks from outside users, some of which can be redirected to the other processors. Processing times are independent and identically distributed with an arbitrary distribution. The arrival sequence of outside tasks to each processor may be arbitrary as long as it is independent of the state of the system. Processors may fail, with arbitrary failure and repair processes that are also independent of the state of the system. The only information available to a processor is the history of its decisions for routing work to other processors, and the arrival times of its own arrival sequence. We prove the optimality of the round-robin policy, in which each processor sends all the tasks that can be redirected to each of the other processors in turn. We show that, among all policies that balance workload, round robin stochastically minimizes the nth task completion time for all n, and minimizes response times and queue lengths in a separable increasing convex sense for the entire system. We also show that if there is a single centralized controller, round-robin is the optimal policy, and a single controller using round-robin routing is better than the optimal distributed system in which each processor routes its own arrivals. Again "optimal" and "better" are in the sense of stochastically minimizing task completion times, and minimizing response time and queue lengths in the separable increasing convex sense.
Only a few optimality results are known for the dispatching problems. Assuming exponentially distributed interarrival times and job sizes, @cite_29 shows that JSQ with FIFO minimizes the mean waiting time when the number in each queue is available. Also @cite_24 argues for the optimality of JSQ FIFO when the number in each queue is available, while the Round-Robin (RR), followed by FIFO, is shown to be the optimal policy when it is only known that the queues were initially in the same state. @cite_14 proves that RR FIFO is optimal with the absence of queue length information if the job sizes have a non-decreasing hazard function. The RR results were later generalized in @cite_17 . Whitt @cite_6 , on the other hand, provides several counterexamples where JSQ FIFO policy fails. @cite_22 and Harchol- @cite_9 assume that the dispatcher is aware of the size of a new job, but not of the state of the FIFO queues, and propose policies based on job size intervals (e.g., short jobs to one queue, and the rest to another). @cite_8 later showed that such a policy is the optimal size-aware state-independent dispatching policy for homogeneous servers.