广义网络多目标优化调度及其算法的研究
|
摘要
广义网络调度问题实质是在广义网络时序关系下通过活动进度的合理安排使得项目关注的目标得到优化。传统的项目调度问题研究往往是在无延迟网络,仅考虑可更新资源的基础上对项目工期进行优化。实际上它忽视广义网络下的活动时序关系、活动的执行模式、资源类别等其他因素对活动进度安排的影响。另外,随着企业对项目目标要求的提高,在项目目标优化上,项目管理者并不只是一味地追求工期最短,还关注其它目标,如资源均衡程度、抗风险能力等等。为此,针对传统项目调度安排研究中有关活动执行模式和活动间的时序关系假设条件和缺陷,本文研究了活动多执行模式、广义网络关系、可更新资源和不可更新资源两种资源约束对调度安排的影响,建立了综合考虑工期、时间鲁棒性、资源均衡多目标分层优化模型。同时,对求解模型的算法也进行了进一步地研究,将串行进度生成机制与遗传算法、模拟退火算法相结合,利用优先权数作为编码,采用串行进度生成机制作为解码方式对目标函数进行求解,并对遗传退火过程中的交叉机制和多目标选择策略进行了分析,形成了新型的遗传退火算法,并通过算例对模型进行了求解分析,验证模型和算法的可行性。
在基本完成预期研究目标的同时,本文也发现了研究过程中存在的问题,如何克服这些不足,通过更为科学的方法建立项目进度目标体系,以及将算法与禁忌等其它算法结合起来寻求更好地解决项目调度问题的算法都将是今后值得思考的方向。
The essence of the generalized network scheduling problem is through the reasonable arrangement of the progress of the activities to make the goal of the project to optimization in generalized network timing relationships.The traditional research on project schedule problems usually thinks that the net of project schedule is a no-delay network and the activities'resources are all renewable resources. In fact, it ignored the timing relationships in the generalized network, different execution mode of the activities, resource type and so on.With the increasing demand for the project objectives, project managers not just blindly pursue the shortest duration, but also concerned about other goals, such as resource equilibrium level, the ability to resist risk.Therefore, Aiming at the defects of the assumptions of execution mode for activities and net relations between activities,the paper studies the influence of the multiple execution mode, generalized network relations, two resource constraints(the renewable resources and the non-renewable resources) on scheduling arrangements, and build multi-objective hierarchical optimization model for the time limit, time robustness and resources equilibrium. At the same time, the algorithm to solve the model is the further studied, which is combined serial schedule generation mechanisms with genetic algorithms and simulated annealing algorithm.The algorithm uses priority number as a code and Serial schedule generation mechanism as the way of decoding to solve the objective function.In addition, the crossing mechanisms and the strategy of multi-objective selection are further Analyzed in the process of genetic simulated annealing in the paper.Then, through examples for solving the model analysis, the feasibility of the proposed model and algorithm is verified.
While achieving the expected objectives basically, this paper also finds some problems during the studying. How to build a more perfect target system by scientific methods and combine the annealing with the other algorithm (taboos algorithm) to seek better way to solve project scheduling problem, will be a researching direction worth considering.
在基本完成预期研究目标的同时,本文也发现了研究过程中存在的问题,如何克服这些不足,通过更为科学的方法建立项目进度目标体系,以及将算法与禁忌等其它算法结合起来寻求更好地解决项目调度问题的算法都将是今后值得思考的方向。
The essence of the generalized network scheduling problem is through the reasonable arrangement of the progress of the activities to make the goal of the project to optimization in generalized network timing relationships.The traditional research on project schedule problems usually thinks that the net of project schedule is a no-delay network and the activities'resources are all renewable resources. In fact, it ignored the timing relationships in the generalized network, different execution mode of the activities, resource type and so on.With the increasing demand for the project objectives, project managers not just blindly pursue the shortest duration, but also concerned about other goals, such as resource equilibrium level, the ability to resist risk.Therefore, Aiming at the defects of the assumptions of execution mode for activities and net relations between activities,the paper studies the influence of the multiple execution mode, generalized network relations, two resource constraints(the renewable resources and the non-renewable resources) on scheduling arrangements, and build multi-objective hierarchical optimization model for the time limit, time robustness and resources equilibrium. At the same time, the algorithm to solve the model is the further studied, which is combined serial schedule generation mechanisms with genetic algorithms and simulated annealing algorithm.The algorithm uses priority number as a code and Serial schedule generation mechanism as the way of decoding to solve the objective function.In addition, the crossing mechanisms and the strategy of multi-objective selection are further Analyzed in the process of genetic simulated annealing in the paper.Then, through examples for solving the model analysis, the feasibility of the proposed model and algorithm is verified.
While achieving the expected objectives basically, this paper also finds some problems during the studying. How to build a more perfect target system by scientific methods and combine the annealing with the other algorithm (taboos algorithm) to seek better way to solve project scheduling problem, will be a researching direction worth considering.
引文
[1]Blazewicz J, Lenstra J K. Scheduling subject to resource constraints:classification and complexity[J]. Discrete Applied Mathematics,1983,5(1):11-24
[2]Clark W. the Gantt chart [M].London:Pitman,1938
[3]Shaffer L R,Ritter J B, Meyer W L. The critical-path method[M].New York: McGraw-Hill,1965
[4]Malcolm D G, Roseboom J H, Clark C E. Application of a technique for research and development program evaluation[J]. Operations Research,1959,7(5):646-669
[5]Kelley J E, Jr J E. Critical path planning and scheduling:Mathematical basis [J]. Operation,1961,9(3):296-320
[6]Fulkerson D R. A network flow computation for project cost curves[J]. Management Science,1961,7(2):167-178
[7]Hindelang T J, Muth J F. A dynamic programming algorithm for decision CPM networks[J]. Operations Research,1979,27(2):225-241
[8]Hartmann S. Project scheduling with multiple modes:A genetic algorithm[J]. Annals of Operations Research,2001,102(4):111-135
[9]Fendley L G. Towards the development of a complete multi-Project scheduling system[J]. Journal of Industrial Engineering,1968,19(10):505-515
[10]Shigeru T, Richard F D. A heuristic for multi-project scheduling with limited resources in the housing industry[J]. European Journal of Operational Research,1990,49(1):80-91
[11]John D, Vincent A M. Evaluating project scheduling and due date assignment procedures: An experimental analysis[J]. Management Science,1998,34(1):101-118
[12]Demeulemeester E, Herroelen W. A branch-and-bound procedure for the multiple resource-constrained project scheduling problem [J].Management Science,1992,38(12): 1803-1818
[13]Brucker P, Knust S. A branch and bound algorithm for the resource-constrained project scheduling problem [J]. European J of Operational Research,1998,107(2):272-288
[14]Kolisch R, Sprecher A. A project scheduling problem library on operations research. European Journal of Operational Research,1997,96(1):205-216
[15]Kolisch R. Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation [J].European J of Operational Research,1996,90(2):320-333
[16]Ozdamar L, Ulusoy G. A note on an iterative forward/backward scheduling technique with reference to a procedure by Li and Willis[J]. European Journal of Operational Research,1996,89(2):400-407
[17]Drexl A. Scheduling of project networks by job assignment[J]. Management Science, 1991,37(12):1590-1602
[18]Leon V J, Balakrishnan R. Strength and adaptability of problem-space based neighborhoods for resource-constrained scheduling[J]. OR Spectrum,1995,17(2): 173-182
[19]Hartmann S. A competitive genetic algorithm for resource-constrained project scheduling[J]. Naval Research Logistics,1998,45(7):733-750
[20]Kim K W, Gen M, Yamazaki G. Hybrid genetic algorithm with fuzzy logic for resource-constrained project scheduling [J]. Applied soft Computing,2003,2(3):174-188
[21]Boctor FF.A new and efficient beuristic for scheduling projects with resource restrictions and multiple execution modes[J]. European J of Operational Research, 1996,90(2):349-361
[22]Cho J H, Kim Y D. A simulated annealing algorithm for resource constrained project scheduling problems[J]. J of the Operational Research Society,1997,48(7):736-744
[23]Vall V, Ballestin F, Quintanilla S. Justification and RCPSP:A technique that pay[J]. European J of Operational Research,2005,165(2):375-386
[24]Thomas P R, Salhi S.A tabu search approach for the resource constrained project scheduling problem[J]. J of Heuristics,1998,4(2):123-139
[25]曹佐,王窍成.工期优化数学模型研究[J].山西交通科技,2010,12(6)：18-27
[26]邢莉燕,李纪成.动态规划法在网络成本工期优化中的应用[J].山东科学,1998,11(3)：60-64
[27]蒋文娟,李春锋,高斌.“TFE”法—网络计划工期优化的新思路[J].河西学院学报,2006,22(2)：96-98
[28]吴相林,尹峥.应用最小费用流求解活动网络时间-费用模型[J].华中科技大学学报(自然科学版),2007,(1)：42-45
[29]王霞,马庆.基于遗传算法的时间、费用优化[J].商场现代化,2010,(14)
[30]王祖和.多资源均衡的权重优选法[J].管理工程学报,2002,16(3)：91-93
[31]高兴夫,钟登华,胡程顺.考虑动态投资影响下的资源均衡优化[J].浙江建筑,2006,23(11)：76-78
[32]宋洋,钟登华.考虑资金时间价值因素的多资源均衡优化[J].天津大学学报,2006,39(9)：1048-1053
[33]郑惠莉.多资源均衡的网络计划优化方法[J].南京邮电学院学报,1997,17：104-108
[34]马丹祥,初建宇,王海霞.考虑自由时差的资源均衡优化[J].河北理工大学学报,2011,33(3)：133-137
[35]寿涌毅,傅奥.多目标资源受限项目调度的多种群蚁群算法[J].浙江大学学报,2010.44(1)：51-55
[36]高雷阜.资源分配的多目标优化动态规划模型[J].辽宁工程技术大学学报(自然科学版),2001,20(5)：679-681
[37]刘士新,王梦光,聂义勇.多执行模式资源受限工程调度问题的优化算法[J].系统 工程学报,2001,16(1)：55-60
[38]周楷,何正文.周期性支付的多模式Max-npv项目调度问题研究[J].中国企业运筹学学术会议,2008
[39]方炜,欧立雄.多项目环境下新产品研发项目资源分配问题研究[J].管理工程学报,2005,19(S1)：6-10
[40]谈烨,仲伟俊,徐南荣.多种资源受限多项目排序问题的两层决策方法[J].系统工程理论与实践,2001,21(2)：1-5
[41]廖仁,陈庆新,毛宁.资源约束下多项目调度的启发式算法[J].管理工程学报,2002,16：100-103
[42]寿涌毅.资源约束下多项目调度的迭代算法[J].浙江大学学报(工学版),2004,38(8)：1095-1099
[43]陈志勇,杜志达,周华.基于微粒群算法的工程项目资源均衡优化[J].土木工程学报.2007,40(2)：94-96
[44]林志荣,朱鋐道.网络计划中资源均衡优化的研究[J].中国管理科学,2000,8(3)：41-43
[45]赵胜利,刘燕,杜光乾.基于遗传算法的工程项目资源均衡研究[J].计算机工程与应用,2008,44(25)：213-214
[46]王为新,李原,张开富.基于遗传算法的多模式资源受限项目调度问题研究[J].计算机应用研究,2007,(1)：70-216
[47]马云峰.资源约束条件下多模式项目调度问题研究[J].雁北师范学院学报,2005,21(6)：105-107
[48]柴永生,孙树栋.基于免疫遗传算法的车间动态调度[J].机械工程学报,2005,41(10)：23-27
[49]吴秀丽.柔性作业车间动态调度问题研究明[J].系统仿真学报,2008,20(14)：3828-3832
[50]熊唯,李宗斌,郝建波.解决动态作业车间调度关键问题的方法研究[J].组合机床与自动化加工技术,2008,(7)：105-108
[51]M.A.Al-Fawzana, Mohamed Haouari. A bi-objective model for robust resource-constrained project scheduling[J]. Int. J. Production Economics,2005, (96): 175-187
[52]Babak Abbasi, Shahram Shadrokh, Jamal ArkatBi-objective resource-constrained project scheduling with robustness and makespan criteria[J]. Applied Mathematics and Computation,2006, (180):146-152
[53]Olivier Lambrechts, Erik Demeulemeester, Willy Herroelen. A tabu search procedure for developing robust predictive project schedules[J]. Int. J. Production Economic,2008, (111):493-508
[54]Przemyslaw Kobylanski, Dorota Kuchta. A note on the paper by M. A. Al-Fawzan and M. Haouari about a bi-objective problem for robust resource-constrained project scheduling[J]. Int. J. Production Economics,2007, (107):496-501
[55]Stijn Van de Vonder, Francisco Ballestin, Erik Demeulemeester, Willy Herroelen. Heuristic procedures for reactive project scheduling[J]. Computer& Industrial Engineering,2007, (52):11-28
[56]Denise Sato Yamashita, Vinicius Amaral Armentano, Manuel Laguna. Robust optimization models for project scheduling with resource availability cost[J]. J Ssched, 2007, (10):67-76
[57]高孝伟,孔锐,张谦孜,周彦喆.对网络计划中时间—费用优化方法的改进性探讨[J].统计与决策,2008,14(2)：161-162
[58]周树发,刘莉.工程网络计划中的多目标优化问题[J].华东交通大学学报,2004,21(2)：11-13
[2]Clark W. the Gantt chart [M].London:Pitman,1938
[3]Shaffer L R,Ritter J B, Meyer W L. The critical-path method[M].New York: McGraw-Hill,1965
[4]Malcolm D G, Roseboom J H, Clark C E. Application of a technique for research and development program evaluation[J]. Operations Research,1959,7(5):646-669
[5]Kelley J E, Jr J E. Critical path planning and scheduling:Mathematical basis [J]. Operation,1961,9(3):296-320
[6]Fulkerson D R. A network flow computation for project cost curves[J]. Management Science,1961,7(2):167-178
[7]Hindelang T J, Muth J F. A dynamic programming algorithm for decision CPM networks[J]. Operations Research,1979,27(2):225-241
[8]Hartmann S. Project scheduling with multiple modes:A genetic algorithm[J]. Annals of Operations Research,2001,102(4):111-135
[9]Fendley L G. Towards the development of a complete multi-Project scheduling system[J]. Journal of Industrial Engineering,1968,19(10):505-515
[10]Shigeru T, Richard F D. A heuristic for multi-project scheduling with limited resources in the housing industry[J]. European Journal of Operational Research,1990,49(1):80-91
[11]John D, Vincent A M. Evaluating project scheduling and due date assignment procedures: An experimental analysis[J]. Management Science,1998,34(1):101-118
[12]Demeulemeester E, Herroelen W. A branch-and-bound procedure for the multiple resource-constrained project scheduling problem [J].Management Science,1992,38(12): 1803-1818
[13]Brucker P, Knust S. A branch and bound algorithm for the resource-constrained project scheduling problem [J]. European J of Operational Research,1998,107(2):272-288
[14]Kolisch R, Sprecher A. A project scheduling problem library on operations research. European Journal of Operational Research,1997,96(1):205-216
[15]Kolisch R. Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation [J].European J of Operational Research,1996,90(2):320-333
[16]Ozdamar L, Ulusoy G. A note on an iterative forward/backward scheduling technique with reference to a procedure by Li and Willis[J]. European Journal of Operational Research,1996,89(2):400-407
[17]Drexl A. Scheduling of project networks by job assignment[J]. Management Science, 1991,37(12):1590-1602
[18]Leon V J, Balakrishnan R. Strength and adaptability of problem-space based neighborhoods for resource-constrained scheduling[J]. OR Spectrum,1995,17(2): 173-182
[19]Hartmann S. A competitive genetic algorithm for resource-constrained project scheduling[J]. Naval Research Logistics,1998,45(7):733-750
[20]Kim K W, Gen M, Yamazaki G. Hybrid genetic algorithm with fuzzy logic for resource-constrained project scheduling [J]. Applied soft Computing,2003,2(3):174-188
[21]Boctor FF.A new and efficient beuristic for scheduling projects with resource restrictions and multiple execution modes[J]. European J of Operational Research, 1996,90(2):349-361
[22]Cho J H, Kim Y D. A simulated annealing algorithm for resource constrained project scheduling problems[J]. J of the Operational Research Society,1997,48(7):736-744
[23]Vall V, Ballestin F, Quintanilla S. Justification and RCPSP:A technique that pay[J]. European J of Operational Research,2005,165(2):375-386
[24]Thomas P R, Salhi S.A tabu search approach for the resource constrained project scheduling problem[J]. J of Heuristics,1998,4(2):123-139
[25]曹佐,王窍成.工期优化数学模型研究[J].山西交通科技,2010,12(6)：18-27
[26]邢莉燕,李纪成.动态规划法在网络成本工期优化中的应用[J].山东科学,1998,11(3)：60-64
[27]蒋文娟,李春锋,高斌.“TFE”法—网络计划工期优化的新思路[J].河西学院学报,2006,22(2)：96-98
[28]吴相林,尹峥.应用最小费用流求解活动网络时间-费用模型[J].华中科技大学学报(自然科学版),2007,(1)：42-45
[29]王霞,马庆.基于遗传算法的时间、费用优化[J].商场现代化,2010,(14)
[30]王祖和.多资源均衡的权重优选法[J].管理工程学报,2002,16(3)：91-93
[31]高兴夫,钟登华,胡程顺.考虑动态投资影响下的资源均衡优化[J].浙江建筑,2006,23(11)：76-78
[32]宋洋,钟登华.考虑资金时间价值因素的多资源均衡优化[J].天津大学学报,2006,39(9)：1048-1053
[33]郑惠莉.多资源均衡的网络计划优化方法[J].南京邮电学院学报,1997,17：104-108
[34]马丹祥,初建宇,王海霞.考虑自由时差的资源均衡优化[J].河北理工大学学报,2011,33(3)：133-137
[35]寿涌毅,傅奥.多目标资源受限项目调度的多种群蚁群算法[J].浙江大学学报,2010.44(1)：51-55
[36]高雷阜.资源分配的多目标优化动态规划模型[J].辽宁工程技术大学学报(自然科学版),2001,20(5)：679-681
[37]刘士新,王梦光,聂义勇.多执行模式资源受限工程调度问题的优化算法[J].系统 工程学报,2001,16(1)：55-60
[38]周楷,何正文.周期性支付的多模式Max-npv项目调度问题研究[J].中国企业运筹学学术会议,2008
[39]方炜,欧立雄.多项目环境下新产品研发项目资源分配问题研究[J].管理工程学报,2005,19(S1)：6-10
[40]谈烨,仲伟俊,徐南荣.多种资源受限多项目排序问题的两层决策方法[J].系统工程理论与实践,2001,21(2)：1-5
[41]廖仁,陈庆新,毛宁.资源约束下多项目调度的启发式算法[J].管理工程学报,2002,16：100-103
[42]寿涌毅.资源约束下多项目调度的迭代算法[J].浙江大学学报(工学版),2004,38(8)：1095-1099
[43]陈志勇,杜志达,周华.基于微粒群算法的工程项目资源均衡优化[J].土木工程学报.2007,40(2)：94-96
[44]林志荣,朱鋐道.网络计划中资源均衡优化的研究[J].中国管理科学,2000,8(3)：41-43
[45]赵胜利,刘燕,杜光乾.基于遗传算法的工程项目资源均衡研究[J].计算机工程与应用,2008,44(25)：213-214
[46]王为新,李原,张开富.基于遗传算法的多模式资源受限项目调度问题研究[J].计算机应用研究,2007,(1)：70-216
[47]马云峰.资源约束条件下多模式项目调度问题研究[J].雁北师范学院学报,2005,21(6)：105-107
[48]柴永生,孙树栋.基于免疫遗传算法的车间动态调度[J].机械工程学报,2005,41(10)：23-27
[49]吴秀丽.柔性作业车间动态调度问题研究明[J].系统仿真学报,2008,20(14)：3828-3832
[50]熊唯,李宗斌,郝建波.解决动态作业车间调度关键问题的方法研究[J].组合机床与自动化加工技术,2008,(7)：105-108
[51]M.A.Al-Fawzana, Mohamed Haouari. A bi-objective model for robust resource-constrained project scheduling[J]. Int. J. Production Economics,2005, (96): 175-187
[52]Babak Abbasi, Shahram Shadrokh, Jamal ArkatBi-objective resource-constrained project scheduling with robustness and makespan criteria[J]. Applied Mathematics and Computation,2006, (180):146-152
[53]Olivier Lambrechts, Erik Demeulemeester, Willy Herroelen. A tabu search procedure for developing robust predictive project schedules[J]. Int. J. Production Economic,2008, (111):493-508
[54]Przemyslaw Kobylanski, Dorota Kuchta. A note on the paper by M. A. Al-Fawzan and M. Haouari about a bi-objective problem for robust resource-constrained project scheduling[J]. Int. J. Production Economics,2007, (107):496-501
[55]Stijn Van de Vonder, Francisco Ballestin, Erik Demeulemeester, Willy Herroelen. Heuristic procedures for reactive project scheduling[J]. Computer& Industrial Engineering,2007, (52):11-28
[56]Denise Sato Yamashita, Vinicius Amaral Armentano, Manuel Laguna. Robust optimization models for project scheduling with resource availability cost[J]. J Ssched, 2007, (10):67-76
[57]高孝伟,孔锐,张谦孜,周彦喆.对网络计划中时间—费用优化方法的改进性探讨[J].统计与决策,2008,14(2)：161-162
[58]周树发,刘莉.工程网络计划中的多目标优化问题[J].华东交通大学学报,2004,21(2)：11-13