  We introduce and study a class of optimization problems we coin replenishment
problems with fixed turnover times: a very natural model that has received
little attention in the literature. Nodes with capacity for storing a certain
commodity are located at various places; at each node the commodity depletes
within a certain time, the turnover time, which is constant but can vary
between locations. Nodes should never run empty, and to prevent this we may
schedule nodes for replenishment every day. The natural feature that makes this
problem interesting is that we may schedule a replenishment (well) before a
node becomes empty, but then the next replenishment will be due earlier also.
This added workload needs to be balanced against the cost of routing vehicles
to do the replenishments. In this paper, we focus on the aspect of minimizing
routing costs. However, the framework of recurring tasks, in which the next job
of a task must be done within a fixed amount of time after the previous one is
much more general and gives an adequate model for many practical situations.
  Note that our problem has an infinite time horizon. However, it can be fully
characterized by a compact input, containing only the location of each store
and a turnover time. This makes determining its computational complexity highly
challenging and indeed it remains essentially unresolved. We study the problem
for two objectives: min-avg minimizes the average tour length and min-max
minimizes the maximum tour length over all days. For min-max we derive a
logarithmic factor approximation for the problem on general metrics and a
6-approximation for the problem on trees, for which we have a proof of
NP-hardness. For min-avg we present a logarithmic approximation on general
metrics, 2-approximation for trees, and a pseudopolynomial time algorithm for
the line. Many intriguing problems remain open.
