Iterative Algorithm for Threshold Calculation in the Problem of Routing Fixed Size Jobs to Two Parallel Servers

Abstract

At present, solutions of many practical problems require significant computational resources and systems (grids, clouds, clusters etc.), which provide appropriate means are constantly evolving. The capability of the systems to fulfil quality of service requirements pose new challenges for the developers. One of the well-known approaches to increase system performance is the use of optimal scheduling (dispatching) policies. In this paper the special case of the general problem of finding optimal allocation policy in the heterogeneous n-server system processing fixed size jobs is considered. There are two servers working independently at constant but different speeds. Each of them has a dedicated queue (of infinite capacity) in front of it. Jobs of equal size arrive at the system. Inter-arrival times are i.i.d. random variables with general distribution with finite mean. Each job upon arrival must be immediately dispatched to one of the two queues wherefrom it will be served in FCFS manner (no pre-emption). The objective is the minimization of mean job sojourn time in the system. It is known that under this objective the optimal policy is of threshold type. The authors propose scalable fast iterative non-simulation algorithm for approximate calculation of the policy parameter (threshold). Numerical results are given.

Keywords

• continuous MDP
• discretization
• job allocation
• optimal policy
• threshold