The parallel machine min‐max weighted absolute lateness scheduling problem

Chung Lun Li, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

55 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)33-46
Number of pages14
JournalNaval Research Logistics (NRL)
Issue number1
Publication statusPublished - 1 Jan 1994

ASJC Scopus subject areas

  • Modelling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research


Dive into the research topics of 'The parallel machine min‐max weighted absolute lateness scheduling problem'. Together they form a unique fingerprint.

Cite this