Optimal scheduling of a single-supplier single-manufacturer supply chain with common due windows

We study a supply chain scheduling control problem involving a single supplier, a single manufacturer and multiple retailers, where the manufacturer with limited production capacity can only take some of the orders of the retailers. The manufacturer aims to maximize its profit, which is a function of the storage time, storage quantity, order sequence dependent weighted storage costs, and idle time of the orders to be accepted. We formulate the problem as a two-machine common due windows proportionate flow shop scheduling problem. We show that the problem is NP-hard. We provide the first pseudo-polynomial algorithm to optimally solve the problem. We show that for an accepted set of orders the shortest processing time earliest permutation schedule yields an optimal schedule. We prove that we can reduce the latest due dates of the due windows, which are given parameters, for minimizing the computational effort. We establish a tight upper bound on the enumeration process to manage the order idle time. We eliminate the need for generating all the optimal partial schedules to obtain an optimal solution, thus reducing the running time of our algorithm for solving the problem. We computationally tested the algorithm and the results show that the algorithm can solve large-sized problems very efficiently.