Single-machine batch delivery scheduling with an assignable common due date and controllable processing times

Yunqiang Yin, Edwin Tai Chiu Cheng, Shuenn Ren Cheng, Chin Chia Wu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

27 Citations (Scopus)

Abstract

We consider single-machine batch delivery scheduling with an assignable common due date and controllable processing times, which vary as a convex function of the amounts of a continuously divisible common resource allocated to individual jobs. Finished jobs are delivered in batches and there is no capacity limit on each delivery batch. We first provide an O(n5) dynamic programming algorithm to find the optimal job sequence, the partition of the job sequence into batches, the assigned common due date, and the resource allocation that minimize a cost function based on earliness, tardiness, job holding, due date assignment, batch delivery, and resource consumption. We show that a special case of the problem can be solved by a lower-order polynomial algorithm. We then study the problem of finding the optimal solution to minimize the total cost of earliness, tardiness, job holding, and due date assignment, subject to limited resource availability, and develop an O(nlog n) algorithm to solve it.
Original languageEnglish
Pages (from-to)652-662
Number of pages11
JournalComputers and Industrial Engineering
Volume65
Issue number4
DOIs
Publication statusPublished - 28 Jun 2013

Keywords

  • Batch delivery
  • Common due date
  • Resource allocation
  • Scheduling

ASJC Scopus subject areas

  • Computer Science(all)
  • Engineering(all)

Cite this