A parallel-machine scheduling problem with an antithetical property to maximize total weighted early work

Yunhong Min; Byung Cheon Choi; Myoung Ju Park; Kyung Min Kim

doi:10.1007/s10288-022-00517-1

A parallel-machine scheduling problem with an antithetical property to maximize total weighted early work

Yunhong Min, Byung Cheon Choi, Myoung Ju Park, Kyung Min Kim

Research output: Contribution to journal › Article › peer-review

Abstract

In scheduling with early work, jobs are assigned to a machine by maximizing the parts of non-preemptive jobs executed before their due dates. This paper considers a weighted early work maximization problem on parallel, identical machines with an antithetical property, which holds that w_i≤ w_j implies d_i≥ d_j for any two jobs i and j where w_j and d_j are weight and due date of job j, respectively. We show that the problem is weakly NP-hard. Due to the high complexity of dynamic programming, we develop three solution approaches: mixed-integer programming, heuristics, and a branch-and-bound algorithm. Through numerical experiments, we verify their performance.

Original language	English
Journal	4OR
DOIs	https://doi.org/10.1007/s10288-022-00517-1
Publication status	Accepted/In press - 2022

Keywords

Branch and bound
Computational complexity
Early work
Scheduling

Access to Document

10.1007/s10288-022-00517-1

Cite this

@article{4423b93f12044af8ba1f6f353de347fa,

title = "A parallel-machine scheduling problem with an antithetical property to maximize total weighted early work",

abstract = "In scheduling with early work, jobs are assigned to a machine by maximizing the parts of non-preemptive jobs executed before their due dates. This paper considers a weighted early work maximization problem on parallel, identical machines with an antithetical property, which holds that wi≤ wj implies di≥ dj for any two jobs i and j where wj and dj are weight and due date of job j, respectively. We show that the problem is weakly NP-hard. Due to the high complexity of dynamic programming, we develop three solution approaches: mixed-integer programming, heuristics, and a branch-and-bound algorithm. Through numerical experiments, we verify their performance.",

keywords = "Branch and bound, Computational complexity, Early work, Scheduling",

author = "Yunhong Min and Choi, {Byung Cheon} and Park, {Myoung Ju} and Kim, {Kyung Min}",

note = "Funding Information: The corresponding author{\textquoteright}s work was supported by the Basic Science Research Program (2019R1G1A1085191) through the National Research Foundation of Korea (NRF). Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature.",

year = "2022",

doi = "10.1007/s10288-022-00517-1",

language = "English",

journal = "4OR",

issn = "1619-4500",

publisher = "Springer Verlag",

}

TY - JOUR

T1 - A parallel-machine scheduling problem with an antithetical property to maximize total weighted early work

AU - Min, Yunhong

AU - Choi, Byung Cheon

AU - Park, Myoung Ju

AU - Kim, Kyung Min

N1 - Funding Information: The corresponding author’s work was supported by the Basic Science Research Program (2019R1G1A1085191) through the National Research Foundation of Korea (NRF). Publisher Copyright: © 2022, The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature.

PY - 2022

Y1 - 2022

N2 - In scheduling with early work, jobs are assigned to a machine by maximizing the parts of non-preemptive jobs executed before their due dates. This paper considers a weighted early work maximization problem on parallel, identical machines with an antithetical property, which holds that wi≤ wj implies di≥ dj for any two jobs i and j where wj and dj are weight and due date of job j, respectively. We show that the problem is weakly NP-hard. Due to the high complexity of dynamic programming, we develop three solution approaches: mixed-integer programming, heuristics, and a branch-and-bound algorithm. Through numerical experiments, we verify their performance.

AB - In scheduling with early work, jobs are assigned to a machine by maximizing the parts of non-preemptive jobs executed before their due dates. This paper considers a weighted early work maximization problem on parallel, identical machines with an antithetical property, which holds that wi≤ wj implies di≥ dj for any two jobs i and j where wj and dj are weight and due date of job j, respectively. We show that the problem is weakly NP-hard. Due to the high complexity of dynamic programming, we develop three solution approaches: mixed-integer programming, heuristics, and a branch-and-bound algorithm. Through numerical experiments, we verify their performance.

KW - Branch and bound

KW - Computational complexity

KW - Early work

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=85132149259&partnerID=8YFLogxK

U2 - 10.1007/s10288-022-00517-1

DO - 10.1007/s10288-022-00517-1

M3 - Article

AN - SCOPUS:85132149259

SN - 1619-4500

JO - 4OR

JF - 4OR

ER -

A parallel-machine scheduling problem with an antithetical property to maximize total weighted early work

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this