Operations Research Transactions ›› 2022, Vol. 26 ›› Issue (3): 151-156.doi: 10.15960/j.cnki.issn.1007-6093.2022.03.012

Previous Articles    

LPT heuristic for parallel-machine scheduling of maximizing total early work

Ping ZHOU1, Min JI2, Yiwei JIANG2,*()   

  1. 1. College of Humanities, Zhejiang Business College, Hangzhou 310053, Zhejiang, China
    2. School of Management and E-Business, Zhejiang Gongshang University, Hangzhou 310018, Zhejiang, China
  • Received:2022-01-20 Online:2022-09-15 Published:2022-09-07
  • Contact: Yiwei JIANG E-mail:jywzju@163.com

Abstract:

This paper considers the problem of scheduling on three identical machines with a common due date. The preemption is not allowed. The goal is to maximize the total early work of all the jobs, i.e., the total processing time of all the jobs (or part) completed before the common due date. Since the problem is NP-hard, we apply the classical heuristic, namely longest processing time (LPT), to tackle the problem. We show that the worst-case ratio of LPT is at most $\frac{15}{13}$ and the lower bound of the worst-case ratio is at least $\frac{27}{25}$ by providing an instance.

Key words: parallel-machine scheduling, LPT heuristic, worst-case ratio, total early work

CLC Number: