Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 International Journal of Applied Mathematics and Computer Science

1 2024

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: problem harmonogramowania

Sortuj według:

Ogranicz wyniki do:

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

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

International Journal of Applied Mathematics and Computer Science

2024

Vol. 34, no. 2

235--251

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.