Premium
Locating mobile servers on a network with markovian properties
Author(s) -
Berman Oded,
Odoni Amedeo R.
Publication year - 1982
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230120106
Subject(s) - server , computer science , tree network , heuristic , relocation , function (biology) , markov process , tree (set theory) , probabilistic logic , mathematical optimization , simple (philosophy) , set (abstract data type) , computer network , facility location problem , node (physics) , mathematics , mathematical analysis , philosophy , statistics , epistemology , artificial intelligence , evolutionary biology , biology , programming language , structural engineering , engineering
The median problem has been generalized to the case in which facilities (“servers”) can be moved, at a cost, on the network in response to changes in the state of the network. Such changes are brought about by changes in travel times on the links of the network due to the occurrence of probabilistic events. For the case examined here, transitions among states of the network are assumed to be Markovian. The problem is examined for an objective which is a weighted function of demand travel times and of server relocation costs. It is shown that when these latter costs are a concave function of the time to travel from the current server location to the new server location, an optimal set of server locations exists solely on the nodes of the network. The location‐relocation problem can be formulated as an integer programming problem. The problem of locating a single server on a network which is a tree is shown to have a simple solution. A heuristic algorithm for the single server on a general network is also described. The paper develops simple bounds for the general multifacility, multistate problem and concludes with the description of a relaxed version of this model and with a discussion of the model's applicability.