Heuristic column generation algorithm for identical parallel machine scheduling problem with deterioration effect
An integer programming model is built to minimize the maximum completion time and a heuristic column generation algorithm(HCGA)is proposed for a class of identical parallel machine scheduling problem with deterioration effect that widely exist in practical production.In the HCGA,first,the original problem is decomposed into a master problem(MP)and multiple subproblems by using the Dantzig-Wolfe decomposition method.Secondly,a heuristic algorithm is designed to obtain initial columns,where each column represents a schedule on one machine.Based on the initial columns,a restricted MP(RMP)model is constructed.Then,a fast and effective dynamic programming algorithm is designed to solve each subproblem to obtain the column set to be added to the RMP.At the same time,considering that the convergence speed of traditional column generation algorithms is slow,a series of methods are designed to accelerate the column generation process.Finally,based on the obtained linear relaxation solution of the MP,a diving heuristic algorithm is designed to determine the integer solution of the original problem.According to the comparative experimental results of the HCGA and commercial solver GUROBI,the HCGA can obtain better solutions in a shorter time.
NETL
NSTL
万方数据
