Identical parallel machine scheduling to minimise makespan and total weighted completion time: a column generation approach

In this paper, we consider an identical parallel machine scheduling problem with the objective to minimise the sum of weighted completion time and makespan, which is denoted as P-m parallel to Sigma w(j)C(j)+C-max, w(j) >= 0. We formulate the problem as a mixed integer programming (MIP) problem based on the properties of an optimal schedule. Leveraging the Dantzig-Wolfe decomposition method, the problem is solved in a Column Generation (CG) framework with a master problem and an NP-hard pricing problem. With derived lower bounds, we are able to solve the problems to near optimality in a short time. The CG procedure is also used in the special conditions when P-m parallel to Sigma w(j)C(j)+C-max becomes P-m parallel to Sigma w(j)C(j) or P-m parallel to C-max. Comparison experiments between the CG procedure and CPLEX are carried out for a set of synthetically generated scenarios. Computational experiments demonstrate that our CG procedure provides near-optimal solutions in a short time.