Some Resource Allocation Problems

We include three works on resource allocation in this thesis. Proper pricing helps the system to allocate resource efficiently. However, the computational efforts to obtain such prices are not always easy. In airline network revenue setting, high-quality bid prices can be obtained via approximate dynamic programming approach. However, this leads to an exponential-size linear program which is slow to solve. We show that this large linear program is actually equivalent to a compact linear program with appealing interpretation by exploiting the minimum-cost network flow structure of this problem. Computational experiments indicate that our results can speed up the computation for the approximate linear programming approach by a factor ranging between 13 and 135. In the second chapter, we study how to better serve clients by allocating resources to open facilities with right location and type. We extend the classical facility location problem by associating types with the facilities and the clients. The types define a partial ordering and a client can only be served by facilities of equal or higher type. We show how to obtain approximation algorithms for two interesting special cases. We also study the problem embedded in time, which is known as the lot-sizing variant. We give algorithm that finds optimal solution for the variant. In the third chapter, we study how to allocate medical resource in imaging facilities. The most common method to allocate imaging machine time is by a appointment system. However, despite the best efforts by medical staff, the inherently stochastic nature of the duration of various procedures and unexpected disruptions can bring considerate congestion to the system. In the multi-site setting, we seek to complement appointment scheduling with real-time resource sharing. By monitoring system status and making prediction of future, we can identify potential congestions and divert patients accordingly to prevent these congestions from happening. We provide simulation results showing that this method improves patient waiting time and facilities overtime, which are two important quality measurements