Resource Allocation Optimization Method with Multi-Resource Operations

doi:10.3778/j.issn.1002-8331.2307-0109

Abstract

Abstract: This paper addresses a resource-allocation problem from a real life application involving multi-resource operations. Such a problem arises in many practical applications manufacturing and services. A mixed integer linear programming model is established to minimize the makespan. According to the characteristics of the problem, an improved tabu search algorithm is developed. The algorithm avoids falling into local optima by a perturbation strategy and adaptive tabu length. The experimental results on 300 randomly generated instances show that the improved tabu search algorithm outperforms CPLEX, classical taboo search algorithm, variable neighborhood search algorithm, and genetic algorithm in solving large-scale instances, providing better resource allocation solutions. Compared to CPLEX, the objective function value shows an improvement of 3.01%.

Key words: resource allocation, multi-resource operations, resource allocation-based precedence constraints, tabu search algorithm

摘要： 针对广泛存在于制造业和服务业等现实应用中的需要多类资源的多资源工序，提炼出一类新的带多资源工序的资源分配问题。建立了以最小化最大完工时间为目标的混合整数线性规划模型，并根据问题特征设计了改进禁忌搜索算法。在算法设计中，通过扰动策略和自适应禁忌长度避免陷入局部最优。300个不同规模仿真算例实验结果表明：在求解大规模实例中，改进禁忌搜索算法的性能表现优于CPLEX、经典禁忌搜索算法、变邻域搜索算法和遗传算法，能给出更好的资源分配方案；与CPLEX相比，目标函数值改善了3.01%。

关键词: 资源分配, 带多资源工序, 基于资源分配的先后次序, 禁忌搜索算法

WENG Wuyan, CHU Chengbin, WU Peng. Resource Allocation Optimization Method with Multi-Resource Operations[J]. Computer Engineering and Applications, 2024, 60(21): 324-330.

翁武燕, 储诚斌, 吴鹏. 一类带多资源工序的资源分配优化方法[J]. 计算机工程与应用, 2024, 60(21): 324-330.

References

[1] ROSS G T, SOLAND R M. A branch and bound algorithm for the generalized assignment problem[J]. Mathematical Programming, 1975, 8(1): 91-103.
[2] 裴小兵, 祁文博, 戴毓彤. 求解柔性作业车间调度问题的新型改进Jaya算法[J]. 计算机工程与应用, 2022, 58(19): 318-325.
PEI X B, QI W B, DAI Y T. New improved Jaya algorithm for solving flexible job shop scheduling problem[J]. Computer Engineering and Applications, 2022, 58(19): 318-325.
[3] 轩华, 李文婷, 李冰. 混合离散人工蜂群算法求解含不相关并行机的分布式柔性流水线调度[J]. 控制与决策, 2023, 38(3): 779-789.
XUAN H, LI W T, LI B. Hybrid discrete artificial bee colony algorithm for distributed flexible flowline scheduling with unrelated parallel machines[J]. Control and Decision, 2023, 38(3): 779-789.
[4] 刘文程, 高家全. 解并行机模糊调度问题的自适应遗传算法[J]. 计算机工程与应用, 2013, 49(7): 60-63.
LIU W C, GAO J Q. Self-adapting genetic algorithm for solving fuzzy scheduling problem on parallel machines[J]. Computer Engineering and Applications, 2013, 49(7): 60-63.
[5] GAO L, PAN Q K. A shuffled multi-swarm micro-migrating birds optimizer for a multi-resource-constrained flexible job shop scheduling problem[J]. Information Sciences, 2016, 372: 655-676.
[6] CHEN R, YANG B, LI S, et al. A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem[J]. Computers & Industrial Engineering, 2020, 149: 106778.
[7] 谢锐强, 张惠珍. 求解柔性作业车间调度问题的两段式狼群算法[J]. 计算机工程与应用, 2021, 57(7): 251-256.
XIE R Q, ZHANG H Z. Two-vector wolf pack algorithm for flexible job shop scheduling problem[J]. Computer Engineering and Applications, 2021, 57(7): 251-256.
[8] KUO W H, YANG D L. Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect[J]. European Journal of Operational Research, 2006, 174(2): 1184-1190.
[9] MATI Y, XIE X. Multi-resource shop scheduling with resource flexibility and blocking[J]. IEEE Transactions on Automation Science and Engineering, 2010, 8(1): 175-189.
[10] HUH W T, LIU N, TRUONG V A. Multi-resource allocation scheduling in dynamic environments[J]. Manufacturing & Service Operations Management, 2013, 15(2): 280-291.
[11] RAHIMI I, GANDOMI A H. A comprehensive review and analysis of operating room and surgery scheduling[J]. Archives of Computational Methods in Engineering, 2021, 28(3): 1667-1688.
[12] MEDARD C P, SAWHNEY N. Airline crew scheduling from planning to operations[J]. European Journal of Operational Research, 2007, 183(3): 1013-1027.
[13] MANAA A, CHU C B. Scheduling multiprocessor tasks to minimise the makespan on two dedicated processors[J]. European Journal of Industrial Engineering, 2010, 4(3): 265-279.
[14] MELLOULI R, SADFI C, CHU C B, et al. Identical parallel-machine scheduling under availability constraints to minimize the sum of completion times[J]. European Journal of Operational Research, 2009, 197(3): 1150-1165.
[15] JI M, WANG J Y, LEE W C. Minimizing resource consumption on uniform parallel machines with a bound on makespan[J]. Computers & Operations Research, 2013, 40(12): 2970-2974.
[16] WANG S, WU R, CHU F, et al. An exact decomposition method for unrelated parallel machine scheduling with order acceptance and setup times[J]. Computers & Industrial Engineering, 2023, 175: 108899.
[17] 吴秀丽, 肖晓, 赵宁. 考虑装卸的柔性作业车间双资源调度问题[J]. 控制与决策, 2020, 35(10): 2475-2485.
WU X L, XIAO X, ZHAO N. Flexible job shop dual resource scheduling problem considering loading and unloading[J]. Control and Decision, 2020, 35(10): 2475-2485.
[18] LYU X, SONG Y, HE C, et al. Approach to integrated scheduling problems considering optimal number of automated guided vehicles and conflict-free routing in flexible manufacturing systems[J]. IEEE Access, 2019, 7: 74909-74924.
[19] CHU F, LIU M, LIU X, et al. Reentrant flow shop scheduling considering multi-resource qualification matching[J]. Scientific Programming, 2018: 1-8.
[20] LEI D, GUO X. Variable neighbourhood search for dual-resource constrained flexible job shop scheduling[J]. International Journal of Production Research, 2014, 52(9): 2519-2529.
[21] LI J, HUANG Y, NIU X. A branch population genetic algorithm for dual-resource constrained job shop scheduleing problem[J]. Computers & Industrial Engineering, 2016, 102: 113-131.
[22] TAN W, YUAN X, WANG J, et al. A fatigue-conscious dual resource constrained flexible job shop scheduling problem by enhanced NSGA-II: an application from casting workshop[J]. Computers & Industrial Engineering, 2021, 160: 107557.
[23] BERTI N, FINCO S, BATTA?A O, et al. Ageing workforce effects in dual-resource constrained job-shop scheduling[J]. International Journal of Production Economics, 2021, 237: 108-151.
[24] 张洪亮, 徐静茹, 谈波, 等. 考虑交货期的双资源柔性作业车间节能调度[J]. 系统仿真学报, 2023, 35(4): 734-746.
ZHANG H L, XU J R, TAN B, et al. Dual resource constrained flexible job shop energy-saving scheduling considering delivery time[J]. Journal of System Simulation, 2023, 35(4): 734-746.
[25] DAUZERE-PéRES S, ROUX W, LASSERRE J B. Multi-resource shop scheduling with resource flexibility[J]. European Journal of Operational Research, 1998, 107(2): 289-305.
[26] 李淑娟, 李言, 刘志刚. 一类多资源作业车间混合优化调度方法[J]. 系统工程学报, 2007(5): 551-555.
LI S J, LI Y, LIU Z G. Mix optimization scheduling approach for multi-resource job-shop[J]. Journal of System Engineering, 2007(5): 551-555.
[27] DESPREZ C, CHU F, CHU C B. Minimising the weighted number of tardy jobs in a hybrid flow shop with genetic algorithm[J]. International Journal of Computer Integrated Manufacturing, 2009, 22(8): 745-757.
[28] MATI Y, LAHLOU C, DAUZERE-PERES S. Modelling and solving a practical flexible job-shop scheduling problem with blocking constraints[J]. International Journal of Production Research, 2011, 49(8): 2169-2182.
[29] 崔建双, 杨建华. 多资源约束的项目调度问题离散粒子群算法[J].计算机工程与应用, 2015, 51(14): 253-257.
CUI J S, YANG J H. Multiple resource constrained project scheduling problem with discrete particle swarm optimization[J]. Computer Engineering and Applications, 2015, 51 (14): 253-257.
[30] 陈展, 公建宁, 刘媛媛, 等.基于禁忌搜索的多AGV系统路径优化算法[J]. 计算机工程与应用, 2021, 57(10): 273-278.
CHEN Z, GONG J N, LIU Y Y, et al. Multi-AGV system path optimization algorithm based on tabu search[J]. Computer Engineering and Applications, 2021, 57(10): 273-278.
[31] 李国明, 李军华. 基于混合禁忌搜索算法的随机车辆路径问题[J]. 控制与决策, 2021, 36(9): 2161-2169.
LI G M, LI J H. Stochastic vehicle routing problem based on hybrid tabu search algorithm[J]. Control and Decision, 2021, 36(9): 2161-2169.
[32] LIANG Y C, CHUANG C Y. Variable neighborhood search for multi-objective resource allocation problems[J]. Robotics and Computer-Integrated Manufacturing, 2013, 29(3): 73-78.
[33] 王征, 张俊, 王旭坪. 多车场带时间窗车辆路径问题的变邻域搜索算法[J]. 中国管理科学, 2011, 19(2): 99-109.
WANG Z, ZHANG J, WANG X P. A modified variable neighborhood search algorithm for the multi depot vehicle routing problem with time windows[J]. Chinese Journal of Management Science, 2011, 19(2): 99-109.