Single machine total tardiness maximization problems: complexity and algorithms

DOI10.1007/s10479-012-1288-xzbMath1273.90079OpenAlexW2157859449WikidataQ57633823 ScholiaQ57633823MaRDI QIDQ367638

Frank Werner, Evgeny R. Gafarov, Alexander A. Lazarev

Publication date: 16 September 2013

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

Full work available at URL: https://doi.org/10.1007/s10479-012-1288-x

zbMATH Keywords

complexityschedulingdynamic programmingsingle machine maximization problems

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Related Items (3)

Minimizing total weighted tardiness for scheduling equal-length jobs on a single machine ⋮ Research on permutation flow shop scheduling problems with general position-dependent learning effects ⋮ Maximizing total tardiness on a single machine in \(O(n^2)\) time via a reduction to half-product minimization

Cites Work

• Unnamed Item
• Unnamed Item
• Maximization problems in single machine scheduling
• Algorithms for some maximization scheduling problems on a single machine
• Flexible solutions in disjunctive scheduling: general formulation and study of the flow-shop case
• Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Evaluating flexible solutions in single machine scheduling via objective function maximization: the study of computational complexity
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems

This page was built for publication: Single machine total tardiness maximization problems: complexity and algorithms