Algorithms for special cases of the single machine total tardiness problem and an application to the even-odd partition problem

DOI10.1016/j.mcm.2009.01.003zbMath1198.68152OpenAlexW1971048091WikidataQ57633883 ScholiaQ57633883MaRDI QIDQ732689

Alexander A. Lazarev, Frank Werner

Publication date: 12 October 2009

Published in: Mathematical and Computer Modelling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.mcm.2009.01.003

zbMATH Keywords

schedulingsingle machinetotal tardinesseven-odd partition\(NP\)-hardness

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (7)

A metric for total tardiness minimization ⋮ 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 ⋮ Single machine scheduling problems with financial resource constraints: some complexity results and properties ⋮ A graphical realization of the dynamic programming method for solving NP-hard combinatorial problems ⋮ Metric approach for finding approximate solutions of scheduling problems ⋮ A note on a single machine scheduling problem with generalized total tardiness objective function

Cites Work

• Unnamed Item
• Algorithms for solving the NP-hard problem of minimizing total tardiness for a single machine
• Decomposition of the single machine total tardiness problem
• An enhanced dynasearch neighborhood for the single-machine total weighted tardiness scheduling problem
• Solution of the single machine total tardiness problem
• A decomposition algorithm for the single machine total tardiness problem
• A fully polynomial approximation scheme for the total tardiness problem
• Improving local search heuristics for some scheduling problems. I
• On decomposition of the total tardiness problem
• A special case of the single-machine total tardiness problem is NP-hard
• Minimizing Total Tardiness on One Machine is NP-Hard
• The Total Tardiness Problem: Review and Extensions
• One-Machine Sequencing to Minimize Certain Functions of Job Tardiness
• Algorithmic paradoxes of the single-machine total tardiness problem
• A memetic algorithm for the total tardiness single machine scheduling problem

This page was built for publication: Algorithms for special cases of the single machine total tardiness problem and an application to the even-odd partition problem