Optimal delivery time quotation in supply chains to minimize tardiness and delivery costs

There are many situations when, due to unexpected delays, the supplier may not be able to deliver some orders by the promised due dates. We present a model for quoting attainable delivery times to minimize tardiness penalties and delivery costs, when deliveries take place in batches. We show that the general problem is strongly NP$${\mathcal {NP}}$$-hard, but when all orders have the same per-unit due-date-assignment cost, it is NP$${\mathcal {NP}}$$-hard only in the ordinary sense. For the latter case, we present a pseudo-polynomial algorithm, which is converted into a fully polynomial-time approximation scheme. If the tardiness penalties are also identical, we show that the problem can be solved in polynomial time.