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
Abstract
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.
Keywords
Lagrangian relaxation, scheduling, total weighted tardiness, metaheuristics