STOCHASTIC SCHEDULING OF PARALLEL QUEUES WITH SET-UP COSTS

We consider the problem of allocating a single server to a system of q ueues with Poisson arrivals. Each queue represents a class of jobs and possesses a holding cost rate, general service distribution, and a se t-up cost. The objective is to minimize the expected cost due to the w aiting of jobs and the switching of the server. A set-up cost is requi red to effect an instantaneous switch from one queue to another. We pa rtially characterize an optimal policy and provide a simple heuristic scheduling policy. The heuristic's performance is evaluated in the cas es of two and three queues by comparison with a numerically obtained o ptimal policy. Simulation results are provided to demonstrate the effe ctiveness of our heuristic over a wide range of problem instances with four queues.