Optimal resource allocation for time-reservation systems |
| |
Authors: | Ran YangAuthor Vitae Sandjai BhulaiAuthor Vitae Rob van der MeiAuthor Vitae Frank SeinstraAuthor Vitae |
| |
Affiliation: | a VU University Amsterdam, Faculty of Sciences, De Boelelaan 1081a, 1081 HV, Amsterdam, The Netherlandsb CWI, Advanced Communication Networks, P.O. Box 94079, 1090 GB, Amsterdam, The Netherlands |
| |
Abstract: | This paper studies the optimal resource allocation in time-reservation systems. Customers arrive at a service facility and receive service in two steps; in the first step information is gathered from the customer, which is then sent to a pool of computing resources, and in the second step the information is processed after which the customer leaves the system. A central decision maker has to decide when to reserve computing power from the pool of resources, such that the customer does not have to wait for the start of the second service step and that the processing capacity is not wasted due to the customer still being serviced at the first step. The decision maker simultaneously has to decide on how many processors to allocate for the second processing step such that reservation and holding costs are minimized. Since an exact analysis of the system is difficult, we decompose the system into two parts which are solved sequentially leading to nearly optimal solutions. We show via dynamic programming that the near-optimal number of processors follows a step function with as an extreme policy the bang-bang control. Moreover, we provide new fundamental insights in the dependence of the near-optimal policy on the distribution of the information gathering times. Numerical experiments demonstrate that the near-optimal policy closely matches the performance of the optimal policy of the original problem. |
| |
Keywords: | Constrained Markov decision problems Monotonicity Optimal resource allocation Queueing theory Time-reservation systems |
本文献已被 ScienceDirect 等数据库收录! |
|