柔性资源受限的多模式项目调度问题研究
|
摘要
本研究将资源受限的多模式项目调度问题中的可更新资源拓展为柔性资源,建立了柔性资源受限的多模式项目调度问题(flexible resource-constrainedmulti-mode proiect scheduling problem,简称FRCMPSP)的数学模型,并证明了该问题是强NP-hard问题。FRCMPSP的主要特点是项目活动具有时序关系约束和柔性资源约束、每个活动具有多种执行模式且每种执行模式对应着不同种类的能力需求和活动工期、资源柔性体现在资源具有多种不同的能力。
首先,探讨了已有资源受限的项目调度问题的算例生成器PROGEN的实现机制,对其进行改造以能生成FRCMPSP算例,并针对PROGEN的不足构造了专用于生成FRCMPSP的算例生成器FGEN。FGEN能够根据更多的算例特征参数系统地构造算例。
其次,探讨了FRCMPSP的求解方法。设计了该问题的全枚举和隐枚举算法。通过对枚举算法的分析发现FRCMPSP的求解瓶颈存在于3个方面,分别是活动拓扑排序组合、活动执行模式组合以及单位能力柔性资源配置组合。利用PROGEN系统地生成了项目非虚活动数目为10的2500个算例,使用Xpress-MP软件包进行了精确求解,并分析了算例特征参数与算例求解难度和算例项目完工时间之间的关系。在此基础之上,设计了求解FRCMPSP的基于优先规则的三阶段启发式算法,将3种模式选择规则、5种活动优先规则和3种资源配置规则所组合而成的45种启发式规则的求解结果与精确解进行了比较。结果表明活动工期最短模式优先—最小最迟开始时间活动优先—最少能力数资源优先规则是最好规则。
再次,使用FGEN系统地构造了38880个FRCMPSP算例,并选取最好规则即活动工期最短模式优先—最小最迟开始时间活动优先—最少能力数资源优先构建了启发式方法对算例进行了求解,进一步探讨了算例特征参数与算例求解难度和算例项目完工时间之间的关系,对资源柔性的价值进行了分析。指出资源柔性的价值大小并不仅仅取决于资源柔性值的大小,更取决于资源能力的结构。
本论文的研究能够为项目管理中柔性资源的优化配置提供理论依据,为相关调度软件的开发提供研究基础,进而使得基于能力的项目管理得以实现。
Along with the renewable resource in the resource-constrained multi-mode project scheduling problem(RCMPSP) is extended to flexible resource,the mathematic model of the flexible resource-constrained multi-mode project scheduling problem (FRCMPSP) is put forward in this dissertation.FRCMPSP is a strong NP-hard problem in which the jobs of the project are constrained with precedence and flexible resources,every job has several different execution modes and each execution mode has various capability demands and durations,the resource flexibility means resource has various capabilities.FRCMPSP considers the variety of job execution modes and resources' assignment together.
To begin with,the mechanism of PROGEN,which is a benchmark instance generator for the resource-constrained project scheduling problem(RCPSP),is analyzed in detail.Some improvements were made on PROGEN to transfer the benchmark instance for RCPSP to that for FRCMPSP.In addition,to overcome the imperfection of PROGEN,a new benchmark instance generator for FRCMPSP is constructed and named as FGEN.FGEN can generate FRCMPSP benchmark instances with more features.
In the next place,the solving methods for FRCMPSP are explored.Enumeration and implicit enumeration algorithms for FRCMPSP are developed in which implicit enumeration algorithm enumerate the identical flexible resource only once.Through the analysis of enumeration and implicit enumeration algorithms,it is found that the bottleneck of solving the FRCMPSP exists in three aspects which are the combinations of jobs' topological queue,jobs' execution modes,and unit capabilities' resource assignment.Then,2500 benchmark instances with 10 non-dummy jobs every project are generated with PROGEN.They are solved with Xpress-MP exactly and the influences of benchmark instances' parameters on the benchmark instances' solving difficulty and project makespan are analyzed.Based on the research above, 45 priority-based rules are constructed by the combination of three mode selection rules,five job priority rules and three resource assignment rules.It has been showed that the rule combined with mode with shortest job duration first,job with minimum latest start time first,and resource with minimum capability number first outperforms other ones.
Finally,38880 benchmark instances for FRCMPSP are generated with FGEN.A heuristic algorithm is put forward to solve these benchmark instances with the priority rule combined with mode with shortest job duration first,job with minimum latest start time first,and resource with minimum capability number first.The influences of benchmark instances' parameters on benchmark instances' solving difficulty and project makespan are discussed,the value of resource flexibility is analyzed and it is pointed out that the value of resource flexibility relies not only on the value of resource flexibility but also the construction of the resource's capabilities.
This research will provide theory basis for the optimum assignment of flexible resource in project management and foundation for the development of relative scheduling software,which will make the capability-based project management come into realization.
首先,探讨了已有资源受限的项目调度问题的算例生成器PROGEN的实现机制,对其进行改造以能生成FRCMPSP算例,并针对PROGEN的不足构造了专用于生成FRCMPSP的算例生成器FGEN。FGEN能够根据更多的算例特征参数系统地构造算例。
其次,探讨了FRCMPSP的求解方法。设计了该问题的全枚举和隐枚举算法。通过对枚举算法的分析发现FRCMPSP的求解瓶颈存在于3个方面,分别是活动拓扑排序组合、活动执行模式组合以及单位能力柔性资源配置组合。利用PROGEN系统地生成了项目非虚活动数目为10的2500个算例,使用Xpress-MP软件包进行了精确求解,并分析了算例特征参数与算例求解难度和算例项目完工时间之间的关系。在此基础之上,设计了求解FRCMPSP的基于优先规则的三阶段启发式算法,将3种模式选择规则、5种活动优先规则和3种资源配置规则所组合而成的45种启发式规则的求解结果与精确解进行了比较。结果表明活动工期最短模式优先—最小最迟开始时间活动优先—最少能力数资源优先规则是最好规则。
再次,使用FGEN系统地构造了38880个FRCMPSP算例,并选取最好规则即活动工期最短模式优先—最小最迟开始时间活动优先—最少能力数资源优先构建了启发式方法对算例进行了求解,进一步探讨了算例特征参数与算例求解难度和算例项目完工时间之间的关系,对资源柔性的价值进行了分析。指出资源柔性的价值大小并不仅仅取决于资源柔性值的大小,更取决于资源能力的结构。
本论文的研究能够为项目管理中柔性资源的优化配置提供理论依据,为相关调度软件的开发提供研究基础,进而使得基于能力的项目管理得以实现。
Along with the renewable resource in the resource-constrained multi-mode project scheduling problem(RCMPSP) is extended to flexible resource,the mathematic model of the flexible resource-constrained multi-mode project scheduling problem (FRCMPSP) is put forward in this dissertation.FRCMPSP is a strong NP-hard problem in which the jobs of the project are constrained with precedence and flexible resources,every job has several different execution modes and each execution mode has various capability demands and durations,the resource flexibility means resource has various capabilities.FRCMPSP considers the variety of job execution modes and resources' assignment together.
To begin with,the mechanism of PROGEN,which is a benchmark instance generator for the resource-constrained project scheduling problem(RCPSP),is analyzed in detail.Some improvements were made on PROGEN to transfer the benchmark instance for RCPSP to that for FRCMPSP.In addition,to overcome the imperfection of PROGEN,a new benchmark instance generator for FRCMPSP is constructed and named as FGEN.FGEN can generate FRCMPSP benchmark instances with more features.
In the next place,the solving methods for FRCMPSP are explored.Enumeration and implicit enumeration algorithms for FRCMPSP are developed in which implicit enumeration algorithm enumerate the identical flexible resource only once.Through the analysis of enumeration and implicit enumeration algorithms,it is found that the bottleneck of solving the FRCMPSP exists in three aspects which are the combinations of jobs' topological queue,jobs' execution modes,and unit capabilities' resource assignment.Then,2500 benchmark instances with 10 non-dummy jobs every project are generated with PROGEN.They are solved with Xpress-MP exactly and the influences of benchmark instances' parameters on the benchmark instances' solving difficulty and project makespan are analyzed.Based on the research above, 45 priority-based rules are constructed by the combination of three mode selection rules,five job priority rules and three resource assignment rules.It has been showed that the rule combined with mode with shortest job duration first,job with minimum latest start time first,and resource with minimum capability number first outperforms other ones.
Finally,38880 benchmark instances for FRCMPSP are generated with FGEN.A heuristic algorithm is put forward to solve these benchmark instances with the priority rule combined with mode with shortest job duration first,job with minimum latest start time first,and resource with minimum capability number first.The influences of benchmark instances' parameters on benchmark instances' solving difficulty and project makespan are discussed,the value of resource flexibility is analyzed and it is pointed out that the value of resource flexibility relies not only on the value of resource flexibility but also the construction of the resource's capabilities.
This research will provide theory basis for the optimum assignment of flexible resource in project management and foundation for the development of relative scheduling software,which will make the capability-based project management come into realization.
引文
[1]関根智明.计划评审法与关键路径法[M].李静,译.北京:机械工业出版社,1983
[2]Slowinski R.Two approaches to problems of resource allocation among project activities:A comparative study[J].Journal of the Operational Research Society,1980,31(8):711-723
[3]Slowinski R.Multiobjective network scheduling with efficient use of renewable and nonrenewable resource[J].European Journal of Operational Research,1981,7(3):265-273
[4]Weglarz J.Project scheduling with discrete and continuous resource[J].IEEE Transactions on Systems,Man,and Cybernetics,1979,9(10):644-650
[5]Weglarz J.On certain models of resource allocation problem[J].Kybernetics,1980,9(1):61-66
[6]Harver R T,Patterson J H.An implicit enumeration algorithm for the time\cost trade-off problem in project network analysis[J].Foundations of Control Engineering,1979,4(2):107-117
[7]Demeulemeester E L.Minimizing resource availability costs in time-limited project networks [J].Management Science,1995,41(10):1590-1598
[8]刘士新,王梦光.一种求解多执行模式工程调度中资源水平问题的遗传算法[J].控制与决策,2001,16(1):111-113
[9]De Reyck B,Herroelen W.A branch-and-bound procedure for the resource-constrained project scheduling problem with generalized procedure relations[J].European Journal of Operational Research,1998,111(1):152-174
[10]Russell A H.Cash flows in networks[J].Management Science,1970,16(5):357-373
[11]Russell A H.A comparison of heuristics for scheduling projects with cash flows and resource restrictions[J].Management Science,1986,32(10):1291-1300
[12]Mohanthy R P and Siddiq M K.Multiple projects multiple resources constrained scheduling:Some studies[J].International Journal of Production Research,1989,27(2):261-280
[13]Herroelen W,De Reyck B,Demeulemeester E.Resource-constrained project scheduling:A survey of recent developments[J].Computers&Operations Research,1998,25(4):279-302
[14]刘士新.项目优化调度理论与方法[M].北京:机械工业出版社,2007
[15]Johnson T J R.An algorithm for the resource-constrained project scheduling problem,Ph.D.Disseration.MIT,Boston,USA,1967
[16]Christofides N,Alvarez-Valdes R,Tamari J M.Project scheduling with resource constraints:A branch and bound approach[J].European Journal of Operational Research,1987,29(3):262-273
[17]Demeulemeester E L,Herroelen W S.A branch-and-bound procedure for the multiple resource-constrained project scheduling problem[J].Management Science,1992,38(12):1803-1818
[18]Patterson J H.A comparison of exact approaches for solving the multiple constrained resource project scheduling problem[J].Management Science,1984,30(7):854-867
[19]Kolisch R,Sprecher A.PSPLIB-A project scheduling problem library[J].European Journal of the Operational Research,1996,96(1):205-216
[20]Demeulemeester E L,Herroelen W S.New benchmark results for the resource-constrained project scheduling problem[J].Management Science,1997,43(11):1485-1492
[21]Stinson J P,Davis E W,Khumawala B M.Multiple resource-constrained scheduling using branch and bound[J].AIIE Transactions,1978,10(3):252-259
[22]Mingozzi A,Maniezzo V,Ricciardelli S,et al.An exact algorithm for the resource-constrained project scheduling problem based on a new mathematical formulation[J].Management Science,1998,44(5):714-729
[23]Brucker P,Knust S,Schoo A,et al.A branch and bound algorithm for the resource-constrained project scheduling problem[J].European Journal of Operational Research,1998,107(2):272-288
[24]Patterson J H,Slowinski R,Talbot F B,et al.An algorithm for a general class of precedence and resource-constrained scheduling problem.In Slowinski R,Weglarz J(eds.),Advances in Project scheduling[M].Amsterdam:Elsevier,1989:3-28
[25]Sprecher A.Scheduling resource-constrained projects competitively at modest memory requirements[J].Management Science,2000,46(5):710-723
[26]Nazareth T,Verma S,Bhattacharya S,et al.The multiple resource-constrained project scheduling problem:A breadth-first approach[J].European Journal of Operational Research,1999,112(2):347-366
[27]Simpson W P,Patterson J H.A multiple-tree search procedures for the resource-constrained project scheduling problem[J].European Journal of Operational Research,1996,89(3):525-542
[28]Klein R,Scholl A.Computing lower bounds by destructive improvement:An application to resource-constrained project scheduling[J].European Journal of Operational Research,1999,112(2):322-346
[29]Bruker P,Knust S.A linear programming and constrained propagation-based lower bound for the RCPSP[J].European Journal of Operational Research,2000,127(2):355-362
[30]Kelley J E Jr.The critical path method:Resource planning and scheduling.In Muth J F,Thompson G L(eds.),Industrial Scheduling[M],Englewood Cliffs:Prentice-Hall,1963
[31]Kolisch R,Hartmann S.Heuristic algorithms for solving the resource-constrained project scheduling problem:Classification and computational analysis.In Weglarz J.,(ed).Handbook on Recent Advances in Project Scheduling[M].Amsterdam:Kluwer,1999
[32]Hartmann S,Kolisch R.Experimental Evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem[J].European Journal of Operational Research,2000,127(2):394-407
[33]Boctor F F.Some efficient multi-heuristic procedures for resource-constrained project scheduling[J].European Journal of Operational Research,1990,49(1):3-13
[34]Cooper D F.Heuristics for scheduling resource-constrained projects:an experimental investigation[J].Management Science,1976,22(11):1186-1194
[35]Drexl A.Scheduling of project networks by job assignment[J].Management Science,1991,37(12):1590-1602
[36]Schirmer A.Resource-constrained project scheduling:An evaluation of adaptive control schemes for pammeterized sampling heuristics[J].International Journal of Production Research,2001,39(7):1343-1365
[37]Schirmer A.Case-based reasoning and improved adaptive search for project scheduling[J].Naval Research Logistics,2000,47(3):201-222
[38]Lee J K,K.im Y D,Search heuristics for resource constrained project scheduling[J].Journal of the Operational Research Society,1996,47(3):678-689
[39]Cho J H,Kim Y D.A simulated annealing algorithm for resource constrained project scheduling problem[J].Journal of Opeartional Research Society,1997,48(7):736-744
[40]Baar T,Brucker P,Knust S.Tabu-search algorithms and lower bounds for the resource-constrained project scheduling problem.In Voss S,Martello S,Osman I,et al(eds.),Meta-heuristics:Advances and trends in Local Search Paradigms for Optimization[M].Amsterdam:Kluwer,1998
[41]Bouleimen K,Lecocq H,A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version[J].European Journal of Operational Research,2003,149(2):268-281
[42]Hartmann S.A competitive genetic algorithm for resource-constrained project scheduling[J].Naval Research Logistics,1998,49(5):733-750
[43]刘士新,王梦光,唐加福.一种求解资源受限工程调度问题的遗传算法[J].系统工程学报,2002,17(1):1-7
[44]Liu Shixin,Wang Mengguang.An object-oriented methodology for solving the RCPSPs with heuristics and metaheuristics[J].Production Planning&Control,2000,11(5):434-442
[45]Elmaghraby S E.Activity networks:Project planning and control by network models[M].New York:Wiley,1977
[46]Patterson J H,Slowinski R,Talbot F B,et al.An algorithm for a general class of precedence and resource-constrained scheduling problem.In Slowinski R,Weglarz J(eds.),Advances in Project Scheduling[M],Amsterdam:Elsevier,1989
[47]Patterson J H,Talbot F B,Slowinski R,et al.Computational experience with a backtracking algorithm for solving a general class of precedence and resource-constrained scheduling problems[J].European Journal of Operational Research,1990,49(1):768-798
[48]Speranza M G,Vercellis c.Hierarchical models for multi-project planning and scheduling[J].European Journal of Operational Research,1993,64(2):312-325
[49]Sprecher A,Hartmann S.Drexl A.An exact algorithm for project scheduling with multiple modes[J].OR Spectrum,1997,19(3):195-203
[50]Sprecher A,Drexl A.Multi-mode resource-constrained project scheduling by a simple,general and powerful sequencing algorithm[J].European Journal of Operational Research,1998,107(2):431-450
[51]Hartmann S,Drexl A.Project scheduling with multiple modes:A comparison of exact algorithms[J].Networks,1998,32(4):283-297
[52]Boctor F F.Heuristics for scheduling projects with resource restrictions and several resource-duration modes[J].International Journal of Production Research,1993,31(11):2547-2558
[53]Boctor F F.A new and efficient heuristic for scheduling projects with resource restrictions and multiple execution modes[J].European Journal of Operational Research,1996,90(2):349-361
[54](O|¨)zdamar L,Ulusoy G.A local constraint based analysis approach to project scheduling under general resource constraints[J].European Journal of Operational Research,1994,79(2):287-298
[55]Ulusoy G;(O|¨)zdamar L.A framework for an interactive project scheduling system under limited resources[J].European Journal of Operational Research,1996,90(2):362-375
[56](O|¨)zdamar L,A genetic algorithm approach to a general category project scheduling problem[J].IEEE Transactions on Systems,Man,and Cybemetics,Part C:Applications and Reviews,1999,29(1):44-59
[57]Mori M,Tseng C C.A genetic algorithm for multi-mode resource constrained project scheduling problem[J].European Journal of Operational Research,1997,100(1):134-141
[58]Hartmann S.Project scheduling with multiple modes:A genetic algorithm[J].Annals of Operations Research,2001,102(1-4):111-135
[59]刘士新,王梦光.多执行模式资源受限工程调度问题的优化算法[J].系统工程学报, 2001,16(1):55-60
[60]J(?)zefowska J,Mika M,R(?)zycki R,Walig(?)ra G,Weglarz J.Simulated annealing for multi-mode resource-constrained project scheduling[J].Annals of Operations Research,2001,102(1-4):137-155
[61]Bouleimen K L,Lecocq H.A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version[J].European Journal of Operational Research,2003,149(2):268-281
[62]Kolisch R,Hartmann S.Local search for nonpreemptive multi-mode resource-constrained project scheduling[J].IIE Transactions,1997,29(11):987-999
[63]Jarboui B,Damak N,Siarry P,Rebai A.A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems[J].Applied Mathematics and Computation,2008,195(1):299-308
[64]Shi D,Daniels R L.A Survey of manufacturing flexibility:Implications for E-business Flexibility[J].IBM Systems Journal,2003,42(3):414-426.
[65]Daniels R L and Mazzola J B.Flow shop scheduling with resource flexibility[J].Operations Research,1994,42(3):504-522
[66]Daniels R L,Hoopes B J,and Mazzola J B.Scheduling parallel manufacturing cells with resource flexibility[J].Management Science,1996,42(9):1260-1276
[67]Olafsson S and Shi L.A method for scheduling in parallel manufacturing systems with flexible resources[J].IIE transactions,2000,32(2):135-146
[68]Daniels R L,Mazzola J B,and Shi D.Flow shop scheduling with partial resource flexibility [J].Management Science,2004,50(5):658-669
[69]Luo R,Huang M.Parallel-machine scheduling with partial resource flexibility[C].The Proceedings of the 11th International Conference on Industrial Engineering and Engineering Management.Beijing:China Machine Press,2005:326-331
[70]罗荣桂,吴兵.作业车间人力资源柔性研究[J].武汉理工大学学报,2006,28(6):121-123
[71]Vairaktarakis G L.The value of resource flexibility in the resource-constrained job assignment problem[J].Management Science,2003,49(6):718-732
[72]Sleator D D.An O(nm log n) algorithm for maximum network flow.Ph.D.dissertation,Stanford University,Stanford,CA,1980
[73]Bellenguez O.M(?)thodes de R(?)solution pour un problem de gestion de projet multi-comp(?)tence.Ph.D.dissertation,Universit(?) Francqis Rabelais Tours,2006
[74]Bellenguez O and N(?)ron E.Methods for solving the multi-skill project scheduling problem[C].9~(th) International Workshop on Project Management and Scheduling,Nancy, 2004,66-69
[75]Bellenguez O and N(?)ron E.Lower bounds for the multi-skill project scheduling problem with hierarchical levels of skills[C].Practice and Theory of Automated Timetabling,Pttsburgh,PA,2004,429-432
[76]Bellenguez O and N(?)ron E.An exact method for solving the multi-skill project scheduling problem[C].Operations Research Conference,Tilburg,2004,97-98
[77]Bellenguez O and N(?)ron E.Lower bounds for the multi-skill project scheduling problem with hierarchical levels of skills,Lecture Notes in Computer Science:Practice and Theory of Automated Timetabling V:5~(th) International Comference,PATAT2004,Pittsburgh,PA,USA,August 18-20,2004,Revised Selected Papers,Springer-Verlag GmbH,2005,229-243
[78]Bellenguez O and N(?)ron E.Exact mtheods for a fixed job problem.Models and Algorithms for Planning and Scheduling Problems,Siena,2005
[79]Artigues C.Resource-Constrained Project Scheduling:Models,Algorithms,Extensions and Application[M].USA:John Wiley&Sons,inc.2007
[80]N(?)ron E and Baptista D.Heuristics for the multi-skill project scheduling problem[C].International Symposium on Combinatiorial Optimization,Paris,France,2002
[81]Carlier J and B latapie.Une m(?)thode arborescente pour r(?)soudre les probl(?)mes cumulatifs[J].RAIRO-Recherche Op(?)rationnelle,1991,25(3):311-340
[82]Carlier J.Scheduling jobs with release dates and tails on identical machines to minimize the makespan[J].European Journal of Opeartional Research,1987,29(3):298-306
[83]Kolen A and L Kroon.On the computational complexity of maximum class scheduling[J].European Journal of Operational Research,1991,54(1),23-28
[84]Kardrou Y,Najid N M.A new heuristic to solve RCPSP with multiple execution modes and multi-skilled labor[C].In:Proceedings of IMACS Multicomference on “Computational Engineering in Systems Applications”(CESA),October,2006,Beijing
[85]Kardrou Y,Najid N M,2007.Tabu search algorithm for the MRCPSP with multi-skilled labor,working paper,CPI'2007,Rabat,Maroc
[86]黄敏镁.具有柔性资源约束的调度问题研究:[博士学位论文].武汉:武汉理工大学管理学院,2007
[87]黄敏镁,罗荣桂,袁际军.求解置换调度问题的改进混合遗传算法[J].中国机械工程,2006,17(16):1707-1710
[88]黄敏镁,罗荣桂,袁际军.具有学习效果的两机流水车间调度启发式算法研究.武汉理工大学学报(交通科学与工程版),2007,31(5):931-934
[89]Minmei Huang,Ronggui Luo and Jijun Yuan.Heuristic-tabu-genetic algorithm based method for flowshop scheduling to minimize flowtime[C].In:Proceedings of The 6th World Congress on Intelligent Control and Automation,IEEE,2006
[90]Ronggui Luo,Minmei Huang.Parallel-machine scheduling with partial resource flexibility[C].In:Proceedings of the 11th International Conference on Industrial Engineering and Engineering Management.China Machine Press,2005
[91]谢政.网络算法与复杂性理论(第二版)[M].长沙:国防科技大学出版社,2003
[92]Cordeau J F,Laporte G.Pasin F,et al.Scheduling technicians and tasks in a telecommunications company,2008,working paper
[93]Dutot P.F.,Laugier A.,and Bustos A.M.Technicians and interventions scheduling for telecommunications.France Telecom R&D,August,2006
[94]Garey M R and Johnson D S.Computers and Intractability:A Guide to the Theory of NP-Completeness[M].Freeman,San Francisco,1979
[95]Demeulemeester E L.A random activity network generator[J].Operations Research,1993,41(5):972-980
[96]Demeulemeester E L,Vanhoucke M,Herroelen W S.RanGen:A random network generator for activity-on-the-node networks[J].Journal of Scheduling,2003,6(1):17-38
[97]刘士新,王梦光.多资源受限工程网络的随机生成器[J].东北大学学报,1997,18(5):494-497
[98]Davis E W,Patterson J H.A comparison of heuristic and optimum solutions in resource-constrained project scheduling[J].Management Science,1975,21(8):944-55
[99]Schrage L.A more portable fortran random number generator[J].ACM Transactions on Mathematical Software,1979,5(2):132-138
[100]TL Pascoe T L.An experimental comparison of heuristic methods for allocating resources.PhD Thesis,University of Cambridge,UK,1965
[101]Davis E W.Project network stmmary measures constrained-resource scheduling[J].AIIE Transactions(since 1985:IIE Transactions),1975,7(2):132-142
[102]Kaimann R A.Coefficients of network complexity[J].Management Science,1974,21(2):172-177
[103]Thesen A.Measures of the restrictiveness of project networks[J].Networks,1977,7(3):193-208
[104]Elmaghraby S E.Activity Networks:Project Planning and Control by Network Models[M].New York:Wiley,1977
[105]Cooper D F.Heuristics for scheduling resource-constrained projects:An experimental investigation[J].Management Science,1976,22(11):1186-1194
[2]Slowinski R.Two approaches to problems of resource allocation among project activities:A comparative study[J].Journal of the Operational Research Society,1980,31(8):711-723
[3]Slowinski R.Multiobjective network scheduling with efficient use of renewable and nonrenewable resource[J].European Journal of Operational Research,1981,7(3):265-273
[4]Weglarz J.Project scheduling with discrete and continuous resource[J].IEEE Transactions on Systems,Man,and Cybernetics,1979,9(10):644-650
[5]Weglarz J.On certain models of resource allocation problem[J].Kybernetics,1980,9(1):61-66
[6]Harver R T,Patterson J H.An implicit enumeration algorithm for the time\cost trade-off problem in project network analysis[J].Foundations of Control Engineering,1979,4(2):107-117
[7]Demeulemeester E L.Minimizing resource availability costs in time-limited project networks [J].Management Science,1995,41(10):1590-1598
[8]刘士新,王梦光.一种求解多执行模式工程调度中资源水平问题的遗传算法[J].控制与决策,2001,16(1):111-113
[9]De Reyck B,Herroelen W.A branch-and-bound procedure for the resource-constrained project scheduling problem with generalized procedure relations[J].European Journal of Operational Research,1998,111(1):152-174
[10]Russell A H.Cash flows in networks[J].Management Science,1970,16(5):357-373
[11]Russell A H.A comparison of heuristics for scheduling projects with cash flows and resource restrictions[J].Management Science,1986,32(10):1291-1300
[12]Mohanthy R P and Siddiq M K.Multiple projects multiple resources constrained scheduling:Some studies[J].International Journal of Production Research,1989,27(2):261-280
[13]Herroelen W,De Reyck B,Demeulemeester E.Resource-constrained project scheduling:A survey of recent developments[J].Computers&Operations Research,1998,25(4):279-302
[14]刘士新.项目优化调度理论与方法[M].北京:机械工业出版社,2007
[15]Johnson T J R.An algorithm for the resource-constrained project scheduling problem,Ph.D.Disseration.MIT,Boston,USA,1967
[16]Christofides N,Alvarez-Valdes R,Tamari J M.Project scheduling with resource constraints:A branch and bound approach[J].European Journal of Operational Research,1987,29(3):262-273
[17]Demeulemeester E L,Herroelen W S.A branch-and-bound procedure for the multiple resource-constrained project scheduling problem[J].Management Science,1992,38(12):1803-1818
[18]Patterson J H.A comparison of exact approaches for solving the multiple constrained resource project scheduling problem[J].Management Science,1984,30(7):854-867
[19]Kolisch R,Sprecher A.PSPLIB-A project scheduling problem library[J].European Journal of the Operational Research,1996,96(1):205-216
[20]Demeulemeester E L,Herroelen W S.New benchmark results for the resource-constrained project scheduling problem[J].Management Science,1997,43(11):1485-1492
[21]Stinson J P,Davis E W,Khumawala B M.Multiple resource-constrained scheduling using branch and bound[J].AIIE Transactions,1978,10(3):252-259
[22]Mingozzi A,Maniezzo V,Ricciardelli S,et al.An exact algorithm for the resource-constrained project scheduling problem based on a new mathematical formulation[J].Management Science,1998,44(5):714-729
[23]Brucker P,Knust S,Schoo A,et al.A branch and bound algorithm for the resource-constrained project scheduling problem[J].European Journal of Operational Research,1998,107(2):272-288
[24]Patterson J H,Slowinski R,Talbot F B,et al.An algorithm for a general class of precedence and resource-constrained scheduling problem.In Slowinski R,Weglarz J(eds.),Advances in Project scheduling[M].Amsterdam:Elsevier,1989:3-28
[25]Sprecher A.Scheduling resource-constrained projects competitively at modest memory requirements[J].Management Science,2000,46(5):710-723
[26]Nazareth T,Verma S,Bhattacharya S,et al.The multiple resource-constrained project scheduling problem:A breadth-first approach[J].European Journal of Operational Research,1999,112(2):347-366
[27]Simpson W P,Patterson J H.A multiple-tree search procedures for the resource-constrained project scheduling problem[J].European Journal of Operational Research,1996,89(3):525-542
[28]Klein R,Scholl A.Computing lower bounds by destructive improvement:An application to resource-constrained project scheduling[J].European Journal of Operational Research,1999,112(2):322-346
[29]Bruker P,Knust S.A linear programming and constrained propagation-based lower bound for the RCPSP[J].European Journal of Operational Research,2000,127(2):355-362
[30]Kelley J E Jr.The critical path method:Resource planning and scheduling.In Muth J F,Thompson G L(eds.),Industrial Scheduling[M],Englewood Cliffs:Prentice-Hall,1963
[31]Kolisch R,Hartmann S.Heuristic algorithms for solving the resource-constrained project scheduling problem:Classification and computational analysis.In Weglarz J.,(ed).Handbook on Recent Advances in Project Scheduling[M].Amsterdam:Kluwer,1999
[32]Hartmann S,Kolisch R.Experimental Evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem[J].European Journal of Operational Research,2000,127(2):394-407
[33]Boctor F F.Some efficient multi-heuristic procedures for resource-constrained project scheduling[J].European Journal of Operational Research,1990,49(1):3-13
[34]Cooper D F.Heuristics for scheduling resource-constrained projects:an experimental investigation[J].Management Science,1976,22(11):1186-1194
[35]Drexl A.Scheduling of project networks by job assignment[J].Management Science,1991,37(12):1590-1602
[36]Schirmer A.Resource-constrained project scheduling:An evaluation of adaptive control schemes for pammeterized sampling heuristics[J].International Journal of Production Research,2001,39(7):1343-1365
[37]Schirmer A.Case-based reasoning and improved adaptive search for project scheduling[J].Naval Research Logistics,2000,47(3):201-222
[38]Lee J K,K.im Y D,Search heuristics for resource constrained project scheduling[J].Journal of the Operational Research Society,1996,47(3):678-689
[39]Cho J H,Kim Y D.A simulated annealing algorithm for resource constrained project scheduling problem[J].Journal of Opeartional Research Society,1997,48(7):736-744
[40]Baar T,Brucker P,Knust S.Tabu-search algorithms and lower bounds for the resource-constrained project scheduling problem.In Voss S,Martello S,Osman I,et al(eds.),Meta-heuristics:Advances and trends in Local Search Paradigms for Optimization[M].Amsterdam:Kluwer,1998
[41]Bouleimen K,Lecocq H,A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version[J].European Journal of Operational Research,2003,149(2):268-281
[42]Hartmann S.A competitive genetic algorithm for resource-constrained project scheduling[J].Naval Research Logistics,1998,49(5):733-750
[43]刘士新,王梦光,唐加福.一种求解资源受限工程调度问题的遗传算法[J].系统工程学报,2002,17(1):1-7
[44]Liu Shixin,Wang Mengguang.An object-oriented methodology for solving the RCPSPs with heuristics and metaheuristics[J].Production Planning&Control,2000,11(5):434-442
[45]Elmaghraby S E.Activity networks:Project planning and control by network models[M].New York:Wiley,1977
[46]Patterson J H,Slowinski R,Talbot F B,et al.An algorithm for a general class of precedence and resource-constrained scheduling problem.In Slowinski R,Weglarz J(eds.),Advances in Project Scheduling[M],Amsterdam:Elsevier,1989
[47]Patterson J H,Talbot F B,Slowinski R,et al.Computational experience with a backtracking algorithm for solving a general class of precedence and resource-constrained scheduling problems[J].European Journal of Operational Research,1990,49(1):768-798
[48]Speranza M G,Vercellis c.Hierarchical models for multi-project planning and scheduling[J].European Journal of Operational Research,1993,64(2):312-325
[49]Sprecher A,Hartmann S.Drexl A.An exact algorithm for project scheduling with multiple modes[J].OR Spectrum,1997,19(3):195-203
[50]Sprecher A,Drexl A.Multi-mode resource-constrained project scheduling by a simple,general and powerful sequencing algorithm[J].European Journal of Operational Research,1998,107(2):431-450
[51]Hartmann S,Drexl A.Project scheduling with multiple modes:A comparison of exact algorithms[J].Networks,1998,32(4):283-297
[52]Boctor F F.Heuristics for scheduling projects with resource restrictions and several resource-duration modes[J].International Journal of Production Research,1993,31(11):2547-2558
[53]Boctor F F.A new and efficient heuristic for scheduling projects with resource restrictions and multiple execution modes[J].European Journal of Operational Research,1996,90(2):349-361
[54](O|¨)zdamar L,Ulusoy G.A local constraint based analysis approach to project scheduling under general resource constraints[J].European Journal of Operational Research,1994,79(2):287-298
[55]Ulusoy G;(O|¨)zdamar L.A framework for an interactive project scheduling system under limited resources[J].European Journal of Operational Research,1996,90(2):362-375
[56](O|¨)zdamar L,A genetic algorithm approach to a general category project scheduling problem[J].IEEE Transactions on Systems,Man,and Cybemetics,Part C:Applications and Reviews,1999,29(1):44-59
[57]Mori M,Tseng C C.A genetic algorithm for multi-mode resource constrained project scheduling problem[J].European Journal of Operational Research,1997,100(1):134-141
[58]Hartmann S.Project scheduling with multiple modes:A genetic algorithm[J].Annals of Operations Research,2001,102(1-4):111-135
[59]刘士新,王梦光.多执行模式资源受限工程调度问题的优化算法[J].系统工程学报, 2001,16(1):55-60
[60]J(?)zefowska J,Mika M,R(?)zycki R,Walig(?)ra G,Weglarz J.Simulated annealing for multi-mode resource-constrained project scheduling[J].Annals of Operations Research,2001,102(1-4):137-155
[61]Bouleimen K L,Lecocq H.A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version[J].European Journal of Operational Research,2003,149(2):268-281
[62]Kolisch R,Hartmann S.Local search for nonpreemptive multi-mode resource-constrained project scheduling[J].IIE Transactions,1997,29(11):987-999
[63]Jarboui B,Damak N,Siarry P,Rebai A.A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems[J].Applied Mathematics and Computation,2008,195(1):299-308
[64]Shi D,Daniels R L.A Survey of manufacturing flexibility:Implications for E-business Flexibility[J].IBM Systems Journal,2003,42(3):414-426.
[65]Daniels R L and Mazzola J B.Flow shop scheduling with resource flexibility[J].Operations Research,1994,42(3):504-522
[66]Daniels R L,Hoopes B J,and Mazzola J B.Scheduling parallel manufacturing cells with resource flexibility[J].Management Science,1996,42(9):1260-1276
[67]Olafsson S and Shi L.A method for scheduling in parallel manufacturing systems with flexible resources[J].IIE transactions,2000,32(2):135-146
[68]Daniels R L,Mazzola J B,and Shi D.Flow shop scheduling with partial resource flexibility [J].Management Science,2004,50(5):658-669
[69]Luo R,Huang M.Parallel-machine scheduling with partial resource flexibility[C].The Proceedings of the 11th International Conference on Industrial Engineering and Engineering Management.Beijing:China Machine Press,2005:326-331
[70]罗荣桂,吴兵.作业车间人力资源柔性研究[J].武汉理工大学学报,2006,28(6):121-123
[71]Vairaktarakis G L.The value of resource flexibility in the resource-constrained job assignment problem[J].Management Science,2003,49(6):718-732
[72]Sleator D D.An O(nm log n) algorithm for maximum network flow.Ph.D.dissertation,Stanford University,Stanford,CA,1980
[73]Bellenguez O.M(?)thodes de R(?)solution pour un problem de gestion de projet multi-comp(?)tence.Ph.D.dissertation,Universit(?) Francqis Rabelais Tours,2006
[74]Bellenguez O and N(?)ron E.Methods for solving the multi-skill project scheduling problem[C].9~(th) International Workshop on Project Management and Scheduling,Nancy, 2004,66-69
[75]Bellenguez O and N(?)ron E.Lower bounds for the multi-skill project scheduling problem with hierarchical levels of skills[C].Practice and Theory of Automated Timetabling,Pttsburgh,PA,2004,429-432
[76]Bellenguez O and N(?)ron E.An exact method for solving the multi-skill project scheduling problem[C].Operations Research Conference,Tilburg,2004,97-98
[77]Bellenguez O and N(?)ron E.Lower bounds for the multi-skill project scheduling problem with hierarchical levels of skills,Lecture Notes in Computer Science:Practice and Theory of Automated Timetabling V:5~(th) International Comference,PATAT2004,Pittsburgh,PA,USA,August 18-20,2004,Revised Selected Papers,Springer-Verlag GmbH,2005,229-243
[78]Bellenguez O and N(?)ron E.Exact mtheods for a fixed job problem.Models and Algorithms for Planning and Scheduling Problems,Siena,2005
[79]Artigues C.Resource-Constrained Project Scheduling:Models,Algorithms,Extensions and Application[M].USA:John Wiley&Sons,inc.2007
[80]N(?)ron E and Baptista D.Heuristics for the multi-skill project scheduling problem[C].International Symposium on Combinatiorial Optimization,Paris,France,2002
[81]Carlier J and B latapie.Une m(?)thode arborescente pour r(?)soudre les probl(?)mes cumulatifs[J].RAIRO-Recherche Op(?)rationnelle,1991,25(3):311-340
[82]Carlier J.Scheduling jobs with release dates and tails on identical machines to minimize the makespan[J].European Journal of Opeartional Research,1987,29(3):298-306
[83]Kolen A and L Kroon.On the computational complexity of maximum class scheduling[J].European Journal of Operational Research,1991,54(1),23-28
[84]Kardrou Y,Najid N M.A new heuristic to solve RCPSP with multiple execution modes and multi-skilled labor[C].In:Proceedings of IMACS Multicomference on “Computational Engineering in Systems Applications”(CESA),October,2006,Beijing
[85]Kardrou Y,Najid N M,2007.Tabu search algorithm for the MRCPSP with multi-skilled labor,working paper,CPI'2007,Rabat,Maroc
[86]黄敏镁.具有柔性资源约束的调度问题研究:[博士学位论文].武汉:武汉理工大学管理学院,2007
[87]黄敏镁,罗荣桂,袁际军.求解置换调度问题的改进混合遗传算法[J].中国机械工程,2006,17(16):1707-1710
[88]黄敏镁,罗荣桂,袁际军.具有学习效果的两机流水车间调度启发式算法研究.武汉理工大学学报(交通科学与工程版),2007,31(5):931-934
[89]Minmei Huang,Ronggui Luo and Jijun Yuan.Heuristic-tabu-genetic algorithm based method for flowshop scheduling to minimize flowtime[C].In:Proceedings of The 6th World Congress on Intelligent Control and Automation,IEEE,2006
[90]Ronggui Luo,Minmei Huang.Parallel-machine scheduling with partial resource flexibility[C].In:Proceedings of the 11th International Conference on Industrial Engineering and Engineering Management.China Machine Press,2005
[91]谢政.网络算法与复杂性理论(第二版)[M].长沙:国防科技大学出版社,2003
[92]Cordeau J F,Laporte G.Pasin F,et al.Scheduling technicians and tasks in a telecommunications company,2008,working paper
[93]Dutot P.F.,Laugier A.,and Bustos A.M.Technicians and interventions scheduling for telecommunications.France Telecom R&D,August,2006
[94]Garey M R and Johnson D S.Computers and Intractability:A Guide to the Theory of NP-Completeness[M].Freeman,San Francisco,1979
[95]Demeulemeester E L.A random activity network generator[J].Operations Research,1993,41(5):972-980
[96]Demeulemeester E L,Vanhoucke M,Herroelen W S.RanGen:A random network generator for activity-on-the-node networks[J].Journal of Scheduling,2003,6(1):17-38
[97]刘士新,王梦光.多资源受限工程网络的随机生成器[J].东北大学学报,1997,18(5):494-497
[98]Davis E W,Patterson J H.A comparison of heuristic and optimum solutions in resource-constrained project scheduling[J].Management Science,1975,21(8):944-55
[99]Schrage L.A more portable fortran random number generator[J].ACM Transactions on Mathematical Software,1979,5(2):132-138
[100]TL Pascoe T L.An experimental comparison of heuristic methods for allocating resources.PhD Thesis,University of Cambridge,UK,1965
[101]Davis E W.Project network stmmary measures constrained-resource scheduling[J].AIIE Transactions(since 1985:IIE Transactions),1975,7(2):132-142
[102]Kaimann R A.Coefficients of network complexity[J].Management Science,1974,21(2):172-177
[103]Thesen A.Measures of the restrictiveness of project networks[J].Networks,1977,7(3):193-208
[104]Elmaghraby S E.Activity Networks:Project Planning and Control by Network Models[M].New York:Wiley,1977
[105]Cooper D F.Heuristics for scheduling resource-constrained projects:An experimental investigation[J].Management Science,1976,22(11):1186-1194