<abstract xmlns="http://www.w3.org/1999/xhtml"><p>A scheduling problem in considered on unrelated machines with the goal of total late work minimization, in which the late work of a job means the late units executed after its due date. Due to the NP-hardness of the problem, we propose two meta-heuristic algorithms to solve it, namely, a tabu search (TS) and a genetic algorithm (GA), both of which are equipped with the techniques of initialization, iteration, as well as termination. The performances of the designed algorithms are verified through computational experiments, where we show that the GA can produce better solutions but with a higher time consumption. Moreover, we also analyze the influence of problem parameters on the performances of these meta-heuristics.</p></abstract>

A scheduling problem in considered on unrelated machines with the goal of total late work minimization, in which the late work of a job means the late units executed after its due date. Due to the NP-hardness of the problem, we propose two meta-heuristic algorithms to solve it, namely, a tabu search (TS) and a genetic algorithm (GA), both of which are equipped with the techniques of initialization, iteration, as well as termination. The performances of the designed algorithms are verified through computational experiments, where we show that the GA can produce better solutions but with a higher time consumption. Moreover, we also analyze the influence of problem parameters on the performances of these meta-heuristics.

Two Meta–Heuristic Algorithms for Scheduling on Unrelated Machines with the Late Work Criterion

International Journal of Applied Mathematics and Computer Science

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

A scheduling problem in considered on unrelated machines with the goal of total late work minimization, in which the late work of a job means the late units...

Two Meta–Heuristic Algorithms for Scheduling on Unrelated Machines with the Late Work Criterion

Data publikacji: 29 wrz 2020

Zakres stron: 573 - 584

Otrzymano: 20 lut 2020

Przyjęty: 02 lip 2020

DOI: https://doi.org/10.34768/amcs-2020-0042

Słowa kluczowe
late work minimization, unrelated machines, tabu search, genetic algorithm

© 2020 Wen Wang et al., published by Sciendo

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

Two Meta–Heuristic Algorithms for Scheduling on Unrelated Machines with the Late Work Criterion

Data publikacji: 29 wrz 2020

Zakres stron: 573 - 584

Otrzymano: 20 lut 2020

Przyjęty: 02 lip 2020

DOI: https://doi.org/10.34768/amcs-2020-0042

Słowa kluczowelate work minimization, unrelated machines, tabu search, genetic algorithm

© 2020 Wen Wang et al., published by Sciendo

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

Słowa kluczowe
late work minimization, unrelated machines, tabu search, genetic algorithm