Estimation of absolute error in scheduling problems of minimizing the maximum lateness (Q2377526)

The paper considers the scheduling problem to minimize the maximum lateness on identical parallel machines. The jobs may have distinct release dates and are subject to precedence constraints. Given two instances of the problem with the same set of jobs, a metric is introduced that reflects how the processing times, the release dates and the due dates differ in both instances. The metric and its components are shown to serve as estimates of the differences between the values of objective function in the two instances. Based on that, an approach to finding an approximate solution to a given instance of the problem is discussed. The approach recommends that the original instance should be perturbed to fall into a certain polynomially solvable special case of the problem. The metric will show by how much the solution of this perturbed instance is away from the optimum of the original problem.