online read us now
Paper details
Number 3 - September 2020
Volume 30 - 2020
Two meta-heuristic algorithms for scheduling on unrelated machines with the late work criterion
Wen Wang, Xin Chen, Jedrzej Musial, Jacek Blazewicz
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 metaheuristics.
Keywords
late work minimization, unrelated machines, tabu search, genetic algorithm