A note on scheduling on two identical machines with early work maximization. (March 2021)

• Record Type: Journal Article
• Authors: Jiang, Yiwei; Guan, Lijun; Zhang, Kun; Liu, Chang; Cheng, T.C.E.; Ji, Min
• Is Part Of: Computers & industrial engineering. Volume 153(2021)
• Publication Date: 2021-03
• Subjects: Identical machine scheduling -- Early work maximization -- LPT -- Worst-case ratio; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2020.107091
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: We consider scheduling on two identical machines with a common due date. The goal is to maximize the total early work. We show that the tight bound of LPT for the problem is exactly 12/11. We improve the previous bound of 10/9 by Chen et al. (2020). 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.