A note on scheduling on two identical machines with early work maximization

Yiwei Jiang, Lijun Guan, Kun Zhang, Chang Liu, T. C.E. Cheng, Min Ji

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)


This paper considers the problem of scheduling on two identical machines to maximize the total early work with a common due date of all the jobs. Chen et al. (2020) showed that the worst-case ratio of the classical LPT algorithm for the problem is at most 10/9 and provided an instance to show that the bound of LPT is at least 12/11. In this note we show that the tight bound of LPT is exactly 12/11.

Original languageEnglish
Article number107091
JournalComputers and Industrial Engineering
Publication statusPublished - Mar 2021


  • Early work maximization
  • Identical machine scheduling
  • LPT
  • Worst-case ratio

ASJC Scopus subject areas

  • Computer Science(all)
  • Engineering(all)

Cite this