Investigation of NP-hard scheduling problems on a single machine

To consider classical NP-hard scheduling problems for a single machine. For the problem minimizing maximum lateness: formulated and decided "dual" and "reverse" problems (polynomial algorithms), lower bounds for branch&bound algorithm; new polynomial solvable cases; minimum absolute error by modify parameters of jobs (release times and due dates); "hard" areas; interpolated polynomial; experimental research. For the problem minimizing total tardiness: "suitable" positions in optimal sequence for the job with maximum processing time, "suitable" branch method; "hard" area; interpolated methods; experimental research.

B.Hammer