Metric approach for finding approximate solutions of scheduling problems

Metric functions are introduced for various classes of single-machine scheduling problems. It is shown how approximate solutions of NP-hard problems can be found using these functions. The metric value is determined by solving a linear programming problem with constraints being systems of linear inequalities for polynomial or pseudopolynomial solvable instances of the problem under study. In fact, the initial instance is projected onto the subspace of solvable problem instances in the introduced metric.