1. New Ideas in Lagrangian Relaxation for a Scheduling Problem with the weighted Tardiness Criterion
- Author
-
Rudy Jarosław, Idzikowski Radosław, Smutnicki Czesław, Banaszak Zbigniew, and Bocewicz Grzegorz
- Subjects
lagrangian relaxation ,scheduling ,total weighted tardiness ,metaheuristics ,Mathematics ,QA1-939 ,Electronic computers. Computer science ,QA75.5-76.95 - 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.
- Published
- 2024
- Full Text
- View/download PDF