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

<p>We consider the scheduling problem on unrelated parallel machines in order to minimize the total late work. Since the problem is NP-hard, we propose a mathematical model and two dedicated exact approaches for solving it, based on the branching and bounding strategy and on enumerating combined with a dynamic programming algorithm. The time efficiencies of all three approaches are evaluated through computational experiments.</p>
</abstract>

We consider the scheduling problem on unrelated parallel machines in order to minimize the total late work. Since the problem is NP-hard, we propose a mathematical model and two dedicated exact approaches for solving it, based on the branching and bounding strategy and on enumerating combined with a dynamic programming algorithm. The time efficiencies of all three approaches are evaluated through computational experiments.

Exact Approaches to Late Work Scheduling on Unrelated Machines

International Journal of Applied Mathematics and Computer Science

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

{"article-title":"Exact Approaches to Late Work Scheduling on Unrelated Machines"}

We consider the scheduling problem on unrelated parallel machines in order to minimize the total late work. Since the problem is NP-hard, we propose a...

Exact Approaches to Late Work Scheduling on Unrelated Machines

Publicado en línea: 23 jun 2023

Páginas: 285 - 295

Recibido: 10 jun 2022

Aceptado: 12 ene 2023

DOI: https://doi.org/10.34768/amcs-2023-0021

Palabras clave
late work scheduling, unrelated machines, mathematical model, branch-and-bound algorithm, dynamic programming

© 2023 Xinbo Liu et al., published by Sciendo

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

Exact Approaches to Late Work Scheduling on Unrelated Machines

Publicado en línea: 23 jun 2023

Páginas: 285 - 295

Recibido: 10 jun 2022

Aceptado: 12 ene 2023

DOI: https://doi.org/10.34768/amcs-2023-0021

Palabras clavelate work scheduling, unrelated machines, mathematical model, branch-and-bound algorithm, dynamic programming

© 2023 Xinbo Liu et al., published by Sciendo

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

Palabras clave
late work scheduling, unrelated machines, mathematical model, branch-and-bound algorithm, dynamic programming