极小化加权完工时间的多资源工序的资源分配问题

Resource allocation to minimize the weighted completion time with multi-resource operations

针对现实中广泛存在的多资源工序的资源分配问题,考虑基于资源使用的优先次序约束,以最小化加权完工时间为优化目标,构建一类新的资源分配混合整数线性规划模型.其次,提出Benders分解和禁忌搜索的混合算法,该混合算法以Benders分解为基本框架,将原问题分为提供资源分配方案的主问题和计算工序加权完工时间的子问题,并通过改进数学模型和添加禁忌搜索提高混合算法的收敛速度.最后,通过300个随机仿真算例测试结果表明,在相同时间下求解小规模问题时,所提的Benders分解混合算法能获得距离商业求解器CPLEX最优解平均差距为0.86%的满意解;在求解大规模问题时,所提出的算法的性能表现优于CPLEX、禁忌搜索算法、变邻域搜索算法和Benders分解嵌入遗传算法的混合方法,能给出更好的资源分配方案,与CPLEX相比,上界和下界分别改善了4.74%和9.62%.

This paper addresses a resource-allocation problem extracted from real life application involving multi-resource operations.A new mixed integer linear programming model is proposed to minimize the weighted completion time while considering resource-related precedence relationships.Then,a hybrid algorithm combining Benders decomposition and Tabu search is developed based on Benders decomposition as the basic framework.This method divides the original problem into a master problem for resource allocation and a subproblem of calculating the completion time of each operation.The convergence is sped up by improving the mathematical model and embedding the Tabu search approach.The experimental results on 300 randomly generated instances show that when solving small-scale problems,the proposed hybrid algorithm can yield satisfactory solutions with an average deviation of 0.86%from optimal ones provided by the commercial CPLEX solver;when solving large-scale problems,the proposed algorithm outperforms the CPLEX solver,the pure Tabu search algorithm,the variable neighborhood search algorithm and the Benders decomposition with embedded genetic algorithm.Compared with the CPLEX,the upper bound and lower bound are improved by 4.74%and 9.62%respectively.