Rudy, Jarosław ; Idzikowski, Radosław ; Smutnicki, Czesław ; Banaszak, Zbigniew ; Bocewicz, Grzegorz
Contributor:Korbicz, Józef (1951- ) - red. ; Uciński, Dariusz - red.
Title:New ideas in Lagrangian relaxation for a scheduling problem with the weighted tardiness criterion
Group publication title: Subject and Keywords:Lagrangian relaxation ; scheduling ; total weighted tardiness ; metaheuristics
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.
Publisher:Zielona Góra: Uniwersytet Zielonogórski
Date: Resource Type: DOI: Pages: Source:AMCS, volume 34, number 2 (2024) ; click here to follow the link
Language: License CC BY 4.0: Rights: