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.003MaRDI QIDQ732689zbMATH OpenOpenAlexWikidataFDO

Authors 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)

Recommendations

• Solution of the NP-hard total tardiness minimization problem in scheduling theory
• On the single machine total tardiness problem
• Some improved algorithms on the single machine hierarchical scheduling with total tardiness as the primary criterion
• A special case of the single-machine total tardiness problem is NP-hard
• Minimizing Total Tardiness on One Machine is NP-Hard

Cites work

• scientific article; zbMATH DE number 3550186 (Why is no real title available?)
• A decomposition algorithm for the single machine total tardiness problem
• A fully polynomial approximation scheme for the total tardiness problem
• A memetic algorithm for the total tardiness single machine scheduling problem
• A special case of the single-machine total tardiness problem is NP-hard
• Algorithmic paradoxes of the single-machine total tardiness problem
• Algorithms for solving the NP-hard problem of minimizing total tardiness for a single machine
• An enhanced dynasearch neighborhood for the single-machine total weighted tardiness scheduling problem
• Decomposition of the single machine total tardiness problem
• Improving local search heuristics for some scheduling problems. I
• Minimizing Total Tardiness on One Machine is NP-Hard
• On decomposition of the total tardiness problem
• One-Machine Sequencing to Minimize Certain Functions of Job Tardiness
• Solution of the single machine total tardiness problem
• The Total Tardiness Problem: Review and Extensions

Cited in

(9)

• Single machine scheduling problems with financial resource constraints: some complexity results and properties
• Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one
• A metric for total tardiness minimization
• A special case of the single-machine total tardiness problem is NP-hard
• Algorithms for some maximization scheduling problems on a single machine
• Metric approach for finding approximate solutions of scheduling problems
• Some improved algorithms on the single machine hierarchical scheduling with total tardiness as the primary criterion
• A graphical realization of the dynamic programming method for solving NP-hard combinatorial problems
• A note on a single machine scheduling problem with generalized total tardiness objective function

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

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