Minimizing the weighted number of tardy jobs on a two-machine flow shop

R. L. Bulfin; Rym M'Hallah

doi:10.1016/S0305-0548(02)00114-4

Minimizing the weighted number of tardy jobs on a two-machine flow shop

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

^*Corresponding author for this work

Engineering

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

39 Citations (Scopus)

Abstract

In this paper, we describe an exact algorithm to solve the weighted number of tardy jobs two-machine flow shop scheduling problem. The algorithm uses branch-and-bound; a surrogate relaxation resulting in a multiple-choice knapsack provides the bounds. Extensive computational experiments indicate problems with 100 jobs can be solved quickly. Scope and purpose In many industrial sectors, satisfying due dates is a critical issue. Thus, lateness-related measures such as the (weighted) number of tardy jobs are relevant performance measures of schedules in these industries. Our paper studies the weighted number of tardy jobs two-machine flow shop problem, and proposes an exact algorithm that solves large problems.

Original language	English
Pages (from-to)	1887-1900
Number of pages	14
Journal	COMPUTERS AND OPERATIONS RESEARCH
Volume	30
Issue number	12
DOIs	https://doi.org/10.1016/S0305-0548(02)00114-4
Publication status	Published - Oct 2003

Keywords

Branch-and-bound
Combinatorial optimization
Scheduling
Surrogate relaxation

Access to Document

10.1016/S0305-0548(02)00114-4

Cite this

@article{b5ada53b9fd54d7aa44fb753278e1aed,

title = "Minimizing the weighted number of tardy jobs on a two-machine flow shop",

abstract = "In this paper, we describe an exact algorithm to solve the weighted number of tardy jobs two-machine flow shop scheduling problem. The algorithm uses branch-and-bound; a surrogate relaxation resulting in a multiple-choice knapsack provides the bounds. Extensive computational experiments indicate problems with 100 jobs can be solved quickly. Scope and purpose In many industrial sectors, satisfying due dates is a critical issue. Thus, lateness-related measures such as the (weighted) number of tardy jobs are relevant performance measures of schedules in these industries. Our paper studies the weighted number of tardy jobs two-machine flow shop problem, and proposes an exact algorithm that solves large problems.",

keywords = "Branch-and-bound, Combinatorial optimization, Scheduling, Surrogate relaxation",

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

year = "2003",

month = oct,

doi = "10.1016/S0305-0548(02)00114-4",

language = "English",

volume = "30",

pages = "1887--1900",

journal = "COMPUTERS AND OPERATIONS RESEARCH",

issn = "0305-0548",

publisher = "Elsevier Limited",

number = "12",

}

TY - JOUR

T1 - Minimizing the weighted number of tardy jobs on a two-machine flow shop

AU - Bulfin, R. L.

AU - M'Hallah, Rym

PY - 2003/10

Y1 - 2003/10

N2 - In this paper, we describe an exact algorithm to solve the weighted number of tardy jobs two-machine flow shop scheduling problem. The algorithm uses branch-and-bound; a surrogate relaxation resulting in a multiple-choice knapsack provides the bounds. Extensive computational experiments indicate problems with 100 jobs can be solved quickly. Scope and purpose In many industrial sectors, satisfying due dates is a critical issue. Thus, lateness-related measures such as the (weighted) number of tardy jobs are relevant performance measures of schedules in these industries. Our paper studies the weighted number of tardy jobs two-machine flow shop problem, and proposes an exact algorithm that solves large problems.

AB - In this paper, we describe an exact algorithm to solve the weighted number of tardy jobs two-machine flow shop scheduling problem. The algorithm uses branch-and-bound; a surrogate relaxation resulting in a multiple-choice knapsack provides the bounds. Extensive computational experiments indicate problems with 100 jobs can be solved quickly. Scope and purpose In many industrial sectors, satisfying due dates is a critical issue. Thus, lateness-related measures such as the (weighted) number of tardy jobs are relevant performance measures of schedules in these industries. Our paper studies the weighted number of tardy jobs two-machine flow shop problem, and proposes an exact algorithm that solves large problems.

KW - Branch-and-bound

KW - Combinatorial optimization

KW - Scheduling

KW - Surrogate relaxation

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

U2 - 10.1016/S0305-0548(02)00114-4

DO - 10.1016/S0305-0548(02)00114-4

M3 - Article

AN - SCOPUS:0041810535

SN - 0305-0548

VL - 30

SP - 1887

EP - 1900

JO - COMPUTERS AND OPERATIONS RESEARCH

JF - COMPUTERS AND OPERATIONS RESEARCH

IS - 12

ER -

Minimizing the weighted number of tardy jobs on a two-machine flow shop

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this