Supply chain scheduling with receiving deadlines and non-linear penalty

We study the operations scheduling problem with delivery deadlines in a three-stage supply chain process consisting of (1) heterogeneous suppliers, (2) capacitated processing centres (PCs), and (3) a network of business customers. The suppliers make and ship semi-finished products to the PCs where products are finalized and packaged before they are shipped to customers. Each business customer has an order quantity to fulfil and a specified delivery date, and the customer network has a required service level so that if the total quantity delivered to the network falls below a given targeted fill rate, a non-linear penalty will apply. Since the PCs are capacitated and both shipping and production operations are non-instantaneous, not all the customer orders may be fulfilled on time. The optimization problem is therefore to select a subset of customers whose orders can be fulfilled on time and a subset of suppliers to ensure the supplies to minimize the total cost, which includes processing cost, shipping cost, cost of unfilled orders (if any), and a non-linear penalty if the target service level is not met. The general version of this problem is difficult because of its combinatorial nature. In this paper, we solve a special case of this problem when the number of PCs equals one, and develop a dynamic programming-based algorithm that identifies the optimal subset of customer orders to be fulfilled under each given utilization level of the PC capacity. We then construct a cost function of a recursive form, and prove that the resulting search algorithm always converges to the optimal solution within pseudo-polynomial time. Two numerical examples are presented to test the computational performance of the proposed algorithm.