International Journal of applied mathematics and computer science

online read us now

Paper details

Number 2 - June 2024
Volume 34 - 2024

New ideas in Lagrangian relaxation for a scheduling problem with the weighted tardiness criterion

Jarosław Rudy, Radosław Idzikowski, Czesław Smutnicki, Zbigniew Banaszak, Grzegorz Bocewicz

We consider an extension of Lagrangian relaxation methods for solving the total weighted tardiness scheduling problem on a single machine. First, we investigate a straightforward relaxation method and decompose it into upper and lower subproblems. For the upper subproblem we propose an alternative solving method in the form of a local search metaheuristic. We also introduce a scaling technique by arbitrary numbers to reduce the complexity of the problem and confront it with greatest common divisor scaling. Next, we propose a novel alternative relaxation approach based on aggregating constraints. We discuss the properties and implementation of this new approach and a technique to further reduce its computational complexity. We perform a number of computer experiments on instances based on the OR-Library generation scheme to illustrate and ascertain the numerical properties of the proposed methods. The results indicate that for larger instances the proposed alternative relaxation and scaling approaches have a much better convergence rate with little to no decrease in solution quality. The results also show that the proposed local-search metaheuristic is a viable alternative to the existing solving methods.

Lagrangian relaxation, scheduling, total weighted tardiness, metaheuristics