Exact approaches to late work scheduling on unrelated machines - Liu, Xinbo; Wang, Wen; Chen, Xin; Sterna, Małgorzata; Blazewicz, Jacek (Zielona Góra: Uniwersytet Zielonogórski)
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.
Keywords: late work scheduling; unrelated machines; mathematical model; branch-and-bound algorithm; dynamic programming