Dynamic programming approach to the single-machine sequencing problem with different due-dates

Research output: Journal article publicationJournal articleAcademic researchpeer-review

2 Citations (Scopus)


Given a set of n jobs each of which is assigned a due-date and all jobs are simultaneously available to be processed on a single machine, the problem is to find the optimal job processing order that minimizes the sum of absolute deviation of job completion times about their respective due-dates. Since this problem has been shown to be NP-complete, we present a DP (dynamic programming) formulation of the problem and apply the principle of optimality of DP to find the optimal solution by implicit enumeration.
Original languageEnglish
Pages (from-to)1-7
Number of pages7
JournalComputers and Mathematics with Applications
Issue number2
Publication statusPublished - 1 Jan 1990
Externally publishedYes

ASJC Scopus subject areas

  • Modelling and Simulation
  • Computational Theory and Mathematics
  • Computational Mathematics

Cite this