Controlling Queues with Constant Interarrival Times

We consider server systems with constant interarrival times subject to arbitrary cost functions. This type of systems arises when we have full control over arrivals. Typical examples include situations where computers or network elements schedule periodic updates at regular time intervals (cf. cron daemon in unix systems), a congestion avoidance or load balancing mechanism imposes regular inter-arrival times at a lower level, and also in customer service and healthcare systems where patients book appointments. In the basic case, known as the D/M/1 queue, there is a single server and the service times are independent and exponentially distributed. We study different value functions for the D/M/1 queue that characterize the expected cost difference in the infinite time horizon if the system is initially in a given state instead of being in equilibrium. When the arrival process is Poisson, the corresponding results are compact and known. The fixed interarrival times complicate the situation, and even the mean waiting time is harder to characterize. We apply our results to develop a heuristic for a dispatching problem, and evaluate the heuristic numerically.