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.
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 (Equation4
(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 still hold for all considered instances of Experiment 2 under the FCFS policy and the T-SFAH policies.