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‖∑w_jC_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‖∑w_jC_j + C_(max) becomes P_m‖∑w_jC_j or P_m‖ 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.