On the fixed interval due-date scheduling problem

Chung Yee Lee, Chung Lun Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

8 Citations (Scopus)

Abstract

We consider the nonpreemptive single machine scheduling problem with multiple due-dates (delivery dates), where the time between two consecutive due-dates is a constant. Given a set of jobs, we are interested in scheduling the jobs such that the sum of the total due-date cost and the total earliness cost is minimized with the constraint that each job must be finished at or before its due-date. We show that this problem is strongly NP-hard in general. We then analyze the problem where the number of due-dates is bounded by a given constant. We describe a pseudo-polynomial dynamic programming algorithm for this restricted problem. A heuristic is also provided and worst-case analysis is performed. An efficient algorithm is developed to solve the special case where all the job processing times are identical.
Original languageEnglish
Pages (from-to)101-117
Number of pages17
JournalDiscrete Applied Mathematics
Volume68
Issue number1-2
DOIs
Publication statusPublished - 12 Jun 1996
Externally publishedYes

Keywords

  • Delivery dates
  • Scheduling
  • Single machine

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Cite this