Scheduling and Reliable Lead-Time Quotation for Orders with Availability Intervals and Lead-Time Sensitive Revenues

Motivated by applications in the manufacturing and service industries, we consider two models for coordinating scheduling with lead-time quotation: a basic model with a single customer type, and an enhanced model where an additional second customer type expects immediate service or production. In both models, revenues obtained from the customers are sensitive to the lead time, there is a threshold of lead time above which the customer does not place an order, and the quoted lead times are 100% reliable. These models are related to well-known scheduling problems, which have been studied in both offline and online settings. We introduce the immediate quotation case and study it with the (traditional) online version. We provide complexity results for the offline case, and perform competitive analysis for the online cases. A natural question of bridging the gap between the online and quotation models leads us to the delayed quotation model, which we study briefly. The analysis of these models provides useful qualitative insights as well.