Abstract:

We investigate a two-stage supply chain scheduling problem in which jobs have the holding time which is limited by a constant. A job which is processed completely by the machine needs to dispatch with batch to customer by many vehicles, and a job will incur a holding cost if its completion time is earlier than its dispatch date. Each job will incur an early (tardy) penalty if it is early (tardy) with respect to the common due window under a given schedule. The objective is to find the optimal size and location of the window, the optimal dispatch date for each job, as well as an optimal job sequence to minimize a cost function based on earliness, tardiness, holding time, window location, window size, and batch delivery.
We provide the proof of NP-hard for the problem. Then, we consider the case where the unit cost of holding time is not more than the unit cost of tardiness and give a pseudo-polynomial time algorithm for this case.

Key words: holding time, supply chain scheduling, NP-hard, pseudo-polynomial time algorithm