Performance Optimization With Deadlines and Job Transfers

Abstract. A model of two coupled single-server queues is analyzed in the steady state. Each new arrival into queue 1 is assigned a random deadline. If a job has not started service before its deadline expires, it is transferred to queue 2. The problem is to determine the optimal value of the average deadline period, in order to minimize a given cost function expressed in terms of average numbers of jobs present in the two queues. That problem can be solved numerically with arbitrary degree of accuracy. A simple heuristic which produces good estimates is also developed; its performance is compared with the optimal solution