This paper investigates a new resource-allocation problem involving multi-resource operations,where completing an operation requires simultaneous use of multiple(renewable)resources,probably of different types.The goa...This paper investigates a new resource-allocation problem involving multi-resource operations,where completing an operation requires simultaneous use of multiple(renewable)resources,probably of different types.The goal of the study is to provide a solution method that minimizes the makespan.The authors formulate the problem into a novel mixed-integer linear program(MILP)model.To efficiently solve practical-sized instances,an exact Benders decomposition algorithm is developed.This algorithm divides the original problem into a master problem of allocating resources and a subproblem of calculating the makespan,and both are linked via Benders cuts.The convergence is sped up by improving the mathematical model and embedding the variable neighborhood search algorithm.Compared with CPLEX,a commonly used MILP solver,the computational results demonstrate that the proposed algorithm provides tighter upper and lower bounds in most instances.In particular,compared with CPLEX,the proposed method can on average improve the upper and lower bounds by 4.76%and 4.39%,respectively,in solving practical-sized instances.展开更多
基金supported by the National Natural Science Foundation of China under Grant Nos.71871159,71701049,and 71901069National Social Science Foundation of China under Grant No.22BGL272+1 种基金Humanities and Social Science Foundation of the Chinese Ministry of Education under Grant No.21YJA630096Natural Science Foundation of Fujian Province,China under Grant Nos.2020J05040 and 2022J01075。
文摘This paper investigates a new resource-allocation problem involving multi-resource operations,where completing an operation requires simultaneous use of multiple(renewable)resources,probably of different types.The goal of the study is to provide a solution method that minimizes the makespan.The authors formulate the problem into a novel mixed-integer linear program(MILP)model.To efficiently solve practical-sized instances,an exact Benders decomposition algorithm is developed.This algorithm divides the original problem into a master problem of allocating resources and a subproblem of calculating the makespan,and both are linked via Benders cuts.The convergence is sped up by improving the mathematical model and embedding the variable neighborhood search algorithm.Compared with CPLEX,a commonly used MILP solver,the computational results demonstrate that the proposed algorithm provides tighter upper and lower bounds in most instances.In particular,compared with CPLEX,the proposed method can on average improve the upper and lower bounds by 4.76%and 4.39%,respectively,in solving practical-sized instances.
