Dynamic admission control for two customer classes with stochastic demands and strict due dates

Abstract

We study a dynamic capacity allocation problem with admission control decisions of a company that caters for two demand classes with random arrivals, capacity requirements and strict due dates. We formulate the problem as a Markov decision process (MDP) in order to find the optimal admission control policy that maximises the expected profit of the company. Such a formulation suffers a state-space explosion. Moreover, it involves an additional dimension arising from the multiple possible order sizes that customers can request which further increases the complexity of the problem. To reduce the cardinality of possible policies, and, thus, the computational requirements, we propose a threshold-based policy. We formulate an MDP to generate such a policy. To deal with the curse of dimensionality, we develop threshold-based approximate algorithms based on the state-reduction heuristics with aggregation proposed previously. Our results reveal that for the majority of instances considered the optimal policy has a threshold structure. We then demonstrate the superiority of the proposed threshold-based approximate algorithms over two benchmark policies in terms of the generated profits and the robustness of the solutions to changes in operational conditions. Finally, we show that our proposed policies are also robust to changes in actual demand from its estimation.

Keywords:

• demand and revenue management
• admission control
• Markov decision process
• heuristics
• due dates

Acknowledgements

The authors are thankful to J. Will M. Bertrand for his useful suggestions which enriched the contribution of the paper. The authors are also grateful to anonymous referees for their valuable comments which improved the quality of the paper.

Notes

No potential conflict of interest was reported by the authors.

1 Note that when updating to the next period, period within will become period at the beginning of the next period. Thus, an unit of reserved/available capacity in period will be shifted to period with an update to the next period. With our representation of the system states, we can properly capture whether an unit of reserved capacity is shifted or not from to with each update to the next period.

2 For a given cumulative vector , its corresponding reservation vector can be calculated as follows: , and for , .

3 For instance, consider that and and that there is no arrival of any class at the beginning of a period. If all the capacity is available within , i.e. the Equation (4(4) ) ensures that also .

4 We exclude the presentation of the average CPU time of Experiment 2 because different probabilities of occurrence and higher differences in the order sizes do not have a significant influence on the CPU time.

5 Note that we show only the results from Experiment 2 with equal probabilities of occurrence (sets ). This is due to the long computational times needed to obtain the PLB policy with the myopic approach (the average CPU time is 2212 s). Our main insights based on the results presented on Figure 1 still hold for all considered instances of Experiment 2 under the FCFS policy and the T-SFAH policies.

Additional information

Funding

Research that the authors conducted at Center for Operations Research and Econometrics, Université catholique de Louvain was partially supported by the ARC project ‘Managing Shared Resources in Supply Chains’ [ARC 08-13-008].