Maximizing total tardiness on a single machine in O(n^2) time via a reduction to half-product minimization

DOI10.1007/S10479-015-2023-1zbMATH Open1332.90113OpenAlexW2174759551MaRDI QIDQ256707FDOQ256707

Authors: Sergey Kovalev 

Publication date: 9 March 2016

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-015-2023-1

Recommendations

• Single machine total tardiness maximization problems: complexity and algorithms
• Algorithms for some maximization scheduling problems on a single machine
• Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one
• On minimizing the sum of \(k\) tardinesses
• Some improved algorithms on the single machine hierarchical scheduling with total tardiness as the primary criterion

zbMATH Keywords

dynamic programmingmaximizationschedulingsingle machinetotal tardiness

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Cites Work

• FPTAS for half-products minimization with scheduling applications
• Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one
• Minimization of ordered, symmetric half-products
• Positive half-products and scheduling with controllable processing times
• New results on the completion time variance minimization
• The symmetric quadratic knapsack problem: approximation and scheduling applications
• Minimizing total completion time in the flexible flowshop sequence-dependent group scheduling problem
• Fast approximation schemes for Boolean programming and scheduling problems related to positive convex half-product
• Minimization of half-products
• Single machine total tardiness maximization problems: complexity and algorithms
• A strongly polynomial FPTAS for the symmetric quadratic knapsack problem
• Evaluating flexible solutions in single machine scheduling via objective function maximization: the study of computational complexity
• Multi-project scheduling with two-stage decomposition
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems
• Algorithms for minclique scheduling problems
• Maximization problems in single machine scheduling
• Isomorphic scheduling problems
• Makespan minimization for parallel machines scheduling with multiple availability constraints
• Spatially explicit forest harvest scheduling with difference equations

Cited In (3)

• Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one
• Algorithms for some maximization scheduling problems on a single machine
• On minimizing the sum of \(k\) tardinesses

This page was built for publication: Maximizing total tardiness on a single machine in \(O(n^2)\) time via a reduction to half-product minimization

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