中文

Operations Research Transactions >

2022 , Vol. 26 >Issue 3: 151 - 156

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2022.03.012

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

Expand
  • 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 date: 2022-01-20

  Online published: 2022-09-07

Fold

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

Cite this article

Ping ZHOU, Min JI, Yiwei JIANG . LPT heuristic for parallel-machine scheduling of maximizing total early work[J]. Operations Research Transactions, 2022 , 26(3) : 151 -156 . DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.012

References

1 Sterna M , Czerniachowska K . Polynomial time approximation scheme for two parallel machines scheduling with a common due date to maximize early work[J]. Journal of Optimization Theory and Applications, 2017, 174 (3): 927- 944.
2 Sterna M . A survey of scheduling problems with late work criteria[J]. Omega, 2011, 39 (2): 120- 129.
3 Sterna M . Late and early work scheduling: A survey[J]. Omega, 2021, 104, 102453.
4 Wu C , Yin Y , Wu W , et al. Using a branch and bound and a genetic algorithm for a single machine total late work scheduling problem[J]. Soft Computing, 2016, 20 (4): 1329- 1339.
5 Zhang X G , Wang Y . Two-agent scheduling problems on a single-machine to minimize the total weighted late work[J]. Journal of Combinatorial Optimization, 2017, 33 (3): 945- 955.
6 Wang D J , Kang C C , Shiau Y R , et al. A two-agent single machine scheduling problem with late work criteria[J]. Soft Computing, 2017, 21 (8): 2015- 2033.
7 Potts C N , Van Wassenhove L N . Single machine scheduling to minimize total late work[J]. Operations Research, 1992, 40 (3): 586- 595.
8 Potts C N , Van Wassenhove L N . Approximation algorithms for scheduling a single machine to minimize total late work[J]. Operations Research Letters, 1992, 11 (5): 261- 266.
9 Chen X , Sterna M , Han X , et al. Scheduling on parallel identical machines with late work criterion: Offline and online cases[J]. Journal of Scheduling, 2016, 19 (6): 729- 736.
10 Chen X , Liang Y , Sterna M , et al. Fully polynomial time approximation scheme to maximize early work on parallel machines with common due date[J]. European Journal of Operational Research, 2020, 284 (1): 67- 74.
11 Chen X , Wang W , Xie P , et al. Exact and heuristic algorithms for scheduling on two identical machines with early work maximization[J]. Computers & Industrial Engineering, 2020, 144, 106449.
12 Jiang Y , Guan L , Zhang K , et al. A note on scheduling on two identical machines with early work maximization[J]. Computers & Industrial Engineering, 2021, 153, 107091.
Options
Outlines

/

〈 〉