A Branch-and-Price Algorithm for Unrelated Parallel Machine Scheduling to Minimize Total Weighted Completion Time

This paper addresses an unrelated parallel machine scheduling problem, aiming to minimize the total weighted completion time. The problem is formulated into a set-partitioning model, and a branch-and-price algorithm is developed to solve it. To handle the pricing problem, a pseudo-polynomial dynamic programming and a polynomial-time heuristic are proposed. Furthermore, a greedy heuristic is designed to provide tight upper bounds. Numerical experiments on 200 benchmark instances with up to 100 jobs and 30 machines, highlight the effectiveness and efficiency of the proposed algorithm, particularly for instances with a large number of machines.