Minimizing the weighted number of tardy jobs on a single machine

Rym M'Hallah; R. L. Bulfin

doi:10.1016/S0377-2217(02)00180-7

Minimizing the weighted number of tardy jobs on a single machine

Rym M'Hallah, R. L. Bulfin^*

^*Corresponding author for this work

Engineering

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

24 Citations (Scopus)

Abstract

In this paper, we describe an exact algorithm to solve the single machine weighted number of tardy jobs scheduling problem. The algorithm uses branch-and-bound with the bounds obtained from a surrogate knapsack. Extensive computational experiments are carried out. These experiments validate previous work on what constitutes a difficult instance and show that even difficult instances with 2500 jobs can be solved optimally in a reasonable amount of time.

Original language	English
Pages (from-to)	45-56
Number of pages	12
Journal	EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume	145
Issue number	1
DOIs	https://doi.org/10.1016/S0377-2217(02)00180-7
Publication status	Published - 16 Feb 2003

Keywords

Combinatorial optimization
Scheduling

Access to Document

10.1016/S0377-2217(02)00180-7

Cite this

@article{ff92d29eb2864359b5ca2b57d3f4598b,

title = "Minimizing the weighted number of tardy jobs on a single machine",

abstract = "In this paper, we describe an exact algorithm to solve the single machine weighted number of tardy jobs scheduling problem. The algorithm uses branch-and-bound with the bounds obtained from a surrogate knapsack. Extensive computational experiments are carried out. These experiments validate previous work on what constitutes a difficult instance and show that even difficult instances with 2500 jobs can be solved optimally in a reasonable amount of time.",

keywords = "Combinatorial optimization, Scheduling",

author = "Rym M'Hallah and Bulfin, {R. L.}",

note = "Funding Information: We would like to thank the referees for their helpful comments on this paper. Parts of this work were supported by grants from the NSF International Collaborative Research Division and from the NSF Division of Design, Manufacture & Industrial Innovation. Copyright: Copyright 2004 Elsevier Science B.V., Amsterdam. All rights reserved.",

year = "2003",

month = feb,

day = "16",

doi = "10.1016/S0377-2217(02)00180-7",

language = "English",

volume = "145",

pages = "45--56",

journal = "EUROPEAN JOURNAL OF OPERATIONAL RESEARCH",

issn = "0377-2217",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - Minimizing the weighted number of tardy jobs on a single machine

AU - M'Hallah, Rym

AU - Bulfin, R. L.

N1 - Funding Information: We would like to thank the referees for their helpful comments on this paper. Parts of this work were supported by grants from the NSF International Collaborative Research Division and from the NSF Division of Design, Manufacture & Industrial Innovation. Copyright: Copyright 2004 Elsevier Science B.V., Amsterdam. All rights reserved.

PY - 2003/2/16

Y1 - 2003/2/16

N2 - In this paper, we describe an exact algorithm to solve the single machine weighted number of tardy jobs scheduling problem. The algorithm uses branch-and-bound with the bounds obtained from a surrogate knapsack. Extensive computational experiments are carried out. These experiments validate previous work on what constitutes a difficult instance and show that even difficult instances with 2500 jobs can be solved optimally in a reasonable amount of time.

AB - In this paper, we describe an exact algorithm to solve the single machine weighted number of tardy jobs scheduling problem. The algorithm uses branch-and-bound with the bounds obtained from a surrogate knapsack. Extensive computational experiments are carried out. These experiments validate previous work on what constitutes a difficult instance and show that even difficult instances with 2500 jobs can be solved optimally in a reasonable amount of time.

KW - Combinatorial optimization

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=0037448772&partnerID=8YFLogxK

U2 - 10.1016/S0377-2217(02)00180-7

DO - 10.1016/S0377-2217(02)00180-7

M3 - Article

AN - SCOPUS:0037448772

SN - 0377-2217

VL - 145

SP - 45

EP - 56

JO - EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

JF - EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

IS - 1

ER -

Minimizing the weighted number of tardy jobs on a single machine

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this