The parallel machine min‐max weighted absolute lateness scheduling problem

Chung‐Lun Li; T. C.E. Cheng

doi:10.1002/1520-6750(199402)41:1<33::AID-NAV3220410104>3.0.CO;2-S

The parallel machine min‐max weighted absolute lateness scheduling problem

Chung‐Lun Li^*
, T. C.E. Cheng

^*Corresponding author for this work

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

56 Citations (Scopus)

Abstract

Given a set of jobs, a processing time and a weight for each job, several parallel and identical machines, and a common due date that is not too early to constrain the scheduling decision, we want to find an optimal job schedule so as to minimize the maximum weighted absolute lateness. We show that this problem is NP‐complete even for the single‐machine case, and is strongly NP‐complete for the general case. We present a polynomial time heuristic for this problem and analyze its worst‐case performance. Empirical testing of the heuristic is reported, and the results suggest that the performance is asymptotically optimal as the number of jobs tends to infinity. © 1994 John Wiley & Sons, Inc. Copyright © 1994 Wiley Periodicals, Inc., A Wiley Company

Original language	English
Pages (from-to)	33-46
Journal	Naval Research Logistics (NRL)
Volume	41
Issue number	1
DOIs	https://doi.org/10.1002/1520-6750(199402)41:1<33::AID-NAV3220410104>3.0.CO;2-S
Publication status	Published - Feb 1994
Externally published	Yes

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Access Output

10.1002/1520-6750(199402)41:1<33::AID-NAV3220410104>3.0.CO;2-S

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{ad1276eba70c434cb9600245c966dfa4,

title = "The parallel machine min‐max weighted absolute lateness scheduling problem",

abstract = "Given a set of jobs, a processing time and a weight for each job, several parallel and identical machines, and a common due date that is not too early to constrain the scheduling decision, we want to find an optimal job schedule so as to minimize the maximum weighted absolute lateness. We show that this problem is NP‐complete even for the single‐machine case, and is strongly NP‐complete for the general case. We present a polynomial time heuristic for this problem and analyze its worst‐case performance. Empirical testing of the heuristic is reported, and the results suggest that the performance is asymptotically optimal as the number of jobs tends to infinity. {\textcopyright} 1994 John Wiley \& Sons, Inc. Copyright {\textcopyright} 1994 Wiley Periodicals, Inc., A Wiley Company",

author = "Chung‐Lun Li and Cheng, \{T. C.E.\}",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].",

year = "1994",

month = feb,

doi = "10.1002/1520-6750(199402)41:1<33::AID-NAV3220410104>3.0.CO;2-S",

language = "English",

volume = "41",

pages = "33--46",

journal = "Naval Research Logistics (NRL)",

issn = "0894-069X",

publisher = "John Wiley \& Sons",

number = "1",

}

TY - JOUR

T1 - The parallel machine min‐max weighted absolute lateness scheduling problem

AU - Li, Chung‐Lun

AU - Cheng, T. C.E.

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 1994/2

Y1 - 1994/2

N2 - Given a set of jobs, a processing time and a weight for each job, several parallel and identical machines, and a common due date that is not too early to constrain the scheduling decision, we want to find an optimal job schedule so as to minimize the maximum weighted absolute lateness. We show that this problem is NP‐complete even for the single‐machine case, and is strongly NP‐complete for the general case. We present a polynomial time heuristic for this problem and analyze its worst‐case performance. Empirical testing of the heuristic is reported, and the results suggest that the performance is asymptotically optimal as the number of jobs tends to infinity. © 1994 John Wiley & Sons, Inc. Copyright © 1994 Wiley Periodicals, Inc., A Wiley Company

AB - Given a set of jobs, a processing time and a weight for each job, several parallel and identical machines, and a common due date that is not too early to constrain the scheduling decision, we want to find an optimal job schedule so as to minimize the maximum weighted absolute lateness. We show that this problem is NP‐complete even for the single‐machine case, and is strongly NP‐complete for the general case. We present a polynomial time heuristic for this problem and analyze its worst‐case performance. Empirical testing of the heuristic is reported, and the results suggest that the performance is asymptotically optimal as the number of jobs tends to infinity. © 1994 John Wiley & Sons, Inc. Copyright © 1994 Wiley Periodicals, Inc., A Wiley Company

UR - https://www.scopus.com/pages/publications/0028377693

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

U2 - 10.1002/1520-6750(199402)41:1<33::AID-NAV3220410104>3.0.CO;2-S

DO - 10.1002/1520-6750(199402)41:1<33::AID-NAV3220410104>3.0.CO;2-S

M3 - RGC 21 - Publication in refereed journal

SN - 0894-069X

VL - 41

SP - 33

EP - 46

JO - Naval Research Logistics (NRL)

JF - Naval Research Logistics (NRL)

IS - 1

ER -

The parallel machine min‐max weighted absolute lateness scheduling problem

Abstract

Bibliographical note

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this