Improved algorithms for single-machine common due window assignment and scheduling with batch deliveries

Research output: Journal article publicationJournal articleAcademic researchpeer-review

6 Citations (Scopus)


We consider a single-machine due window assignment and scheduling problem with batch deliveries, where all jobs have a common due window, and the start time and size of the due window are decision variables. Finished jobs are delivered in batches with unlimited batch capacity. The objective is to determine the due window, a job sequence, and the delivery times, so as to minimize the total cost which comprises earliness of delivery, job holding, start time of due window, size of due window, number of delivery batches, and tardiness penalty. We consider three different variants of the problem corresponding to different measurements of tardiness penalty. We present polynomial-time solution procedures for these variants with significantly lower computational complexities than those of known algorithms in the literature.
Original languageEnglish
Pages (from-to)30-39
Number of pages10
JournalTheoretical Computer Science
Issue numberC
Publication statusPublished - 1 Jan 2015


  • Batch delivery
  • Computational complexity
  • Due window
  • Scheduling

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this