Video-on-Demand (VoD) services require frequent updates in file conguration on the storage
subsystem, so as to keep up with the frequent changes in movie popularity. This defines a
natural reconfiguration problem in which the goal is to minimize the cost of moving from one
file configuration to another. The cost is incurred by file replications performed throughout
the transition. The problem shows up also in production planning, preemptive scheduling with
set-up costs, and dynamic placement of Web applications. We show that the reconfiguration
problem is NP-hard already on very restricted instances. We then develop algorithms which
achieve the optimal cost by using servers whose load capacities are increased by O(1), in particular,
by factor 1 + eps for some small 0 < eps < 1 when the number of servers is fixed, and
by factor of 2 + 2eps for arbitrary number of servers, for some 0 < eps < 1. To the best of our
knowledge, this fundamental optimization problem is studied here for the first time.