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^*

^*Corresponding author for this work

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › 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. © 2002 "IIE".

Original language	English
Pages (from-to)	467-477
Journal	IIE Transactions
Volume	34
Issue number	5
DOIs	https://doi.org/10.1023/A:1013567219570
Publication status	Published - May 2002
Externally published	Yes

Bibliographical note

This has also been published in: XIAO, W.-Q., & LI, C.-L. (2002). Approximation algorithms for common due date assignment and job scheduling on parallel machines. IIE Transactions, 34(5), 467-477. https://doi.org/10.1080/07408170208928883

Access Output

10.1023/A:1013567219570

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{d37d1f71e520443aa8462532f90407ee,

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. {\textcopyright} 2002 {"}IIE{"}.",

author = "Wen-Qiang XIAO and Chung-Lun LI",

note = "This has also been published in: XIAO, W.-Q., & LI, C.-L. (2002). Approximation algorithms for common due date assignment and job scheduling on parallel machines. IIE Transactions, 34(5), 467-477. https://doi.org/10.1080/07408170208928883",

year = "2002",

month = may,

doi = "10.1023/A:1013567219570",

language = "English",

volume = "34",

pages = "467--477",

journal = "IIE Transactions",

issn = "0740-817X",

publisher = "Taylor & Francis",

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

N1 - This has also been published in: XIAO, W.-Q., & LI, C.-L. (2002). Approximation algorithms for common due date assignment and job scheduling on parallel machines. IIE Transactions, 34(5), 467-477. https://doi.org/10.1080/07408170208928883

PY - 2002/5

Y1 - 2002/5

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. © 2002 "IIE".

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. © 2002 "IIE".

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

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0036568108&origin=recordpage

U2 - 10.1023/A:1013567219570

DO - 10.1023/A:1013567219570

M3 - RGC 21 - Publication in refereed journal

SN - 0740-817X

VL - 34

SP - 467

EP - 477

JO - IIE Transactions

JF - IIE Transactions

IS - 5

ER -

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

Abstract

Bibliographical note

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

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

Cite this