Online Lead Time Quotation with Predictions

In this work, we study the problem of online lead time quotation with predictions, where the Decision Maker (DM) has one unit of resource to process arriving orders, with each requiring a unit processing time. The reward earned from processing each order decreases with its lead time, and drops to zero when the lead time limit is reached. Without knowing the actual future sequences, which could be chosen adversarially, the DM aims to maximize the total revenue through deciding irrevocably the lead time of each order upon its arrival. We assume that a prediction is available to the DM. We establish for this problem the upper bounds of the two desiderata of online algorithms with predictions: consistency (performance improvement with accurate prediction) and competitiveness (worst-case performance with inaccurate prediction). We then propose an original online algorithmic framework, featuring dynamic reward thresholds at each time step, which are based on both the prediction and the prescribed competitiveness. We show via an original phase construction algorithm that such algorithmic framework achieves the highest possible consistency when the lead time limit is large, and it also achieves the highest possible competitiveness when it is required. We geometrically illustrate the proposed policy and the trade-off between the two desiderata. Numerical experiments further shows superior empirical performance with accurate predictions, and robustness with mildly inaccurate predictions, as compared to an algorithm with a fixed threshold. Numerical results also provide managerial insights on the desirable competitiveness to be prescribed.