Scheduling of Jobs with Multiple Weights on a Single Machine for Minimizing the Total Weighted Number of Tardy Jobs

Shuen Guo (), Hao Lang and Hanxiang Zhang
Additional contact information
Shuen Guo: School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China
Hao Lang: Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hong Kong SAR, China
Hanxiang Zhang: Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hong Kong SAR, China

Mathematics, 2023, vol. 11, issue 4, 1-19

Abstract: We consider the scheduling of jobs with multiple weights on a single machine for minimizing the total weighted number of tardy jobs. In this setting, each job has m weights (or equivalently, the jobs have m weighting vectors), and thus we have m criteria, each of which is to minimize the total weighted number of tardy jobs under a corresponding weighting vector of the jobs. For this scheduling model, the feasibility problem aims to find a feasible schedule such that each criterion is upper bounded by its threshold value, and the Pareto scheduling problem aims to find all the Pareto-optimal points and for each one a corresponding Pareto-optimal schedule. Although the two problems have not been studied before, it is implied in the literature that both of them are unary NP-hard when m is an arbitrary number. We show in this paper that, in the case where m is a fixed number, the two problems are solvable in pseudo-polynomial time, the feasibility problem admits a dual-fully polynomial-time approximation scheme, and the Pareto-scheduling problem admits a fully polynomial-time approximation scheme.

Keywords: scheduling; pareto-optimal points; multi-weights; tardy jobs (search for similar items in EconPapers)
JEL-codes: C (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)
https://www.mdpi.com/2227-7390/11/4/1013/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/4/1013/ (text/html)

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:gam:jmathe:v:11:y:2023:i:4:p:1013-:d:1070715

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().