Nearly optimal competitive online replacement policies. (English) Zbl 0894.68076

Summary: This paper studies the online replacement problem. In this problem, an online player is engaged at each time in one activity. Associated with each activity are a changeover cost and flow rate. While involved in an activity the player’s budget is depleted at the activity’s flow rate. The player can switch to a new activity whenever it is offered but he pays a changeover cost. The player’s goal is to decide when to switch activities so that his total cost is minimized. Typical applications are: equipment, jobs and supplier replacement, mortgage refinancing, etc. 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.


68Q25 Analysis of algorithms and problem complexity
90B25 Reliability, availability, maintenance, inspection in operations research
91A05 2-person games
Full Text: DOI Link