A metric approach for scheduling problems with minimizing the maximum penalty

What is it about?

NP-hard scheduling problems with the criterion of minimizing the maximum penalty, e.g. maximum lateness, are considered. For such problems, a metric which delivers an upper bound on the absolute error of the objective function value is introduced. Taking the given instance of some problem and using the introduced metric, the nearest instance is determined for which a polynomial or pseudo-polynomial algorithm is known. A schedule is constructed for this determined instance which is then applied to the original instance. It is shown how this approach can be applied to different scheduling problems.

Featured Image

Why is it important?

1) A theory for solving a class of scheduling problems approximately is developed; 2) A metric is introduced based on the parameters of an instance allowing to estimate the absolute error; 3) Polynomially solvable sub-cases are effectively used for solving NP-hard problems; 4) The metric approach uses all available knowledge about particular cases of scheduling problems; 5) The theory is applied to several scheduling problems and tested on a single machine problem.