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 Pm || ∑wjCj + Cmax, wj ≥ 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 Pm || ∑wjCj + Cmax becomes Pm || ∑wjCj or Pm || Cmax. 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.
- Column generation
- Identical parallel machine scheduling
- Weighted completion time
ASJC Scopus subject areas
- Strategy and Management
- Management Science and Operations Research
- Industrial and Manufacturing Engineering