A faster algorithm for the maximum weighted tardiness problem

DOI10.1016/0020-0190(90)90184-YMaRDI QIDQ916393zbMATH OpenOpenAlexFDO

Authors Malcolm C. Fields, Greg N. Frederickson

Publication date 1990

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(90)90184-y

zbMATH Keywords

analysis of algorithmsconvex hulljob schedulingmaximum weighted tardiness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• An \(O(n \log^ 2\,n)\) algorithm for the maximum weighted tardiness problem
• A branch and bound algorithm to minimize total weighted tardiness on a single processor
• Minimizing the weighted number of tardy task units
• Single machine scheduling to minimize weighted earliness subject to maximum tardiness
• Minimizing the number of tardy job units under release time constraints

Cites work

• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• An \(O(n \log^ 2\,n)\) algorithm for the maximum weighted tardiness problem
• Maintenance of configurations in the plane
• On the convex layers of a planar set
• Optimal Sequencing of a Single Machine Subject to Precedence Constraints

Cited in

(6)

• A note on reverse scheduling with maximum lateness objective
• Minimizing functions of infeasibilities in a two-machine flow shop
• Applications of a semi-dynamic convex hull algorithm
• Minimizing the weighted number of tardy task units
• An \(O(n \log^ 2\,n)\) algorithm for the maximum weighted tardiness problem
• Applications of a semi-dynamic convex hull algorithm

This page was built for publication: A faster algorithm for the maximum weighted tardiness problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q916393)