A note on scheduling on two identical machines with early work maximization. (March 2021) - Jiang, Yiwei; Guan, Lijun; Zhang, Kun; Liu, Chang; Cheng, T.C.E.; Ji, Min
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.