Estimation of the absolute error and polynomial solvability for a classical NP-hard scheduling problem

DOI10.1134/S1064562418030201MaRDI QIDQ1673705zbMATH OpenFDO

Authors Alexander A. Lazarev, Dmitry I. Arkhipov

Publication date 13 September 2018

Published in Doklady Mathematics (Search for Journal in Brave)

zbMATH Keywords

approximate solution

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35)

Recommendations

• A scheme of approximation solution of problem 1 |r j|L max
• A metric for total tardiness minimization
• Estimation of absolute error in scheduling problems of minimizing the maximum lateness
• Solution of the NP-hard total tardiness minimization problem in scheduling theory
• Metric approach for finding approximate solutions of scheduling problems

Cites work

• scientific article; zbMATH DE number 3550182 (Why is no real title available?)
• Minimization of the maximal lateness for a single machine
• Minimizing Maximum Promptness and Maximum Lateness on a Single Machine

Cited in

(5)

• Polynomially solvable subcases for the approximate solution of multi-machine scheduling problems
• A metric approach for scheduling problems with minimizing the maximum penalty
• Metric approach for finding approximate solutions of scheduling problems
• A greedy algorithm for the solution of the classical NP-hard scheduling problem of minimizing the total delay
• Estimation of absolute error in scheduling problems of minimizing the maximum lateness

This page was built for publication: Estimation of the absolute error and polynomial solvability for a classical NP-hard scheduling problem

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