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

doi:10.1016/j.cie.2020.107091

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 publication › Journal article › Academic research › peer-review

11 Citations (Scopus)

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 language	English
Article number	107091
Journal	Computers and Industrial Engineering
Volume	153
DOIs	https://doi.org/10.1016/j.cie.2020.107091
Publication status	Published - Mar 2021

Keywords

Early work maximization
Identical machine scheduling
LPT
Worst-case ratio

ASJC Scopus subject areas

General Computer Science
General Engineering

More information

10.1016/j.cie.2020.107091

Cite this

@article{f3638e74b1124412922bea8b7e994f4f,

title = "A note on scheduling on two identical machines with early work maximization",

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.",

keywords = "Early work maximization, Identical machine scheduling, LPT, Worst-case ratio",

author = "Yiwei Jiang and Lijun Guan and Kun Zhang and Chang Liu and Cheng, \{T. C.E.\} and Min Ji",

note = "Funding Information: We are thankful to three anonymous referees for their helpful comments and suggestions on an earlier version of our paper. This research was supported in part by the National Natural Science Foundation of China under grant numbers 11971434 and 11871327, Zhejiang Provincial Natural Science Foundation of China under grant number LY21G010002, and the Contemporary Business and Trade Research Center of Zhejiang Gongshang University, which is a key Research Institute of Social Sciences and Humanities of the Ministry of Education of China. Cheng was supported in part by The Hong Kong Polytechnic University under the Fung Yiu King - Wing Hang Bank Endowed Professorship in Business Administration. Publisher Copyright: {\textcopyright} 2020 Elsevier Ltd Copyright: Copyright 2021 Elsevier B.V., All rights reserved.",

year = "2021",

month = mar,

doi = "10.1016/j.cie.2020.107091",

language = "English",

volume = "153",

journal = "Computers and Industrial Engineering",

issn = "0360-8352",

publisher = "Elsevier Ltd",

}

TY - JOUR

T1 - A note on scheduling on two identical machines with early work maximization

AU - Jiang, Yiwei

AU - Guan, Lijun

AU - Zhang, Kun

AU - Liu, Chang

AU - Cheng, T. C.E.

AU - Ji, Min

N1 - Funding Information: We are thankful to three anonymous referees for their helpful comments and suggestions on an earlier version of our paper. This research was supported in part by the National Natural Science Foundation of China under grant numbers 11971434 and 11871327, Zhejiang Provincial Natural Science Foundation of China under grant number LY21G010002, and the Contemporary Business and Trade Research Center of Zhejiang Gongshang University, which is a key Research Institute of Social Sciences and Humanities of the Ministry of Education of China. Cheng was supported in part by The Hong Kong Polytechnic University under the Fung Yiu King - Wing Hang Bank Endowed Professorship in Business Administration. Publisher Copyright: © 2020 Elsevier Ltd Copyright: Copyright 2021 Elsevier B.V., All rights reserved.

PY - 2021/3

Y1 - 2021/3

N2 - 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.

AB - 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.

KW - Early work maximization

KW - Identical machine scheduling

KW - LPT

KW - Worst-case ratio

UR - https://www.scopus.com/pages/publications/85099179448

U2 - 10.1016/j.cie.2020.107091

DO - 10.1016/j.cie.2020.107091

M3 - Journal article

AN - SCOPUS:85099179448

SN - 0360-8352

VL - 153

JO - Computers and Industrial Engineering

JF - Computers and Industrial Engineering

M1 - 107091

ER -

A note on scheduling on two identical machines with early work maximization

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this