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

Abstract

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
Volume153
DOIs
Publication statusPublished - Mar 2021

Keywords

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

ASJC Scopus subject areas

  • Computer Science(all)
  • Engineering(all)

Cite this