Scheduling unrelated parallel machines to minimize total weighted tardiness
This article considers the problem of scheduling a given set of independent jobs on unrelated parallel machines to minimize the total weighted tardiness. The problem is known to be NP-hard in the strong sense. Efficient lower and upper bounds are developed. The lower bound is based on the solution of an assignment problem, while the upper bound is obtained by a two-phase heuristic. A branch-and-bound algorithm that incorporates various dominance rules is presented. Computational experiments are conducted to demonstrate the performance of the proposed algorithm. Scope and purpose Parallel machine scheduling models are important from both the theoretical and practical points of view. From the theoretical point of view, they generalize the single machine scheduling models. From the practical point of view, they are important because the occurrence of a bank of machines in parallel is common in industries. In this article, the unrelated parallel machine total weighted tardiness scheduling problem is examined. The tardiness criterion has many applications in real world. This problem is difficult to solve. A branch-and-bound algorithm that incorporates various dominance rules along with efficient lower and upper bounds is proposed to find an optimal solution.
scheduling parallel machines tardiness branch-and-bound