Minimization of maximum lateness under linear deterioration

Y. S. Hsu, Bertrand M.T. Lin*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

32 Scopus citations


This paper considers a single-machine scheduling problem to minimize the maximum lateness. The processing time of each job is a linear function of the time when the job starts processing. This problem is known to be NP-hard in the literature. In this paper, we design a branch-and-bound algorithm for deriving exact solutions by incorporating several properties concerning dominance relations and lower bounds. These properties produce synergic effects in accelerating the solution finding process such that the algorithm can solve problems of 100 jobs within 1 min on average. To compose approximate solutions, we revise a heuristic algorithm available in the literature and propose several hybrid variants. Numerical results evince that the proposed approaches are very effective in successfully reporting optimal solutions for most of the test cases.

Original languageEnglish
Pages (from-to)459-469
Number of pages11
Issue number6
StatePublished - 1 Dec 2003


  • Branch-and-bound algorithm
  • Heuristic algorithm
  • Linear deterioration
  • Maximum lateness
  • Operations scheduling

Fingerprint Dive into the research topics of 'Minimization of maximum lateness under linear deterioration'. Together they form a unique fingerprint.

Cite this