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

Yunhong Min (), Byung-Cheon Choi (), Myoung-Ju Park () and Kyung Min Kim ()
Additional contact information
Yunhong Min: Incheon National University
Byung-Cheon Choi: Chungnam National University
Myoung-Ju Park: Kyung Hee University
Kyung Min Kim: Myongji University

4OR, 2023, vol. 21, issue 3, No 3, 437 pages

Abstract: 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 \le w_j$$ w i ≤ w j implies $$d_i \ge d_j$$ d i ≥ d j for any two jobs i and j where $$w_j$$ w j and $$d_j$$ 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.

Keywords: Scheduling; Early work; Computational complexity; Branch and bound; 90B35; 68Q25; 90C57 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10288-022-00517-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:aqjoor:v:21:y:2023:i:3:d:10.1007_s10288-022-00517-1

Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE

DOI: 10.1007/s10288-022-00517-1

Access Statistics for this article

4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello

More articles in 4OR from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().