Computer Science ›› 2020, Vol. 47 ›› Issue (6A): 124-129.doi: 10.11896/JsJkx.190900123

• Artificial Intelligence • Previous Articles     Next Articles

Multi-population Genetic Algorithm for Multi-skill Resource-constrained ProJect Scheduling Problem

YAO Min   

  1. Department of Information Engineering,Datong Vocational and Technical College of Coal,Datong,Shanxi 037003,China
  • Published:2020-07-07
  • About author:YAO Min, born in 1982, lecturer.Her main research interests include computerapplication, data center network, cloud computing and computer software.

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

CLC Number: 

  • TP29
[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] ZHOU Rong,YE Chun-ming,XIE Yang and CHEN Jun-lan. Research of Multi-objective and Multi-mode Project Scheduling Problem Based on Chaos Particle Swam Optimization [J]. Computer Science, 2013, 40(4): 259-262.
[2] . Flexible-resource Constrained Project Scheduling Research Based on Particle Swarm Optimization [J]. Computer Science, 2013, 40(2): 241-244.
[3] XUE Feng,QU Dai-ming,ZHU Guang-xi,LIU Li. Optimal Cooperative Spectrum Sensing Algorithm of the Resource Constrained Cognitive Radio Networks [J]. Computer Science, 2010, 37(9): 54-56.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!