International Journal of applied mathematics and computer science

online read us now

Paper details

Number 2 - June 2023
Volume 33 - 2023

Exact approaches to late work scheduling on unrelated machines

Xinbo Liu, Wen Wang, Xin Chen, Malgorzata Sterna, Jacek Blazewicz

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.

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