<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>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.</p>
</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.

New Ideas in Lagrangian Relaxation for a Scheduling Problem with the weighted Tardiness Criterion

Department of Control Systems and Mechatronics

Wrocław University of Science and Technology

Department of Computer Science and Management

International Journal of Applied Mathematics and Computer Science

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

We consider an extension of Lagrangian relaxation methods for solving the total weighted tardiness scheduling problem on a single machine. First, we...

New Ideas in Lagrangian Relaxation for a Scheduling Problem with the weighted Tardiness Criterion

Published Online: Jun 25, 2024

Page range: 235 - 251

Received: Oct 17, 2023

Accepted: Mar 18, 2024

DOI: https://doi.org/10.61822/amcs-2024-0017

Keywords
Lagrangian relaxation, scheduling, total weighted tardiness, metaheuristics

© 2024 Jarosław Rudy et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

New Ideas in Lagrangian Relaxation for a Scheduling Problem with the weighted Tardiness Criterion

Published Online: Jun 25, 2024

Page range: 235 - 251

Received: Oct 17, 2023

Accepted: Mar 18, 2024

DOI: https://doi.org/10.61822/amcs-2024-0017

KeywordsLagrangian relaxation, scheduling, total weighted tardiness, metaheuristics

© 2024 Jarosław Rudy et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Keywords
Lagrangian relaxation, scheduling, total weighted tardiness, metaheuristics