Competitive analysis for make‐to‐order scheduling with reliable lead time quotation

This paper makes extended studies on the discrete problem of online scheduling and reliable lead time quotation (discrete Q‐SLTQ) introduced by Keskinocak et al. (2001). We first relax the assumption on revenue function from a linear decreasing function to any decreasing function. We present an online deterministic strategy which is optimal in competitiveness for concave revenue functions. The above results are further extended to the continuous Q‐SLTQ model where orders are released at arbitrary time points. For the discrete Q‐SLTQ problem, if orders are with nonuniform lengths, we prove the nonexistence of online strategies with bounded competitive ratios; otherwise if orders are with unit length but various weights, we present an optimal online strategy.