Rudy, Jarosław ; Idzikowski, Radosław ; Smutnicki, Czesław ; Banaszak, Zbigniew ; Bocewicz, Grzegorz
Współtwórca:Korbicz, Józef (1951- ) - red. ; Uciński, Dariusz - red.
Tytuł:New ideas in Lagrangian relaxation for a scheduling problem with the weighted tardiness criterion
Tytuł publikacji grupowej: Temat i słowa kluczowe: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.
Wydawca:Zielona Góra: Uniwersytet Zielonogórski
Data wydania: Typ zasobu: DOI: Strony: Źródło:AMCS, volume 34, number 2 (2024) ; kliknij tutaj, żeby przejść
Jezyk: Licencja CC BY 4.0: Prawa do dysponowania publikacją: