Max-npv Project Scheduling Problems with Generalized PrecedenceRelations and Its Genetic Algorithm

doi:10.12005/orms.2016.0206

Abstract

Abstract: In the classical Max-npv project scheduling problems, an activity must have been finished before any of its successors can be started. This basic precedence concept cannot cover all the relationships between activities in reality. A new Max-npv project scheduling model is established in this paper, in which activities are subject to generalized precedence relations. A two stage genetic algorithm is developed for the problem. In the first stage, the outer genetic algorithm determines a set of task execution modes; in the second stage, the inner genetic algorithm is responsible for searching the best schedules of activities. In the inner genetic algorithm, the difference in the start time of tasks is used as the coding representation. This coding method can simplify the crossover and mutation operator. While the repair operator is also built to ensure the task starttime meets the cycle structures’ requirements. Finally, the two-stage algorithm is tested on an example, and the result validates the effectiveness of the proposed algorithm.

Key words: project scheduling, net present value, generalized precedence relations, genetic algorithm

摘要： 以往Max-npv项目调度问题的研究都假定活动之间的关系为单一结束-开始类型,现实中活动之间关系复杂多变,因此,将广义优先关系引入Max-npv项目调度问题中,构建了广义优先关系约束下的Max-npv项目调度模型。针对该优化模型设计了一种双层遗传算法,外层遗传算法负责任务执行模式的优化,内层遗传算法负责任务调度的优化。在内层遗传算法中,采用任务开始时间之差作为新的编码方式,大大简化了交叉变异算子,针对网络图中的环状结构设计了修复算子,确保了编码的有效性。通过一个算例对算法进行了测试,实验结果验证了算法的有效性。

关键词: 项目调度, 净现金值, 广义优先关系, 遗传算法

CLC Number:

C935
F224.3

LIU Yang, CHEN Zhi , BAI Si-jun. Max-npv Project Scheduling Problems with Generalized PrecedenceRelations and Its Genetic Algorithm[J]. Operations Research and Management Science, 2016, 25(6): 91-98.

刘洋, 陈志, 白思俊. 广义优先关系约束下Max-npv项目调度问题及其遗传算法[J]. 运筹与管理, 2016, 25(6): 91-98.

References

[1] Russell A H. Cash flows in networks[J]. Management Science, 1970, 16(5): 357-373.[2] 何正文,徐渝,朱少英.Max-npv项目进度问题研究评述[J].管理工程学报,2005,19(4):60-63.
[3] Dayanand N, Padman R. On modeling progress payments in project networks[J]. Journal of the Operational Research Society, 1997,48(9): 906-918.
[4] Dayanand N, Padman R. Project contracts and payment schedules: the client’s problem[J]. Management Science, 2001, 47(12): 1654-1667.
[5] Dayanand N, Padman R. A two stage search heuristic for scheduling payments in projects[J]. Annals of Operations Research, 2001, 102(1-4): 197-220.
[6] 何正文,徐渝.多模式项目支付进度的整合优化研究[J].系统工程理论与实践,2006,26(1):76-83.
[7] 何正文,刘人境,徐渝.基于不同支付规则的MPPSP及其模拟退火与禁忌搜索算法[J].系统工程理论与实践,2010 ,30(8):1439-1447.
[8] 何正文,徐渝,朱少英.具有奖励惩罚结构的项目支付进度问题研究:双重角度[J].系统工程理论与实践,2005,25(10):39-45.
[9] 何正文,徐渝,朱少英.项目融资费用分担及联合支付进度问题研究[J].系统工程,2004,22(3):15-19.
[10] 何正文,刘人境,胡信布,等.现金流平衡约束下的Max-npv项目调度[J].系统工程理论与实践,2009,29(3):132-141.
[11] 何正文,刘人境,徐渝.基于现金流均衡目标的多模式项目调度问题研究[J].管理工程学报,2011,25(2):124-130.
[12] 柴国荣,徐渝,张静文,等.多模式柔性资源约束型折现流项目进度问题研究[J].系统工程,2005,23(2):14-18.
[13] 柴国荣,洪兆富,何正文.柔性资源约束下的大型项目奖惩结构优化[J].系统管理学报,2009,18(2):142-152.
[14] Brucker P, Drexl A, Mhring R, et al. Resource-constrained project scheduling: notation, classification, models, and methods[J]. European Journal of Operational Research, 1999, 112(1): 3-41.
[15] Bartusch M, Mhring R H, Radermacher F J. Scheduling project networks with resource constraints and time windows[J]. Annals of operations Research, 1988, 16(1): 199-240.
[16] Jarboui B, Damak N, Siarry P, et al. A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems[J]. Applied Mathematics and Computation, 2008, 195(1): 299-308.