Minimizing the maximum deviation of job completion time about a common due-date

Research output: Journal article publicationJournal articleAcademic researchpeer-review

15 Citations (Scopus)


Given a set of n jobs with deterministic processing times and the same ready times, the problem is to find the optimal common due-date k*and the optimal job sequences σ*to minimize the maximum deviation of job completion time about the common due-date. It is shown that the problem can be formulated as an equivalent linear programming (LP) minimization problem. Using the strong duality property of LP, we derive the optimal due-date by considering the dual of the LP problem. When the optimal due-date is determined the optimal job sequence is readily available. After the theoretical treatment numerical examples are presented to demonstrate the validity of the theories.
Original languageEnglish
Pages (from-to)279-283
Number of pages5
JournalComputers and Mathematics with Applications
Issue number4
Publication statusPublished - 1 Jan 1987
Externally publishedYes

ASJC Scopus subject areas

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

Cite this