|
Given a set of facilities, or servers S = { s1, s2, . . ., sm} and a set of requests R = { r1, r2, . . ., rn} with each server si having the serving capacity of ci and the assignment cost dij occurred if the request rj has been assigned to server si , the online facility problem under our consideration is to find an assignment for a new coming request rj to a server before the next one arrived, such that in the end each si serves exactly ci requests and such that the total occurring cost ∑ n j=1 {dij|rj is assigned to si} is minimized. This paper considers a constrained version of online facility problem (COFP, for short) in which ci = 2 for all i = {1, 2, . . ., m} and dij = 2 |j-i| for all i , j. First, we obtain the optimal assignment for the offline version of COFP by exploiting a nice property of powers of two and the so-called the natural order assignment. Second, we design an online algorithm for COFP is based on the optimal assignment for the offline version of COFP. We show that our online algorithm runs in linear time and always achieves the optimal assignment for the COFP.
|
