Bi-criteria scheduling problems: Number of tardy jobs and maximum weighted tardiness

Yumei Huo; Joseph Y.T. Leung; Hairong Zhao

doi:10.1016/j.ejor.2005.06.067

Bi-criteria scheduling problems: Number of tardy jobs and maximum weighted tardiness

Yumei Huo, Joseph Y.T. Leung, Hairong Zhao

Computer Science

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

26 Scopus citations

Abstract

Consider a single machine and a set of n jobs that are available for processing at time 0. Job j has a processing time p_j, a due date d_j and a weight w_j. 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.

Original language	English (US)
Pages (from-to)	116-134
Number of pages	19
Journal	European Journal of Operational Research
Volume	177
Issue number	1
DOIs	https://doi.org/10.1016/j.ejor.2005.06.067
State	Published - Feb 16 2007

All Science Journal Classification (ASJC) codes

General Computer Science
Modeling and Simulation
Management Science and Operations Research
Information Systems and Management

Keywords

Heuristics
Maximum weighted tardiness
NP-hard
Number of tardy jobs
Scheduling

Access to Document

10.1016/j.ejor.2005.06.067

Cite this

@article{ae1f5a4129a94fa6ae3a8cfd13d20d9c,

title = "Bi-criteria scheduling problems: Number of tardy jobs and maximum weighted tardiness",

abstract = "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.",

keywords = "Heuristics, Maximum weighted tardiness, NP-hard, Number of tardy jobs, Scheduling",

author = "Yumei Huo and Leung, {Joseph Y.T.} and Hairong Zhao",

note = "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. ",

year = "2007",

month = feb,

day = "16",

doi = "10.1016/j.ejor.2005.06.067",

language = "English (US)",

volume = "177",

pages = "116--134",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier B.V.",

number = "1",

}

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 -

Bi-criteria scheduling problems: Number of tardy jobs and maximum weighted tardiness

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this