非表示:
キーワード:
-
要旨:
We study an on-line problem that is motivated by service calls management in a
remote support center. When a customer calls the remote support center of a
software company, a technician opens a service request and assigns it a
severity rating. This request is then transferred to the appropriate support
engineer (SE) who establishes a connection to the customer's site and uses
remote diagnostic capabilities to resolve the problem. We assume that the SE
can service at most one customer at time and a request service time is
negligible. There is a constant setup cost of creating a new connection to a
customer's site and a specific cost per request for delaying its service that
depends on the severity of the request. The problem is to decide which
customers to serve first so as to minimize the incurred cost. This problem with
just two customers is a natural generalization of the TCP acknowledgment
problem. For the on-line version of the Remote Server Problem (RSP), we present
algorithms for the general case and for a special casef of two customers that
achieve competitive ratios of exactly 4 and 3, respectively. We also show that
no deterministic on-line algorithm can have competitive ratio better than 3.
Then we study generalized versions of our model, these are the case of an
asymmetric setup cost function and the case of multiple SEs. For the off-line
version of the RSP, we derive an optimal algorithm with a polynomial running
time for a constant number of customers.
