Approximation algorithms for common due date assignment and job scheduling on parallel machines

Wen Qiang Xiao; Chung Lun Li

doi:10.1023/A:1013567219570

Approximation algorithms for common due date assignment and job scheduling on parallel machines

Wen Qiang Xiao, Chung Lun Li

Research output: Journal article publication › Journal article › Academic research › peer-review

6 Citations (Scopus)

Abstract

We consider the problem of assigning a common due date to a set of jobs and scheduling the jobs on a set of parallel machines so that the weighted sum of the due date, total earliness, and total tardiness is minimized. A heuristic is developed to solve this problem, and an absolute performance ratio is provided for this heuristic. Another heuristic with a better worst-case performance bound is presented for the case with a zero earliness penalty. A fully polynomial approximation scheme is also developed.

Original language	English
Pages (from-to)	467-477
Number of pages	11
Journal	IIE Transactions (Institute of Industrial Engineers)
Volume	34
Issue number	5
DOIs	https://doi.org/10.1023/A:1013567219570 https://doi.org/10.1080/07408170208928883
Publication status	Published - 1 May 2002
Externally published	Yes

ASJC Scopus subject areas

Industrial and Manufacturing Engineering

More information

Cite this

@article{898fa529a8b1489b96631877a1447851,

title = "Approximation algorithms for common due date assignment and job scheduling on parallel machines",

abstract = "We consider the problem of assigning a common due date to a set of jobs and scheduling the jobs on a set of parallel machines so that the weighted sum of the due date, total earliness, and total tardiness is minimized. A heuristic is developed to solve this problem, and an absolute performance ratio is provided for this heuristic. Another heuristic with a better worst-case performance bound is presented for the case with a zero earliness penalty. A fully polynomial approximation scheme is also developed.",

author = "Xiao, {Wen Qiang} and Li, {Chung Lun}",

year = "2002",

month = may,

day = "1",

doi = "10.1023/A:1013567219570",

language = "English",

volume = "34",

pages = "467--477",

journal = "IIE Transactions (Institute of Industrial Engineers)",

issn = "0740-817X",

publisher = "Taylor and Francis Ltd.",

number = "5",

}

TY - JOUR

T1 - Approximation algorithms for common due date assignment and job scheduling on parallel machines

AU - Xiao, Wen Qiang

AU - Li, Chung Lun

PY - 2002/5/1

Y1 - 2002/5/1

N2 - We consider the problem of assigning a common due date to a set of jobs and scheduling the jobs on a set of parallel machines so that the weighted sum of the due date, total earliness, and total tardiness is minimized. A heuristic is developed to solve this problem, and an absolute performance ratio is provided for this heuristic. Another heuristic with a better worst-case performance bound is presented for the case with a zero earliness penalty. A fully polynomial approximation scheme is also developed.

AB - We consider the problem of assigning a common due date to a set of jobs and scheduling the jobs on a set of parallel machines so that the weighted sum of the due date, total earliness, and total tardiness is minimized. A heuristic is developed to solve this problem, and an absolute performance ratio is provided for this heuristic. Another heuristic with a better worst-case performance bound is presented for the case with a zero earliness penalty. A fully polynomial approximation scheme is also developed.

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

U2 - 10.1023/A:1013567219570

DO - 10.1023/A:1013567219570

M3 - Journal article

SN - 0740-817X

VL - 34

SP - 467

EP - 477

JO - IIE Transactions (Institute of Industrial Engineers)

JF - IIE Transactions (Institute of Industrial Engineers)

IS - 5

ER -

Approximation algorithms for common due date assignment and job scheduling on parallel machines

Abstract

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this