Single-machine batch delivery scheduling with an assignable common due window

Yunqiang Yin, Edwin Tai Chiu Cheng, Chou Jung Hsu, Chin Chia Wu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

71 Citations (Scopus)


This paper addresses a batch delivery single-machine scheduling problem in which jobs have an assignable common due window. Each job will incur an early (tardy) penalty if it is early (tardy) with respect to the common due window under a given schedule. There is no capacity limit on each delivery batch, and the cost per batch delivery is fixed and independent of the number of jobs in the batch. 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 show that the problem can be optimally solved in O(n8) time by a dynamic programming algorithm under a reasonable assumption on the relationships among the cost parameters. A computational experiment is also conducted to evaluate the performance of the proposed algorithm. We also show that some special cases of the problem can be optimally solved by lower order algorithms.
Original languageEnglish
Pages (from-to)216-225
Number of pages10
JournalOmega (United Kingdom)
Issue number2
Publication statusPublished - 1 Apr 2013


  • Batch delivery
  • Due window assignment
  • Scheduling

ASJC Scopus subject areas

  • Strategy and Management
  • Management Science and Operations Research
  • Information Systems and Management


Dive into the research topics of 'Single-machine batch delivery scheduling with an assignable common due window'. Together they form a unique fingerprint.

Cite this