An \(O(n \log^ 2\,n)\) algorithm for the maximum weighted tardiness problem

DOI10.1016/0020-0190(89)90126-9zbMath0672.68011OpenAlexW1967164367MaRDI QIDQ1120271

Dorit S. Hochbaum, Ron Shamir

Publication date: 1989

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

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90126-9

zbMATH Keywords

analysis of algorithmsdata structuressequential processing

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) Data structures (68P05) Algorithms in computer science (68W99)

Related Items (9)

A note: minmax due-date assignment problem with lead-time cost ⋮ Scheduling identical jobs on uniform parallel machines ⋮ Lawler's minmax cost problem under uncertainty ⋮ Minimizing maximum cost for a single machine under uncertainty of processing times ⋮ A faster algorithm for the maximum weighted tardiness problem ⋮ Minimizing functions of infeasibilities in a two-machine flow shop ⋮ Applications of a semi-dynamic convex hull algorithm ⋮ Applications of a semi-dynamic convex hull algorithm ⋮ Improved polynomial algorithms for robust bottleneck problems with interval data

Cites Work

• Maintenance of configurations in the plane
• On general routing problems
• Optimal Sequencing of a Single Machine Subject to Precedence Constraints
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An \(O(n \log^ 2\,n)\) algorithm for the maximum weighted tardiness problem