Scheduling to maximize the weighted number of on-time jobs on parallel machines with bounded job-rejection

Matan Atsmony () and Gur Mosheiov
Additional contact information
Matan Atsmony: The Hebrew University
Gur Mosheiov: The Hebrew University

Journal of Scheduling, 2023, vol. 26, issue 2, No 5, 193-207

Abstract: Abstract We study a scheduling problem on parallel identical machines, where the objective function is maximizing the weighted number of jobs completed exactly at their due-dates. The scheduler may reject a subset of the jobs, and the total permitted rejection cost is assumed to be bounded. Thus, when a decision has to be made regarding a certain job, the following options need to be considered: either ( $$\mathrm{i}$$ i ) identify the set of machines on which the job can be scheduled on time, and assign the job to one of these machines, or ( $$\mathrm{ii}$$ ii ) reject the job (if possible), or ( $$\mathrm{iii}$$ iii ) delay the job. A pseudo-polynomial dynamic programming algorithm is introduced for this NP-hard problem. Medium size problems are solved in reasonable running times. We then study a different version of the problem, in which job-dependent due-windows are considered, and the job processing times are assumed to be identical. This version is proved to be NP-hard, and a pseudo-polynomial dynamic programming algorithm is introduced as well. Our numerical study indicates that medium size instances can be handled for this version. In addition, for both problems, an alternative solution procedure based on integer-linear-programming formulation is introduced.

Keywords: Scheduling; Parallel identical machines; Just-in-time; Job-rejection; Dynamic programming (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-022-00745-7 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:jsched:v:26:y:2023:i:2:d:10.1007_s10951-022-00745-7

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-022-00745-7

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

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