Abstract:

This Paper studies the following online replacement problem. There is a real function f(t), called the flow rate, defined over a finite time horizon [0,T]. It is known that m% f(t) % M for some reals 0 % m < M. At time 0 an online player starts to pay money at the rate of f(0). At each time 0 < t % T the player may changeover and continue paying money at the rate f(t). The complication is that each such changeover incures some fixed penalty. The player is called online as at each time t the player knows f only over the time interval [0,t]. The goal of the player is to minimize the total cost comprised of cumulative payment flow plus change over costs. This formulation of the replacement problem has various interesting applications among which are: equipment replacement, supplier replacement, the menu cost problem and mortgagere financing. With respect to the competitive ratio performance measure, this paper seeks to determine the best possible competitive ratio achievable by an online replacement policy. Our results include the following: a general lower bound on the performance of any deterministic policy, a policy that is optimal in several special cases and a simple policy that is approximately optimal.

Website