Online Lead Time Quotation with Predictions

In this work, we study the problem of online lead time quotation with predictions. The decision maker (DM) has one unit of resource to process arriving orders, 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 demands, which could be chosen adversarially, the DM aims to maximize the total revenue through irrevocably deciding the lead time of each order upon its arrival. We assume that a possibly inaccurate prediction of the future demand 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 is based on both the prediction and the prescribed competitiveness. We show via an original phase construction algorithm that such an 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 the level of required competitiveness. To provide insights, we geometrically illustrate the proposed policy and the trade-off between the two desiderata on worst-case instances. Numerical experiments further show superior empirical performance of our algorithm with accurate predictions and resilience with mildly inaccurate predictions as compared with an algorithm without prediction. Numerical results also provide managerial insights into the desirable competitiveness to be prescribed.

History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms–Discrete.

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1104) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2025.1104). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.