计算机科学 ›› 2020, Vol. 47 ›› Issue (6A): 124-129.doi: 10.11896/JsJkx.190900123
姚敏
YAO Min
摘要: 柔性资源普遍存在于制造业生产制造的各个环节中,提高了资源利用率和生产效益。以柔性资源为研究对象,建立了以最小化项目完成工期为目标的柔性资源受限项目调度问题的数学模型。针对现有标准遗传算法过早地收敛从而使整个遗传搜索无法求解出全局最优值的缺陷,提出了一种改进的多种群遗传算法来求解该问题模型。算法对作业优先级列表编码,引入交叉移民算子实现多种群间的协同进化,在解码过程中运用一种启发式柔性资源技能分配算法为作业分配资源,同时通过改进的串行调度生成方案对作业调度。最后通过标准算例库PSPLIB进行数值试验,验证了所提算法求解该问题的有效性。
中图分类号:
[1] KADRI R L,BOCTOR F F.An efficient genetic algorithm to solve the resource-constrained proJect scheduling problem with transfer times:The single mode case.European Journal of Operational Research,2018,265(2):454-462. [2] REN Y F,LU Z Q,LIU X Y,et al.ProJect scheduling problem with hierarchical levels of skills.Journal of ZheJiang University (Engineering Science),2017,51(5):1000-1006. [3] NRON E.Lower bounds for the multi-skill proJect scheduling problem//Proceeding of the Eighth International Workshop on ProJect Management and Scheduling.2002:274-277. [4] BELLENGUEZ-MORINEAU O.Methods to solve multi-skill proJect scheduling problem.Springer-Verlag,2008. [5] LI H,WOMER K.Scheduling proJects with multi-skilled personnel by a hybrid MILP/CP benders decomposition algorithm.Journal of Scheduling,2009,12(3):281. [6] JIA Y,WANG Z M,ZHANG Y G.Heuristic algorithm for flexible resource-constrained proJect scheduling problem.Computer Integrated Manufacturing Systems,2015,21(7):1846-1855. [7] ZHANG M,LU Z Q.Improved algorithm for multi-skill resource constraint proJect scheduling problem.Computer Integrated Manufacturing Systems,2016,22(3):782-792. [8] XIE F,XU Z,YU J.Bi-obJective optimization for the proJectscheduling problem with variable resource availability.Systems Engineering-Theory & Practice,2016,36(3):674-683. [9] HEIMERL C,KOLISCH R.Scheduling and staffing multiple proJects with a multi-skilled workforce.OR spectrum,2010,32(2):343-368. [10] LIU Z Y,YUAN H T,ZHOU C,et al.Branch and bound based approach for preemptive proJect scheduling with time-window constraints on multi-skilled resources.Systems Engineering-Theory & Practice,2019,39(1):183-199. [11] MYSZKOWSKI P B,OLECH P,LASZCZYK M,et al.Hybrid differential evolution and greedy algorithm (DEGR) for solving multi-skill resource-constrained proJect scheduling problem.Applied Soft Computing,2018,62:1-14. [12] TRITSCHLER M,NABER A,KOLISCH R.A hybrid metaheuristic for resource-constrained proJect scheduling with flexible resource profiles.European Journal of Operational Research,2017,262(1):262-273. [13] ZHA H,ZHANG L.Fuzzy flexible resource constrained proJect scheduling based on genetic algorithm.Transactions of TianJin University,2014,20(6):469-474. [14] RANJBAR M,KIANFAR F.Resource constrained proJect scheduling problem with flexible work profiles:a genetic algorithm approach.Scientia Iranica.Transaction E,Industrial Engineering,2010,17(1):25. [15] XING L N,CHEN Y W,YANG K W.Multi-population interactive coevolutionary algorithm for flexible Job shop scheduling problems.Computational Optimization and Applications,2011,48(1):139-155. [16] COCHRAN J K,HORNG S M,FOWLER J W.A multi-population genetic algorithm to solve multi-obJective scheduling problems for parallel machines.Computers & Operations Research,2003,30(7):1087-1102. [17] JIAO Y L,ZHANG P,TIAN G D,et al.Slotting optimization of automated warehouse based on multi-population GA.Journal of Jilin University(Engineering and Technology Edition),2018,48(5):1398-1404. [18] LIU A J,YANG Y,XING Q S,et al.Multi-population genetic algorithm in multiobJective fuzzy and flexible Job Shop scheduling.Computer Integrated Manufacturing Systems,2011,17(9):1954-1961. [19] WANG D,GUI W X.A multi-population genetic algorithm based on cross accessibility evaluation.Journal of Guangxi University(Natural Science Edition),2015,40(6):1508-1516. [20] MAGHSOUDLOU H,AFSHAR-NADJAFI B,NIAKI S T A.A multi-obJective invasive weeds optimization algorithm for solving multi-skill multi-mode resource constrained proJect scheduling problem.Computers & Chemical Engineering,2016,88:157-169. |
[1] | 郑哲, 胡庆浩, 刘青山, 冷聪. 量化权值激活的生成对抗网络 Quantizing Weights and Activations in Generative Adversarial Networks 计算机科学, 2020, 47(5): 144-148. https://doi.org/10.11896/jsjkx.190700176 |
[2] | 唐文,吴雷. 基于遗传算法的分段Chen系统的参数估计 Parameter Estimation for Piecewise-linear Chen System Based on Genetic Algorithm 计算机科学, 2015, 42(Z11): 83-85. |
[3] | 周蓉,叶春明,谢阳,陈君兰. 基于混沌粒子群算法的多目标多执行模式项目调度问题研究 Research of Multi-objective and Multi-mode Project Scheduling Problem Based on Chaos Particle Swam Optimization 计算机科学, 2013, 40(4): 259-262. |
[4] | 陈君兰,叶春明. 粒子群优化算法在柔性资源受限项目调度中的研究 Flexible-resource Constrained Project Scheduling Research Based on Particle Swarm Optimization 计算机科学, 2013, 40(2): 241-244. |
[5] | 薛峰,屈代明,朱光喜,刘立. 资源受限的认知无线电系统优化合作频谱感知算法 Optimal Cooperative Spectrum Sensing Algorithm of the Resource Constrained Cognitive Radio Networks 计算机科学, 2010, 37(9): 54-56. |
[6] | 赵刚 杨宗凯 何建华. 基于感知运动能量模型的MPEG-21数字项适配 计算机科学, 2005, 32(7): 131-134. |
|