求解柔性资源受限项目调度问题的多种群遗传算法

doi:10.11896/JsJkx.190900123

摘要/Abstract

摘要： 柔性资源普遍存在于制造业生产制造的各个环节中,提高了资源利用率和生产效益。以柔性资源为研究对象,建立了以最小化项目完成工期为目标的柔性资源受限项目调度问题的数学模型。针对现有标准遗传算法过早地收敛从而使整个遗传搜索无法求解出全局最优值的缺陷,提出了一种改进的多种群遗传算法来求解该问题模型。算法对作业优先级列表编码,引入交叉移民算子实现多种群间的协同进化,在解码过程中运用一种启发式柔性资源技能分配算法为作业分配资源,同时通过改进的串行调度生成方案对作业调度。最后通过标准算例库PSPLIB进行数值试验,验证了所提算法求解该问题的有效性。

关键词: 多种群遗传算法, 柔性资源, 项目调度, 资源受限

Abstract: Multi-skill resource resource is popularly existing in the process of production and manufacturing,which improves resource utilization and production efficiency.This paper makes the multi-skill resource as the obJect and presents a mathematical model of multi-skill resource-constrained proJect scheduling problem (MSRCPSP) with the obJective of minimizing the makespan of the proJect.In order to solve the disadvantage that the existing genetic algorithm converges prematurely and the whole algorithm cannot solve the global optimal value,an improved multi-population genetic algorithm is proposed to solve the problem model.The algorithm is designed to code Job priority list and introduced the cross immigration operator to promote the co-evolution of different groups.In the decoding process,a heuristic flexible resource skill allocation algorithm is used to allocate resources for Jobs,and an improved serial scheduling generation scheme is used to schedule Jobs.Finally,numerical experiments are carried out with standard case library PSPLIB to verify the effectiveness of the proposed algorithm in solving MSRCPSP.

Key words: Multi-population genetic algorithm, Multi-skill resource, ProJect scheduling, Resource constrained

中图分类号:

TP29

姚敏. 求解柔性资源受限项目调度问题的多种群遗传算法[J]. 计算机科学, 2020, 47(6A): 124-129. https://doi.org/10.11896/JsJkx.190900123

YAO Min. Multi-population Genetic Algorithm for Multi-skill Resource-constrained ProJect Scheduling Problem[J]. Computer Science, 2020, 47(6A): 124-129. https://doi.org/10.11896/JsJkx.190900123

参考文献

[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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed