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

Wing Kwan Yeung, Tsan Ming Choi, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

48 Citations (Scopus)


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.
Original languageEnglish
Article number5460987
Pages (from-to)2767-2777
Number of pages11
JournalIEEE Transactions on Automatic Control
Issue number12
Publication statusPublished - 1 Dec 2010


  • NP-hardness
  • operations research
  • optimal control
  • scheduling

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Control and Systems Engineering
  • Computer Science Applications


Dive into the research topics of 'Optimal scheduling of a single-supplier single-manufacturer supply chain with common due windows'. Together they form a unique fingerprint.

Cite this