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

DOI10.1134/S1064562418030201zbMATH Open1401.90077MaRDI QIDQ1673705FDOQ1673705

Authors: Alexander A. Lazarev, Dmitry I. Arkhipov 

Publication date: 13 September 2018

Published in: Doklady Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

approximate solution

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Minimizing Maximum Promptness and Maximum Lateness on a Single Machine
• Minimization of the maximal lateness for a single machine

Cited In (4)

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