TY - JOUR
T1 - Bi-criteria scheduling problems
T2 - Number of tardy jobs and maximum weighted tardiness
AU - Huo, Yumei
AU - Leung, Joseph Y.T.
AU - Zhao, Hairong
N1 - Funding Information:
The authors gratefully acknowledge the support by the National Science Foundation through grant DMI-0300156. Computing facilities are provided by the PC Cluster Lab of the CS Department at NJIT, which is partially supported by NSF grant NSF-9977508 and partially supported by NJIT SBR grant SBR-421350.
PY - 2007/2/16
Y1 - 2007/2/16
N2 - Consider a single machine and a set of n jobs that are available for processing at time 0. Job j has a processing time pj, a due date dj and a weight wj. We consider bi-criteria scheduling problems involving the maximum weighted tardiness and the number of tardy jobs. We give NP-hardness proofs for the scheduling problems when either one of the two criteria is the primary criterion and the other one is the secondary criterion. These results answer two open questions posed by Lee and Vairaktarakis in 1993. We consider complexity relationships between the various problems, give polynomial-time algorithms for some special cases, and propose fast heuristics for the general case. The effectiveness of the heuristics is measured by empirical study. Our results show that one heuristic performs extremely well compared to optimal solutions.
AB - Consider a single machine and a set of n jobs that are available for processing at time 0. Job j has a processing time pj, a due date dj and a weight wj. We consider bi-criteria scheduling problems involving the maximum weighted tardiness and the number of tardy jobs. We give NP-hardness proofs for the scheduling problems when either one of the two criteria is the primary criterion and the other one is the secondary criterion. These results answer two open questions posed by Lee and Vairaktarakis in 1993. We consider complexity relationships between the various problems, give polynomial-time algorithms for some special cases, and propose fast heuristics for the general case. The effectiveness of the heuristics is measured by empirical study. Our results show that one heuristic performs extremely well compared to optimal solutions.
KW - Heuristics
KW - Maximum weighted tardiness
KW - NP-hard
KW - Number of tardy jobs
KW - Scheduling
UR - http://www.scopus.com/inward/record.url?scp=33750471582&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33750471582&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2005.06.067
DO - 10.1016/j.ejor.2005.06.067
M3 - Article
AN - SCOPUS:33750471582
SN - 0377-2217
VL - 177
SP - 116
EP - 134
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 1
ER -