共享资源约束净现值最大化多项目调度及其禁忌搜索启发式算法

何华; 曹芳芳; 何正文; 王能民

doi:10.3969/j.issn.1007-7375.240024

共享资源约束净现值最大化多项目调度及其禁忌搜索启发式算法

何华^{1, 2, 3,},
曹芳芳^{1, 2},
何正文^{1, 2},
王能民^{1, 2}

1.
西安交通大学管理学院，陕西西安 710049
2.
西安交通大学过程管理与效率工程教育部重点实验室，陕西西安 710049
3.
西安职业技术学院现代商学院，陕西西安 710077

基金项目: 国家自然科学基金资助项目 (72371195, 71871176)

详细信息

作者简介:
何华(1984—)，女，山西省人，博士研究生，主要研究方向为项目调度及优化。Email: 365074073@qq.com

中图分类号: C935; F224.33; F425
计量
- 文章访问数: 134
- HTML全文浏览量: 38
- PDF下载量: 4
出版历程
- 收稿日期: 2023-10-31
- 刊出日期: 2024-12-24

Multi-project Scheduling with Shared Resource Constraints for Maximizing Net Present Value Using a Tabu Search Heuristic Algorithm

HE Hua^{1, 2, 3,},
CAO Fangfang^{1, 2},
HE Zhengwen^{1, 2},
WANG Nengmin^{1, 2}

1.
School of Management, Xi'an Jiaotong University, Xi'an 710049, China
2.
The Key Lab of the Ministry of Education for Process Management & Efficiency Engineering, Xi'an Jiaotong University, Xi'an 710049, China
3.
Modern Business School, Xi'an Vocational and Technical College, Xi'an 710077, China

摘要

摘要:
研究共享资源约束下的净现值最大化多项目调度问题。介绍了该问题的现实和理论背景并提出研究问题，构建问题优化模型和分析模型特点并提炼问题性质，设计问题求解的禁忌搜索启发式算法，并提出改进措施以提升算法效率。在随机生成的标准算例上进行计算实验，对算法进行验证，以及对关键参数进行敏感性分析。研究表明，禁忌搜索算法优于多重迭代改进和随机抽样算法，且基于改进措施的禁忌搜索算法绩效最佳；净现值随资源强度和项目截止日期增加而增加，而随资源因子呈下降趋势；另外净现值随里程碑数量、预付款比例和支付比例呈单调递增的趋势，而折现率则负向影响净现值。
- 多项目调度 /
- 净现值最大化 /
- 优化模型 /
- 禁忌搜索 /
- 共享资源
Abstract:
This study investigates the multi-project scheduling problem under shared resource constraints, aiming to maximize net present value (NPV). The practical and theoretical background of the problem is introduced, while the research problem is formulated. An optimization model is established and the characteristics of this model are analyzed, furthermore, the key problem properties are refined. A tabu search (TS) heuristic algorithm is designed for solving the problem, with improvement measures proposed to enhance its efficiency. Finally, numerical experiments are conducted on randomly generated standard instances to verify the effectiveness of the algorithm, while sensitivity analysis of key parameters is performed. The conclusions drawn from the study are as follows: TS algorithm outperforms multistart iteration improvement (MSII) algorithm and random sampling (RS) algorithm, with the performance of the improved TS algorithm being the best. NPV increases with resource intensity and project deadlines, while it decreases with the resource factor. Additionally, NPV shows a monotonic increasing trend with the number of milestones, advance payment ratios, and progress payment ratios, while the discount rate negatively impacts NPV.
- multi-project scheduling /
- NPV maximization /
- optimization model /
- tabu search /
- shared resources

HTML全文

项目调度问题研究如何合理安排活动开始时间并有效使用企业资源以实现给定的目标要求。由于承包商实施项目的根本目的是企业的生存和盈利，所以，以净现值 (net present value，NPV) 最大化为目标的项目调度问题 (亦称max-NPV项目调度问题) 成为该领域的一个重要分支。在该问题中，需要回答如何最优地安排项目的进度计划，以取得承包商现金流出与流入的最佳匹配，从而实现项目净现值的最大化。事实上，考虑到现实中的承包商往往会同时承接和并行实施多个项目，该问题在多项目环境下更具实用价值。与单项目调度问题不同，多项目调度问题需要将各单个项目的差异性考虑在内，将企业资源在多项目之间进行合理配置，统筹安排各单个项目的进度计划以取得企业收益的总体最优。

在多项目环境下，根据各单项目的特点属性及企业所拥有的资源状况，通常存在两种代表性资源配置模式^[1]：共享资源配置模式和非共享资源配置模式。共享资源指的是那些可供多个项目共同使用的资源。这些资源可能包括设备、人力、专业知识或其他关键要素，它们对于多个项目的顺利进行至关重要。共享资源的特点在于它们不像项目特定非共享资源只允许分配给某个项目，而是在多个项目之间共享和竞争使用。共享资源在制造、软件开发等行业较为常见，在该种资源配置模式下，由于各单个项目的地点较为集中，其在实施中所需的资源通用性较强，为提高资源使用效率，承包商一般允许资源可以在不同的单个项目之间共享，并集中统一地安排多个项目的进度计划；而后者则多用于交通、水电等建设类项目中，对于该类项目，由于其地理位置较为分散，资源在不同项目之间调运成本较高，承包商只能将企业资源分配到单个项目上，而各项目在所分配的资源条件下各自独立地安排自身的进度计划。由此可见，如何基于企业的资源配置模式，统筹地安排各单个项目的进度计划，以取得多项目净现值的最大化，无疑是一个具有较高现实意义的研究问题。

基于上述现实背景，本文研究共享资源配置模式下的净现值最大化多项目调度问题，即企业需要并行地实施多个项目，资源可以在这些项目之间无代价共享；各单个项目有各自的活动网络优先关系、截止时间约束以及合同规定的支付条件；目标是在企业所拥有资源总量限制下，集中地安排所有单个项目的进度计划，以实现多项目净现值的最大化。由于该问题普遍存在于制造业、软件开发等行业，因此，本文的研究具有较为明确的现实背景，可以为这些行业的多项目进度计划安排、资源配置及现金流优化提供直接的方法支持，有助于承包商提升项目管理水平并改善项目收益。

1. 文献综述

本研究主要涉及项目调度领域中的Max-npv项目调度问题、资源约束多项目调度问题，以及考虑现金流的多项目调度问题。因此，以下主要从资源角度进行多项目调度综述。

1.1 资源约束多项目调度问题

Max-npv项目调度问题是1970年由Russell^[2]首先提出。按照资源可否在多个项目之间共享，资源约束多项目调度问题分为共享资源约束和非共享资源约束两大分支。共享资源约束背景下，Kurtulus等^[3]提出两种衡量资源使用绩效的指标。Mohanty等^[4]利用整数目标规划构建共享资源约束多项目调度模型，借助于仿真技术分析了多个绩效的效果。Lawrence等^[5]设计一种成本−收益调度策略，该策略可以通过资源定价最小化多个项目的加权延迟成本。Lova等^[6]开发了一种针对共享资源多项目调度的多属性启发式算法。寿涌毅^[7]通过对单项目调度迭代算法扩展来解决多项目调度问题。Browning等^[8]研究静态资源受限的多项目调度问题，测试并分析现有20条优先级规则。王海鑫等^[9]研究最小化加权工期的多项目调度问题，提出一种自适应粒子群算法。Hauder等^[10]将研究问题扩展到活动和时间具有柔性的条件下，建立并求解问题的混合整数规划和约束规划模型。彭武良等^[11]以工期和共享资源需求最小化为目标，设计了基于快速非支配遗传算法的两阶段算法求解。Chen等^[12]研究动态多项目调度问题，设计独特的超启发式算法。

关于非共享资源约束项目调度问题，学者们提出较多的方法进行资源冲突的解决。比如，Lee等^[13]提出基于市场机制的资源分配规则。Confessore等^[14]引入基于拍卖机制的多代理人系统。Homberger^[15]把重新启动进化策略与多代理人系统相结合处理多项目局部资源调度问题。Homberger^[16]依据基于谈判的决策机制确定项目的优先权来解决多项目调度中的资源冲突。Zheng等^[17]基于关键链来处理全局资源冲突。丰景春等^[18]设计两阶段资源分配协调机制来解决不确定的全局资源可用量问题。

1.2 考虑现金流的多项目调度问题

在多项目调度问题研究中，也有部分学者将现金流优化统筹在内，形成考虑现金流的多项目调度问题研究分支。在该分支上，Liu等^[19]将融资引入多项目调度问题。Can等^[20]研究多模式的净现值最大化问题。El-Abbasy等^[21]以项目完成时间、总成本、融资成本、项目利润和资源波动的目标的多目标权衡问题。He等^[22]设计并对比资源约束多项目调度问题的禁忌搜索和模拟退火算法，目标是最小化项目实施过程中承包商的最大现金流缺口。针对考虑现金流优化的分布式多项目调度问题，刘万琳等^[23]将全局资源约束拓展为柔性使用状态，设计了遗传−模拟混合算法。

表1对以上两个分支进行汇总。可见，根据资源约束类型，max-NPV项目调度问题分为共享资源约束问题和非共享资源约束问题。虽然这两个问题也出现不少模型和算法，但它们大多基于项目工期定义目标函数。需要指出的是，关于多项目调度问题，也有少部分学者考虑了现金流优化问题，然而他们的研究大多聚焦于如何进行项目融资、保持现金流平衡，以及项目工期、收益、成本、资源等多目标权衡等方面，而对共享资源约束净现值最大化问题的深入研究较为缺乏。本研究正是针对这一问题展开，与现有文献有着较为显著的区别。因此，本研究具有明显的创新性，为推动项目调度领域相关研究的发展做出贡献。

表 1 文献综述汇总

Table 1. Summary of literature review

文献	目标函数				资源类型
文献	工期	成本	净现值	其他	共享资源	非共享资源
Kurtulus等^[3]	√			√	√
Mohanty等^[4]	√	√		√	√
Lawrence等^[5]		√		√	√
Lova等^[6]	√				√
寿涌毅^[7]	√				√
Browninge等^[8]	√				√
王海鑫等^[9]	√				√
Hauder等^[10]	√				√
彭武良等^[11]	√				√
Chen等^[12]	√				√
Lee等^[13]	√					√
Confessore等^[14]	√					√
Homberger^[15]	√					√
Homberger^[16]	√					√
Zheng等^[17]	√					√
丰景春等^[18]	√					√
Liu等^[19]			√		√
Can等^[20]			√		√
El-Abbasy等^[21]	√	√			√
He等^[22]					√
刘万琳^[23]					√
本文			√		√

下载: 导出CSV

| 显示表格

2. 共享资源约束优化模型的构建与分析

2.1 问题表述及模型构建

假定某一承包商同时实施Q个项目，这些项目均规定有各自的开始时间和截止时间，单项目q (q = 1, 2, ···, Q) 的开始时间为I^q，截止时间为D^q。对于某一单项目，构成项目的活动之间存在着零时滞的结束−开始型优先关系。所有活动之间的优先关系被表示为单代号AoN (activity-on-node) 活动网络G^q (N^q, A^q)。N^q为节点集合，表示项目活动；A^q为箭线集合，表示活动之间结束−开始逻辑关系。在集合N^q中，总共有n^q+2个活动，其中虚活动0和n^q+1。

项目活动的执行需要可重复使用资源种类数为K。对于第k (k = 1, 2, $\cdots$ , K) 种资源，承包商拥有的总量为R_k。现假定项目q中活动i (i∈N^q) 对第k种资源的需求量为r_ik，在标准工作条件下，其工期为d_i。资源的使用及消耗产生的成本为c_i。对于某一活动来说，由于资源采购、准备及投入通常是以该活动何时必须完成为基准进行的，所以，本文将c_i计算到活动i的完成时刻。虚活动0和n^q+1，参数r_ik、d_i和c_i均为0。

当项目某一活动完成时，业主会依据合同约定给承包商计入相应数额的合同价值量，以便后续支付中以此为基准计算支付量。该合同价值量被称为活动的挣值，所有合同的挣值之和即为项目的合同总价款。现假定活动i的挣值为v_i (虚活动挣值为0)。项目q的合同总价格表示为 ${P^q} = \displaystyle\sum\limits_{i \in {N^q}} {{v_i}}$ 。在项目的开始时刻，业主会以P^q为基准对承包商支付一定比例的预付款用于项目启动，该预付款的比例为γ^q (0≤γ^q≤1)，其金额为γ^qP^q。对于项目q，有M^q (M^q≤n^q) 个里程碑活动，当这些活动完成时，业主基于承包商已完成活动的累计挣值按支付比例θ^q (0≤θ^q≤1) 对承包商进行中间支付，而在这些中间支付中，业主会按比例γ^q扣回预付款。当项目完成亦即虚活动n^q+1实现时，业主向承包商付清合同总价款。

对于项目q来说，从其开始到结束，业主需对其进行M^q+2次支付。定义项目的第m (m=1, 2, ···, M^q+2) 次支付的支付量为p_m。第一次支付p₁为

$\qquad \mathit{p} _{ \mathrm{1}} \mathrm= \mathit{\gamma } ^{ \mathit{q} } \mathit{P} ^{ \mathit{q} } \mathrm{。}$

(1)

当第m (m=2, 3, ···, M^q+1) 次支付发生时，亦即与第m支付相关联的里程碑活动完成时，设定承包商已经完成的活动集合为F_m，那么，p_m计算为

$\qquad {p_m} = ({\theta ^q} - {\gamma ^q}) \left(\sum\limits_{i \in {F_m}} {{v_i}} - \sum\limits_{i \in {F_{m - 1}}} {{v_i}} \right) \text{，} \mathit{m=} \mathrm{2,3,\cdots,} \;\mathit{M} ^{ \mathit{q} } \mathrm{+1。}$

(2)

当项目完成时，由于业主要向承包商付清合同总价款P^q，所以业主的最后一次支付为

$\qquad {p_{{M^q} + 2}} = {P^q} - \sum\limits_{m = 1}^{{M^h} + 1} {{p_m}} 。$

(3)

现假定项目q中活动i的开始时间被安排为s_i。项目q的进度计划安排为 ${S^q} = ({s_0},{s_1}, \cdots ,{s_{{n^q} + 1}})$ 。所有Q个单项目的S^q组合到一起，即为多项目的进度计划安排S= (S¹, S², ···, S^Q)。本文假定活动的成本发生在各活动的结束时刻，因此，项目执行过程中的现金流出时间及大小也相应确定，令多项目现金流出的现值为NPV^‒，单位时期的折现率为α，则有

$\qquad {\rm{NPV}}^ - = \sum\limits_{q = 1}^Q {\sum\limits_{i \in {N^q}}^{} {\Big\{ {c_i} \exp [ - \alpha ({s_i} + {d_i}) ]\Big\} } } 。$

(4)

相似地，假定第m (m = 2, 3, ···, M^q+1) 次支付相关联的里程碑活动为i_m，则NPV⁺为

$\begin{split} &\qquad {\rm{NPV}}^ + = \sum\limits_{q = 1}^Q \Bigg\{ {p_1} \exp ( - \alpha {s_0}) + \Bigg.\\ & \Bigg.\sum\limits_{m = 2}^{{M^q} + 1} {\left[{p_m} \exp ( - \alpha ({s_{{i_m}}} + {d_{{i_m}}})\right ]} + {p_{{M^q} + 2}} \exp ( - \alpha {s_{{n^q} + 1}}) \Bigg\} 。 \end{split}$

(5)

因此多项目的净现值NPV计算为

$\qquad \mathrm{NPV=NPV}^{ \mathrm+} -\mathrm{NPV}^- 。$

(6)

将问题界定为：对于并行实施的Q个项目，在各单个项目的开始时间I^q、截止时间D^q、网络优先关系A^q，以及资源可用量R_k的约束下，综合考虑合同对预付款比例γ^q、支付比例θ^q及里程碑活动i_m的规定，根据各活动的资源需求r_ik、工期d_i、成本c_i和挣值v_i等输入数据，合理安排各活动的开始时间以形成最优的多项目进度计划S，以实现项目活动成本 (现金流出) 和业主支付 (现金流入) 之间的最佳匹配，进而取得承包商项目净现值NPV的最大化。因此，研究问题的优化模型构建如式 (7) ~ 式 (12) 所示。

$\qquad \mathrm{\max }\; \rm{NPV} \mathrm= \rm{NPV} ^{ \mathrm+} - \rm{NPV} ^-。$

(7)

$\qquad \mathrm{s.t.}$

$\qquad \mathit{s} _{ \mathrm{0}} \mathrm= \mathit{I} ^{ \mathit{q} }，\; \mathit{q} \mathrm{=1,2,\cdots,} \mathit{Q} ；$

(8)

$\qquad \mathit{s} _{ \mathit{i} } \mathrm+ \mathit{d} _{ \mathit{i} } {\leqslant } \mathit{s} _{ \mathit{j} }， \mathrm{ (} \mathit{i,\;j}) \in \mathit{A} ^{ \mathit{q} } \mathrm{,}\;\; \mathit{q} \mathrm{=1,2,\cdots,} \mathit{Q} \mathrm{\text{；} }$

(9)

$\qquad{s_{{n^q} + 1}} \leqslant {D^q}，\; q=1, 2, \cdots, Q ；$

(10)

$\qquad \displaystyle\sum\limits_{i \in {O^t}} {{r_{ik}}} \leqslant R{}_k ，\;t \in [s_0^{\min },s{}_{n + 1}^{\max }],\;\; k=1, 2, \cdots, K\text{；}^{ }$

(11)

$\qquad \mathit{s} _{ \mathit{i} } \mathrm{为非负整数\text{，}} \mathit{i} \in \mathit{N} ^{ \mathit{q} } \mathrm{,} \;\;\; \mathit{q} {=1,2,…,} \mathit{Q} 。$

(12)

其中，式 (7) 为最大化多项目的净现值；约束 (8) 将各单项目虚开始活动的开始时间定义为所规定的项目开始时间；式 (9) 为项目活动的优先关系约束；式 (10) 为各单个项目截止时间约束；式 (11) 表示t时刻正在进行的活动集合O^t的资源需求总量不能超过给定的资源可用量；式 (12) 为决策变量定义域约束。

2.2 模型性质分析

本文的优化模型中存在非里程碑活动和里程碑活动。在前者完成时业主不会对承包商进行支付，而是将其挣值计入已完成活动的累计挣值中；而当后者完成时，业主才会进行支付。由此可见，只有当完成里程碑活动时，才会给承包商带来现金流入；而非里程碑活动的完成，只会发生现金流出。对于某一给定的多项目进度计划安排S，将某活动开始时间的提前称为该活动左移，相应地，将某活动开始时间的延后称为右移。根据问题的上述特点，可以提出以下3条性质。利用这些性质可以将S中活动合理地进行左移或右移，由此提升目标函数NPV，并得到一个改进的多项目进度计划S。

性质1　 (非里程碑活动右移) 给定一个可行的S，假定某一单项目中的某一非里程碑活动i的挣值累计到里程碑活动i_m完成时支付，在不影响其他活动的前提下，如果活动i能够右移一定幅度且这种右移不会影响其在i_m完成时支付，则执行该操作能够提升NPV进而得到一个改进的S。

证明　给定一个可行的S，某一非里程碑活动i的成本，即其引起的现金流出发生在该活动的完成时刻。若该活动的挣值累计到里程碑活动i_m完成时进行支付，则由该活动带来的现金流入发生在活动i_m的完成时刻。在不影响其在活动i_m完成时支付的前提下，如果该活动能够右移一定幅度，那么，由其引起的现金流入的发生时间不会改变，但由其带来的现金流出将会延后。由于在此过程中，其他活动的安排保持不变，因此，对活动i执行上述右移操作能够提高多项目净现值NPV并由此得到一个改进的S。

性质2　 (非里程碑活动左移) 给定可行的S，假定某一单项目中的某一非里程碑活动i的挣值累计到里程碑活动i_m完成时支付，在不影响其他活动的前提下，如果活动i能够左移，至使其在i_m‒1完成时支付，则执行该操作能够提升NPV进而得到改进的S。

证明　与性质1中的情形相似，若某一单项目中的某一非里程碑活动i的挣值累计到里程碑活动i_m完成时支付，则由其带来的现金流入发生在该里程碑活动的完成时刻。如果在不影响其他活动的前提下，活动i能够左移至使其在i_m‒1完成时支付，则由该活动完成所带来的现金流入的发生时间将会提前。虽然在此过程中，由该活动引起的现金流出也会同步提前，但由于对于某一给定活动来说，其导致的现金流入通常会大于现金流出，所以，则执行该操作能够提升多项目NPV并得到一个改进的进度计划S。

性质3　 (里程碑活动左移) 给定可行的S，假定某一单项目中在某一里程碑活动i_m之前最晚完成的非里程碑活动为i，在不影响其他活动的前提下，如果活动i_m能够左移至活动i结束时刻完成，则能够提升NPV进而得到改进的S。

证明　给定一个可行的S，某一单项目中在某一里程碑活动i_m之前最晚完成的非里程碑活动为i，则在i_m完成时进行支付的所有非里程碑活动的完成时间都不会晚于活动i的完成时间。如果在不影响其他活动的前提下，活动i_m能够左移至活动i结束时刻完成，那么，在i_m完成时进行支付的支付量不会因i_m的左移而发生变化，但该次支付的时间将会提前。在此过程中其他活动的安排不会发生变化，尽管i_m的左移会导致其自身的成本发生时间的同步提前，但由于在i_m完成时的支付量会远大于其成本，因此，执行该操作必然会带来多项目净现值NPV的提高，并由此生成一个改进的S。

3. 禁忌搜索启发式算法设计

资源约束项目调度问题已被证明为NP-hard^[24]问题，本文所研究的问题为资源约束项目调度问题向以净现值最大化目标的多项目情形下的一种扩展，因此该问题也必然为NP-hard问题。从实用角度出发，采用禁忌搜索启发式算法对问题进行求解。因为该算法已被广泛地应用于项目调度问题的求解中，且已被证明是该领域最为成功的启发式算法之一^[25]；同时，采用该算法对问题进行求解，也便于将基于问题性质设计的改进措施添加到算法的搜索过程中。本文所设计算法的改进之处在于，将问题的特点 (即2.2中所提出的3条性质) 有机地融入算法中，借此改进问题的初始解和邻点解，进而有效提升算法的搜索效率。

3.1 解的表示以及目标函数计算

本文用S表示问题的解。给定一个可行解S，按照算法1计算与其对应的目标函数NPV。

算法1: 目标函数计算
输入：可行解S
输出：NPV
1　根据每个活动的开始时间s_i及各活动成本c_i和活动工期d_i，　利用式 (4) 计算出多项目实施过程中所有现金流出的现值NPV⁻
2　根据项目合同总价格P^q和预付款比例 γ^q，利用式 (1) 计算各项目的　预付款p₁
3　根据活动的完成时间s_i，确定各次支付发生时承包商已完成的活动集　合F_m，再结合活动挣值v_i、项目支付比例θ^q和预付款比例γ^q，通过式　 (2) 计算出项目进行过程中各次支付的支付量p_m 4　利用式 (3) 计算　各项目最后一次支付的支付量 ${p_{{M^q} + 2}}$
5　利用式 (5) 计算多项目实施过程中所有现金流入NPV⁺
6　根据得到的NPV^‒和NPV⁺，利用式 (6) 计算多项目的净现值NPV

3.2 初始解构造与邻点解生成

将问题的初始解、当前解和邻点解分别表示为S^init、S^curr和S^neig，将与其对应的目标函数分别表示为NPV^init、NPV^curr和NPV^neig。初始解S^init通过算法2生成。

给定当前解S^curr，其邻点解S^neig通过随机调整一个项目q中一个活动i的开始时间实现的。但需要满足以下条件：1) 活动i的开始时间s_i随机调整需在开始时间时间窗 $[e_{s_i}， l_{s_i}]$ 内进行。2) 调整i的开始时间调整后仍需满足项目网络的优先关系，否则，重新选择新的活动。3) 新得到的S^q与其他仍保持不变的单项目进度计划构成新的多项目进度计划安排S。该进度计划需满足资源约束，否则，重新开始选择新项目，最终得到可行的S^neig与其对应的NPV^neig。

算法2：初始解构造
输入：多项目相关参数，各活动成本c_i，活动工期d_i，r_ik 等
输出：可行进度计划S^init, 目标函数NPV^init
1　初始化：初始化禁忌列表，令Num:=0
2　初始化资源约束标记Flag=0
3　While Flag=0 do
4　　For q=1 to Q do
5　　　计算活动i的开始时间窗 $[e_{s_i}， l_{s_i}]$ (使用关键路径法)
6　　　While (优先关系不满足) do
7　　　　For i=1 to n^q do
8　　　随机选择一个开始时间s_i，且满足 ${s_i} \in [e_{s_i},l_{s_i}]$ ，及　　　　 ${s_i} \geqslant \mathop {\max }\limits_{j \in {\rm{PRED}}_i} \{ {s_j}\}$ ， ${s_i} \leqslant \mathop {\min }\limits_{j \in {\rm{SUCC}}_i} \{ {s_j}\}$
9　　　　 End for
10　　　　得到项目q的进度计划S^q
11　　　　判断是否满足优先关系
12　　　End while
13　　　得到项目q的进度计划S^q，且满足优先关系
14　　End for
15　　得到所有Q个项目的进度计划安排S= (S¹, S², …, S^Q)
16　　If (该进度计划安排S满足可重复使用资源约束) do
17　　　Flag=1
18　　Else:
19　　　继续执行
20　　End if
21　End While
22　利用3.1中的方法计算与S^init对应的目标函数NPV^init

3.3 移动定义与禁忌列表设计

本文采用一个四元组来表示算法从当前解到邻点解的移动 (在多项目中被选中的项目代号q, 在项目q中被选中的活动代号i, 活动i在当前解中的开始时间, 活动i在邻点解中的开始时间)。与移动定义相对应，采用一个三元组来表示某一移动的逆向移动 (在多项目中被选中的项目代号q, 在项目q中被选中的活动代号i, 活动i在移动前的开始时间)。当算法执行一次移动后，便把该移动的逆向移动保存到禁忌列表，避免其重新返回到已经探测过的当前解上。

禁忌列表保持一个固定的长度，采用先进先出FIFO (first-in-first-out) 的方式进行管理，即每当执行一次移动时，该移动的逆向移动被存入禁忌列表中，同时，最先进入列表的逆向移动被移出列表，从而解除其禁忌状态。此外，当某一被禁忌的移动能够生成比当前最好解还要好的邻点解时，可以基于特赦准则直接解除该移动的禁忌状态，使算法能够移动到该邻点解上以避免错失问题的最优解。

3.4 算法的停机准则及实施步骤

将问题的当前最好解和满意解分别表示为S^best和S^desi，与其对应的目标函数表示为NPV^best和NPV^desi。算法的停机准则设定为探测可行解的总数Num^stop，用Num记录算法在搜索过程中探测的可行解数，用TLL表示禁忌列表的长度。禁忌搜索启发式算法如算法3所示。

算法3：禁忌搜索算法
输入：各活动成本c_i，活动工期d_i，r_ik，Num^stop和TLL等参数
输出：进度计划S^best和NPV^best
1　初始化：初始化禁忌列表，令Num:=0
2　初始解构造 (算法2)，得到S^init和NPV^init
3　将当前解和当前最好解赋值为初始解，令S^curr:=S^init，NPV^curr:=　 NPV^init，S^best:=S^init，NPV^best:=NPV^init
4　While ( ${\rm{Num}} \lt {\rm{Nu}}{{\rm{m}}^{stop}}$ ) do
5　　基于S^curr生成 S^neig和NPV^neig
6　　Num=Num+1
7　　If (NPV^neig>NPV^best) do
8　　　令S^curr:=S^neig, NPV^curr:=NPV^neig, S^best:=S^neig, NPV^best:=　　　　 NPV^neig
9　　　If (生成 S^neig的移动不在禁忌列表) do
10　　　　将逆向移动加入禁忌列表TLL
11　　　Else：
12　　　　解除邻点禁忌
13　　　End if
14　　 Else:
15　　　令S^curr:=S^neig，NPV^curr:=NPV^neig
16　　　If (生成 S^neig的移动不在禁忌列表) do
17　　　　将逆向移动加入禁忌列表TLL
18　　　Else：
19　　　　继续执行
20　　　End if
21　　End if
22　End while

3.5 算法的改进措施

基于2.2节的3条性质，通过算法4来进行算法改进措施的实施。在禁忌搜索启发式算法中，对于问题的初始解和邻点解，均会使用上述措施对其中符合2.2节中3条性质所界定条件的活动进行移动，由此提高解的质量。因此，对于本文所研究的问题，改进版本的禁忌搜索启发式算法是原始禁忌搜索算法基于问题特点的一个创新性升级。

算法4：算法改进措施
输入：一个当前可行解S
输出：改进的进度计划S, 目标函数NPV
/利用性质3改进当前进度计划S /
1　For (q=1 to Q) do
2　　For (m=2 to M^q ) do
3　　　计算 ${\varDelta _1} = {s_{{i_m}}} - \mathop {\max }\limits_{j \in {{\rm{PRED}}_i}_m} \{ {s_j}\}$ 及　　　 ${\varDelta _2} = {s_{{i_m}}} + {d_{{i_m}}} - (\mathop {\max }\limits_{v = 1,\cdots ,m - 1} \{ {s_v} + {d_v}\} )$
4　　　 If (∆₁≥∆₂ ) do
5　　　　 ${s_{{i_m}}} = {s_{{i_m}}} - {\varDelta _2}$ ，更新S
6　　　　If (不满足资源约束 ) do
7　　　　　 ${s_{{i_m}}} = {s_{{i_m}}} + {\varDelta _2}$ ，恢复S
8　　　　Else:
9　　　　　继续执行
10　　　　End if
11　　　Else:
12　　　　继续执行
13　/利用性质1改进当前进度计划S /
14　For (q=1 to Q) do
15　　For (m=2 to M^q ) do
16　　　确定在活动i_m‒1与i_m之间完成非里程碑活动集合FM_m
17　　　For ( $i \in {{\rm{FM}}_m}$ ) do
18　　　　计算 ${\varDelta _1} = {s_i} - \mathop {\min }\limits_{j \in SUC{C_i}} \{ {s_j}\}$ 及 ${\varDelta _2} = {s_i} + {d_i} - ({s_{{i_m}}} + {d_{{i_m}}})$
19　　　　If (∆₁≥∆₂ ) do
20　　　　　 ${s_{{i_m}}} = {s_{{i_m}}} + {\varDelta _2}$ ，更新S
21　　　　　If (不满足资源约束 ) do
22　　　　　　 ${s_{{i_m}}} = {s_{{i_m}}} - {\varDelta _2}$ ，恢复S
23　　　　　　 ${s_{{i_m}}} = {s_{{i_m}}} + {\varDelta _1}$ ，更新S
24　　　　　　If (不满足资源约束 ) do
25　　　　　　　 ${s_{{i_m}}} = {s_{{i_m}}} - {\varDelta _1}$ ，恢复S
26　　　　　　Else:
27　　　　　　　继续执行
28　　　　　　End if
29　　　　　Else:
30　　　　　　继续执行
31　　　　　End if
32　　　Else:
33　　　　继续执行
34　　　End if
35　　End for
36　End for
37　/利用性质2改进当前进度计划S /
38　For (q=1 to Q) do
39　　For (m=2 to M^q ) do
40　　　确定在活动i_m‒1与i_m之间完成非里程碑活动集合FM_m
41　　For ( $i \in {{\rm{FM}}_m}$ ) do
42　计算 ${\varDelta _1} = {s_i} - \mathop {\max }\limits_{j \in {{\rm{PRED}}_i}} \{ {s_j}\}$ 及 ${\varDelta _2} = {s_i} + {d_i} - ({s_{{i_{m - 1}}}} + {d_{{i_{m - 1}}}})$
43　　　If (∆₁≥∆₂ ) do
44　　　　 ${s_{{i_m}}} = {s_{{i_m}}} - {\varDelta _2}$ , 更新S
45　　　　If (不满足资源约束 ) do
46　　　　　 ${s_{{i_m}}} = {s_{{i_m}}} + {\varDelta _2}$ ，恢复S
47　　　　Else:
48　　　　　继续执行
49　　　　End if
50　　　Else:
51　　　　继续执行
52　　　End if
53　　End for
54　End for

4. 计算实验

为验证算法对问题的求解效果并分析模型中关键参数对目标函数的影响，本节在随机生成的多项目调度问题标准算例库上，对禁忌搜索启发式算法进行大规模的计算实验。

4.1 计算实验设计

为更清晰准确地评价算法的绩效，体现3.5节中提出的改进措施对算法绩效提升的效果和贡献，设计两个版本的禁忌搜索算法进行对比测试。

1) 原始版禁忌搜索TS-NIM。该算法为不含改进措施的禁忌搜索启发式算法，即不使用3.5节中的改进措施对所生成的初始解和邻点解进行改进。

2) 改进版禁忌搜索TS-IM。该算法为含改进措施的禁忌搜索启发式算法，即在该算法的迭代搜索过程中，使用3.5节中的改进措施对所生成的初始解和邻点解进行改进。

同时，借鉴项目调度研究已有文献^[26]，将上述两个禁忌搜索算法与多重迭代改进 (multistart iteration improvement, MSII) 算法和随机抽样 (random sampling, RS) 算法进行对比，以使算法的评价结果更具说服力。需要说明的是，由于MSII具有与禁忌搜索算法相同的初始解构造和邻点生成方式，通过贪婪式策略搜索问题的满意解并以随机的方式跳出局部最优解。因此，在相同的停机准则下，该算法可以作为对比算法，用以评价禁忌搜索相比于普通启发式算法的优势；而RS作为一种随机抽样算法，其计算结果可为MSII提供对比基准。

计算实验在算例生成器ProGen^[27]生成的标准算例集合上进行，算例的参数设置如表2所示。其中，单项目中的非虚活动数n^q、网络复杂度 (network constrainedness, NC) 、资源因子 (resource factor, RF) 、资源强度 (resource strength, RS) 、项目截止时间D^q、里程碑活动数M^q、预付款比例γ^q、支付比例θ^q、折现率α均被设置为3个水平，在每一种参数取值组合下随机地生成2个算例，因此，上述9个参数3个取值水平的全因素实验共包含3⁹×2=39366个标准算例。

表 2 标准算例集合参数设置

Table 2. Parameter setting of standard instance set

算例参数	取值设置
项目数Q	3
非虚活动数n^q	10, 20, 30
单项目开始和结束活动数	从2、3和4中按等概率随机选取
单项目最大紧前紧后活动数	4
可重复使用资源种类数K	2
网络复杂度NC	1.2, 1.5, 1.8
资源因子RF	0.5, 0.75, 1
资源强度RS	0.5, 0.75, 1
活动资源需求量r_ik	从U[1, 10]中随机选取
活动工期d_i	从U[1, 10]中随机选取
活动成本c_i	从U[1, 10]中随机选取
活动挣值v_i	ρ_v·c_i，其中ρ_v取值从U[1.5, 1.8]中随机选取
里程碑活动数M^q	3, 4, 5
预付款比例γ^q	0.05, 0.1, 0.15
中间支付比例θ^q	0.8, 0.85, 0.9
开始时间I^q	从U[0, 5]中随机选取
折现率α	0.006, 0.008, 0.010
截止时间D^q	I^q+ρ_D·CPL。其中ρ_D为1.2, 1.4和1.6；CPL为关键路径

下载: 导出CSV

| 显示表格

对于一个算例，分别采用TS-NIM、TS-IM、MSII和RS 4种算法对其进行求解，将所得到的最好满意解称为已知最好解。从满意解质量和计算时间两方面定义如下5个指标反映算法的绩效。

1) 求得最好解的数量NBS。该指标反映某一算法得到与已知最好解相同的满意解的数量。

2) 满意解的平均相对偏差ARD。该指标反映某一算法得到的满意解与已知最好解的平均相对偏差。假定对于算例集合H中的某一算例h，已知最好解的目标值为 ${\rm{NPV}}_h^*$ ，被评价算法得到的满意解的目标值为NPV_h，则该满意解距离已知最好解的相对偏差为 ${\rm{RD}}_h = [({\rm{NPV}}_h^{^ * } - {\rm{NPV}}_h^{^{}})/{\rm{NPV}}_h^{^ * }] \times 100\%$ ；对于算例集合H来说， ${\rm{ARD }}= {{\displaystyle\sum\limits_{h \in H} {{\rm{RD}}_h} } \mathord{\left/ {\left| H \right|} \right. } }$ 。

3) 满意解的最大相对偏差MRD。该指标反映某一算法得到的满意解与已知最好解的最大相对偏差。在RD_h的基础上， ${\rm{MRD}} = {\text{ma}}{{\text{x}}_{h \in H}}\{ {{\rm{RD}}_h}\}$ 。

4) 满意解的平均计算时间ACT。该指标反映某一算法得到的满意解的平均计算时间。对于算例集合H中的算例h来说，被评价算法得到的满意解的计算时间为CT_h，则对于算例集合H来说，被评价算法的ACT按下式计算： ${\rm{ACT }}= {{\displaystyle\sum\limits_{h \in H} {{\rm{CT}}_h} } \mathord{\left/ {\left| H \right|} \right. } }$ 。

5) 满意解的最大计算时间MCT。该指标反映某一算法得到的满意解的最大计算时间。在CT_h的基础上，MCT为

$\qquad {\rm{MCT}} = {\text{ma}}{{\text{x}}_{h \in H}}\{ {{\rm{CT}}_h}\} 。$

上述4种算法均采用Python 3.8编程，在CPU主频为2.60 GHz、内存为 8 GB的个人计算机上运行。为了找到一组较为适合的算法参数，在具有代表性的小规模算例集合上对算法进行预测试。基于算法的预测试结果，将算法参数设置如下：Num^stop=10000·n^q，TLL=12，NINum^stop=10。其中，NINum^stop是MSII算法中允许的不改进迭代次数，即当算法迭代超过NINum^stop次当前解都无法得到改进时，就从另一个随机生成的可行解重新启动，开始新一轮的迭代从而避免算法搜索陷入局部最优。

4.2 算法的绩效评价

表3汇总4种算法的计算结果。对于全部算例来说，从代表满意解质量的指标NBS、ARD和MRD看出，算法TS-IM效果最好，其次为TS-NIM和MSII，RS效果最差；并且算法绩效随着活动规模增加而更加显著。因为启发式算法的搜索效率通常都优于简单搜索算法，且这种优势随着项目规模复杂程度的增加而增大。另外，对于TS的两个版本，使用了改进措施的版本TS-IM的优势较为明显，说明本文提出的针对问题特点的改进措施极大提升了满意解的质量。另外，根据运行时间指标ACT和MCT在所有算例上的计算结果可以看出，TS-IM耗时最长，但依然处于可接受的范围内，其次为TS-NIM、MSII、RS。因为TS-IM和TS-NIM搜索过程较为复杂，都需要较多的时间去搜索满意解，其中 TS-IM 由于对邻点解进行改进，每一个可行解均需要通过改进措施提升，因此耗费时间长于TS-NIM。

表 3 4种算法结果比较

Table 3. Comparison results of four algorithms

参数	取值	TS-IM					TS-NIM					MSII					RS
参数	取值	NBS	ARD	MRD	ACT	MCT	NBS	ARD	MRD	ACT	MCT	NBS	ARD	MRD	ACT	MCT	NBS	ARD	MRD	ACT	MCT
n^q	10	11831	0	0.02	12.99	14.01	744	0.03	0.13	9.23	9.87	547	0.03	0.14	8.96	9.08	0	0.04	0.14	8.01	8.56
	20	11224	0	0.03	26.18	35.32	1701	0.03	0.15	19.81	24.11	197	0.04	0.16	15.34	20.09	0	0.04	0.16	12.09	16.48
	30	10707	0	0.04	55.56	63.08	2415	0.03	0.14	33.08	36.52	0	0.05	0.15	28.27	33.12	0	0.05	0.15	20.03	25.09
所有算例		33762	0	0.04	31.58	63.08	4860	0.03	0.15	20.71	36.52	744	0.04	0.16	17.52	33.12	0	0.04	0.16	13.38	25.09

下载: 导出CSV

| 显示表格

4.3 改进措施的效果

对比禁忌搜索两个版本TS-IM和TS-NIM的计算结果，从算法评价指标NBS、ARD和MRD可以看出，TS-IM版本的NBS值为33 762，占据了85%以上的最优解。该版本的算法与最优解的平均距离ARD指标值为0，且MRD指标仅为4%，远远低于TS-NIM的MRD值 (15%)。因此，添加改进措施的算法TS-IM通过对生成的邻点解进行改进，大大提高算法解的质量，从而提高算法绩效。

绘制了4个算法的评价指标ARD随参数n^q、RF、RS和ρ_D变化趋势，如图1所示。其中，指标ARD值越小，表明算法绩效越好。由图1可见，TS-IM版本的算法在不同参数下均有最小的ARD值，几乎接近于0，即几乎所有参数组合下的最优目标值均由TS-IM得到。

图 1 ARD随相关参数的变化趋势

Figure 1. Variation trend of ARD with relative parameters

下载: 全尺寸图片幻灯片

4.4 关键参数的敏感性分析

基于最好算法TS-IM的计算结果，得到不同参数取值下的目标函数见表4，同时基于表4数据结果绘制的NPV随关键参数的变化趋势见图2。

表 4 不同参数取值下的目标函数计算结果

Table 4. Computational results of objectives with different parameter values

参数	取值	NPV	参数	取值	NPV
RF	0.5	93.91	θ^q	0.8	90.67
	0.75	92.36		0.85	94.12
	1	92.01		0.9	96.31
RS	0.5	92.10	α	0.006	103.41
	0.75	94.18		0.008	93.95
	1	95.52		0.01	84.48
M^q	3	92.11	ρ_D	1.2	93.57
	4	96.89		1.4	96.84
	5	102.29		1.6	103.27
γ^q	0.05	86.44
	0.1	95.89
	0.15	100.23

下载: 导出CSV

| 显示表格

从图2可以看出，对于参数RS和ρ_D，NPV随着参数取值的增大而增大，而对于参数RF，则呈现出相反的趋势。这可以解释如下。截止日期增大使得解空间规模变大，从而一定程度上会带来项目净现值的改善。资源强度RS反映了项目资源的供给水平，当RS数值较小时，资源可用量较小，因此同一时间可以安排的活动数目变少；而当RS较大时，资源可用量较大，活动之间受资源流的影响较小，自由度更大，因此更利于找到高质量的解，使得NPV上升。RF对资源的影响与RS则相反，较高的RF意味着更多的活动需要同一种资源，导致更多的资源流形成，因此大大减小了可行解的数量，进而导致NPV下降。

项目NPV随参数 ${M^q}$ 、 ${\gamma ^q}$ 和 ${\theta ^q}$ 的增加而逐渐增加。这一现象可以解释如下。里程碑活动数 ${M^q}$ 、业主预付款比例 ${\gamma ^q}$ 与中间支付比例 ${\theta ^q}$ 的增大，会使得一部分支付从项目的结束时刻提前到项目实施的过程中，这部分正现金流的提前必然会带来项目净现值的上升。此外，从目标函数可以看出，折现系数α在负指数函数的指数位置，该系数的增加必然使得目标值下降。这可以理解为折现率增大使得资金的时间价值随之变大，导致承包商使用资金的成本增加，从而使得项目净现值下降。

图 2 NPV随参数变化趋势

Figure 2. Variation trend of NPV with parameters

下载: 全尺寸图片幻灯片

4.5 管理启示与建议

在上述计算结果的基础上，可以从承包商的视角提出如下管理启示与建议。

1) 对于项目地点较为集中、所需资源通用性较强的多个并行实施项目，采取集中式的统一调度方式能够有效地提高资源的使用效率。而在此种情况下，本文所提出的模型和算法可以为多项目进度计划的安排提供直接的决策支持，从而有助于承包商更好地协调项目的现金流出与流入，获得一个较高的项目收益。

2) 为提高项目收益，承包商应尽可能地为项目进度计划的安排提供较为充裕的资源供给。同时，项目的计划工期也不宜设置得过紧，在安排多项目进度计划时才会有较大的调整余地，从而有利于改善项目收益。

3) 在与业主进行谈判时，承包商应尽可能地为每个项目争取一个较高的预付款比例和中间支付比例，并尽量增加项目执行过程中的中间支付次数，这会对项目净现值的改善产生直接且显著的效果。

4) 较低的资金使用成本会有利于项目收益的增加，为调高项目净现值，承包商应尽可能地降低贷款利率及资金使用机会成本。

5. 结论

本文研究了共享资源约束下的净现值最大化多项目调度优化问题。其中，每个项目拥有独立的活动网络、支付规则、开始时间和截止时间，企业的可重复使用资源总可用量给定，可以在多项目之间自由地共享，目标是在可重复使用资源的限制下，集中地安排多个项目的进度计划以实现多项目净现值的最大化。

首先提出该研究问题并论证其现实和理论意义。在此基础上，通过符号的定义对问题进行准确描述，进而构建问题的优化模型，提出模型的3条可用于提升目标函数的基本性质。根据问题的NP-hard属性，设计模型求解的禁忌搜索启发式算法，基于问题性质提出算法的改进措施。最后在随机生成的标准算例集合上，以多重迭代改进和随机抽样算法为对比算法，对所设计的算法进行对规模的计算测试，评价了算法绩效和改进措施的贡献，并对关键参数对目标函数的影响进行敏感性分析。基于本文的研究，得到如下结论。本文提出的基于改进措施的禁忌搜索算法TS-IM优于其他算法，特别是当活动规模增大时，优势体现得更加明显。净现值随参数RS和ρ_D增加而增加，而对于参数RF呈下降的趋势；另外，项目净现值对于参数M^q、γ^q和θ^q的呈现单调递增的趋势，而折现率则会负向影响项目净现值。

在本文的研究中，作者并没有考虑共享资源在不同项目之间的转运成本。在非共享资源参与的情况下，应综合考虑两种资源的关系及其对多项目净现值目标的影响。因此，在未来的研究中，作者会基于本文研究进行扩展，通过将上述因素考虑在内，使得论文的研究成果更贴近于实际。

图 1 ARD随相关参数的变化趋势

Figure 1. Variation trend of ARD with relative parameters

下载: 全尺寸图片幻灯片

图 2 NPV随参数变化趋势

Figure 2. Variation trend of NPV with parameters

下载: 全尺寸图片幻灯片

表 1 文献综述汇总

Table 1 Summary of literature review

文献	目标函数				资源类型
文献	工期	成本	净现值	其他	共享资源	非共享资源
Kurtulus等^[3]	√			√	√
Mohanty等^[4]	√	√		√	√
Lawrence等^[5]		√		√	√
Lova等^[6]	√				√
寿涌毅^[7]	√				√
Browninge等^[8]	√				√
王海鑫等^[9]	√				√
Hauder等^[10]	√				√
彭武良等^[11]	√				√
Chen等^[12]	√				√
Lee等^[13]	√					√
Confessore等^[14]	√					√
Homberger^[15]	√					√
Homberger^[16]	√					√
Zheng等^[17]	√					√
丰景春等^[18]	√					√
Liu等^[19]			√		√
Can等^[20]			√		√
El-Abbasy等^[21]	√	√			√
He等^[22]					√
刘万琳^[23]					√
本文			√		√

下载: 导出CSV

表 2 标准算例集合参数设置

Table 2 Parameter setting of standard instance set

算例参数	取值设置
项目数Q	3
非虚活动数n^q	10, 20, 30
单项目开始和结束活动数	从2、3和4中按等概率随机选取
单项目最大紧前紧后活动数	4
可重复使用资源种类数K	2
网络复杂度NC	1.2, 1.5, 1.8
资源因子RF	0.5, 0.75, 1
资源强度RS	0.5, 0.75, 1
活动资源需求量r_ik	从U[1, 10]中随机选取
活动工期d_i	从U[1, 10]中随机选取
活动成本c_i	从U[1, 10]中随机选取
活动挣值v_i	ρ_v·c_i，其中ρ_v取值从U[1.5, 1.8]中随机选取
里程碑活动数M^q	3, 4, 5
预付款比例γ^q	0.05, 0.1, 0.15
中间支付比例θ^q	0.8, 0.85, 0.9
开始时间I^q	从U[0, 5]中随机选取
折现率α	0.006, 0.008, 0.010
截止时间D^q	I^q+ρ_D·CPL。其中ρ_D为1.2, 1.4和1.6；CPL为关键路径

下载: 导出CSV

表 3 4种算法结果比较

Table 3 Comparison results of four algorithms

参数	取值	TS-IM					TS-NIM					MSII					RS
参数	取值	NBS	ARD	MRD	ACT	MCT	NBS	ARD	MRD	ACT	MCT	NBS	ARD	MRD	ACT	MCT	NBS	ARD	MRD	ACT	MCT
n^q	10	11831	0	0.02	12.99	14.01	744	0.03	0.13	9.23	9.87	547	0.03	0.14	8.96	9.08	0	0.04	0.14	8.01	8.56
	20	11224	0	0.03	26.18	35.32	1701	0.03	0.15	19.81	24.11	197	0.04	0.16	15.34	20.09	0	0.04	0.16	12.09	16.48
	30	10707	0	0.04	55.56	63.08	2415	0.03	0.14	33.08	36.52	0	0.05	0.15	28.27	33.12	0	0.05	0.15	20.03	25.09
所有算例		33762	0	0.04	31.58	63.08	4860	0.03	0.15	20.71	36.52	744	0.04	0.16	17.52	33.12	0	0.04	0.16	13.38	25.09

下载: 导出CSV

表 4 不同参数取值下的目标函数计算结果

Table 4 Computational results of objectives with different parameter values

参数	取值	NPV	参数	取值	NPV
RF	0.5	93.91	θ^q	0.8	90.67
	0.75	92.36		0.85	94.12
	1	92.01		0.9	96.31
RS	0.5	92.10	α	0.006	103.41
	0.75	94.18		0.008	93.95
	1	95.52		0.01	84.48
M^q	3	92.11	ρ_D	1.2	93.57
	4	96.89		1.4	96.84
	5	102.29		1.6	103.27
γ^q	0.05	86.44
	0.1	95.89
	0.15	100.23

下载: 导出CSV

参考文献(27)

[1]	张立辉, 郭欣雨. 考虑工作连续性的重复性项目鲁棒调度优化[J]. 科技管理研究, 2023, 43(14): 218-225. DOI: 10.3969/j.issn.1000-7695.2023.14.024 ZHANG Lihui, GUO Xinyu. Robust scheduling optimization of repetitive projects considering work continuity[J]. Science and Technology Management Research, 2023, 43(14): 218-225. DOI: 10.3969/j.issn.1000-7695.2023.14.024
[2]	RUSSELL A H. Cash flows in networks[J]. Management Science, 1970, 16: 357-373. DOI: 10.1287/mnsc.16.5.357
[3]	KURTULUS IB, DAVIS EW. Multi-project scheduling: Categorization of heuristic rules performance[J]. Management Science, 1982, 28(2): 161-172. DOI: 10.1287/mnsc.28.2.161
[4]	MOHANTY R U, SIDDIQ MK. Multiple projects-multiple resources-constrained scheduling: Some studies[J]. International Journal of Production Research, 1989, 27(2): 261-280. DOI: 10.1080/00207548908942546
[5]	LAWRENCE S R, MORTON E T. Resource-constrained multi-project scheduling with tardy costs: comparing myopic, bottleneck, and resource pricing heuristics[J]. European Journal of Operational Research, 1993, 64(2): 168-187. DOI: 10.1016/0377-2217(93)90175-M
[6]	LOVA A, MAROTO C, TORMOS P. A multicriteria heuristic method to improve resource allocation in multiproject scheduling[J]. European Journal of Operational Research, 2000, 127(2): 408-424. DOI: 10.1016/S0377-2217(99)00490-7
[7]	寿涌毅. 随机抽样算法在多项目调度中的应用[J]. 管理工程学报, 2005, 19(3): 32-35. DOI: 10.3969/j.issn.1004-6062.2005.03.007 SHOU Yongyi. Application of random sampling algorithm in multi-project scheduling[J]. Journal of Management Engineering, 2005, 19(3): 32-35. DOI: 10.3969/j.issn.1004-6062.2005.03.007
[8]	BROWNING T R, YASSINE A A. Resource-constrained multi-project scheduling: priority rule performance revised[J]. International Journal of Production Economics, 2010, 126(2): 212-228. DOI: 10.1016/j.ijpe.2010.03.009
[9]	王海鑫, 王祖和, 温国锋, 等. 自适应粒子群算法求解资源受限多项目调度问题[J]. 管理工程学报, 2017, 31(4): 220-225. WANG Haixin, WANG Zuhe, WEN Guofeng, et al. Adaptive particle swarm algorithm for solving resource-constrained multi-project scheduling problems[J]. Journal of Management Engineering, 2017, 31(4): 220-225.
[10]	HAUDER V A, BEHAM A, RAGGL S, et al. Resource-constrained multi-project scheduling with activity and time flexibility[J]. Computers & Industrial Engineering, 2020, 150: 106857.
[11]	彭武良, 陈良威, 马雪丽. 分散式项目群调度的双目标优化方法研究[J]. 管理工程学报, 2021, 35(5): 131-140. PENG Wuliang, CHEN Liangwei, MA Xueli. Research on bi-objective optimization method of distributed project group scheduling[J]. Journal of Management Engineering, 2021, 35(5): 131-140.
[12]	CHEN H, DING G, ZHANG J, et al. A filtering genetic programming framework for stochastic resource constrained multi-project scheduling problem under new project insertions[J]. Expert Systems with Applications, 2022, 198: 116911. DOI: 10.1016/j.eswa.2022.116911
[13]	LEE Y, KUMARA S R T, CHATTERJEE K. Multiagent based dynamic resource scheduling for distributed multiple projects using a market mechanism[J]. Journal of Intelligent Manufacturing, 2003, 14: 471-484. DOI: 10.1023/A:1025753309346
[14]	CONFESSOR G, GIORDANI S, RISMONDO S. A market-based multi-agent system model for decentralized multi-project scheduling[J]. Annals of Operations Research, 2007, 150: 115-135. DOI: 10.1007/s10479-006-0158-9
[15]	HOMBERGER J. A multi-agent system for the decentralized resource-constrained multi-project scheduling problem[J]. International Transactions in Operational Research, 2007, 14(6): 565-589. DOI: 10.1111/j.1475-3995.2007.00614.x
[16]	HOMBERGER J. A (µ, λ) -coordination mechanism for agent-based multi-project scheduling[J]. OR Spectrum, 2012, 34: 107-132. DOI: 10.1007/s00291-009-0178-3
[17]	ZHENG Z, GUO Z, ZHU Y, et al. A critical chains based distributed multi-project scheduling approach[J]. Neurocomputing, 2014, 143: 282-293. DOI: 10.1016/j.neucom.2014.04.056
[18]	丰景春, 施嘉锋. 基于遗传算法的工程项目群工期-费用优化研究[J]. 科技管理研究, 2020, 40(20): 212-218. FENG Jingchun, SHI Jiafeng. Research on project duration-cost optimization based on genetic algorithm[J]. Science and Technology Management Research, 2020, 40(20): 212-218.
[19]	LIU S, WANG C. Profit optimization for multiproject scheduling problems considering cash flow[J]. Journal of Construction Engineering and Management, 2010, 136: 1268-1278. DOI: 10.1061/(ASCE)CO.1943-7862.0000235
[20]	CAN A, GÜNDÜZ U. Multi-project scheduling with two-stage decomposition[J]. Annals of Operations Research, 2014, 217: 95-116. DOI: 10.1007/s10479-014-1555-0
[21]	EL-ABBASY MS, ELAZOUNI A, ZAYED T. Generic scheduling optimization model for multiple construction projects[J]. Journal of Computing in Civil Engineering, 2017, 31: 04017003. DOI: 10.1061/(ASCE)CP.1943-5487.0000659
[22]	HE Y, HE Z, WANG N. Tabu search and simulated annealing for resource-constrained multi-project scheduling to minimize maximal cash flow gap[J]. Journal of Industrial & Management Optimization, 2021, 17(5): 2451-2474.
[23]	刘万琳, 张静文, 刘婉君. 带有资源柔性约束的max-NPV分布式多项目调度问题[J]. 运筹与管理, 2021, 30(8): 37-43. LIU Wanlin, ZHANG Jingwen, LIU Wanjun. Max-NPV distributed multi-project scheduling problem with resource flexibility constraints[J]. Operations Research and Management, 2021, 30(8): 37-43.
[24]	BLAZEWICZ J, LENSTRA J K, RINNOOY K A H G. Scheduling subject to resource constraints: classification and complexity[J]. Discrete Applied Mathematics, 1983, 5(1): 11-24. DOI: 10.1016/0166-218X(83)90012-4
[25]	PELLERIN R, PERRIER N, BERTHAUT F. A survey of hybrid metaheuristics for the resource-constrained project scheduling problem[J]. European Journal of Operational Research, 2020, 280(2): 395-416. DOI: 10.1016/j.ejor.2019.01.063
[26]	MIKA M, WALIGÓRA G, WęGLARZ J. Tabu search for multi-mode resource-constrained project scheduling with schedule-dependent setup times[J]. European Journal of Operational Research, 2008, 187(3): 1238-1250. DOI: 10.1016/j.ejor.2006.06.069
[27]	KOLISCH R, SPRECHER A, DREXL A. Characterization and generation of a general class of resource-constrained project scheduling problems[J]. Management Science, 1995, 41(10): 1693-1703. DOI: 10.1287/mnsc.41.10.1693

施引文献

资源附件(0)

图(2) / 表(4)

计量

文章访问数: 134
HTML全文浏览量: 38
PDF下载量: 4
被引次数: 0

1. 文献综述
1.1 资源约束多项目调度问题
1.2 考虑现金流的多项目调度问题
2. 共享资源约束优化模型的构建与分析
2.1 问题表述及模型构建
2.2 模型性质分析
3. 禁忌搜索启发式算法设计
3.1 解的表示以及目标函数计算
3.2 初始解构造与邻点解生成
3.3 移动定义与禁忌列表设计
3.4 算法的停机准则及实施步骤
3.5 算法的改进措施
4. 计算实验
4.1 计算实验设计
4.2 算法的绩效评价
4.3 改进措施的效果
4.4 关键参数的敏感性分析
4.5 管理启示与建议
5. 结论

1. 文献综述
1.1 资源约束多项目调度问题
1.2 考虑现金流的多项目调度问题
2. 共享资源约束优化模型的构建与分析
2.1 问题表述及模型构建
2.2 模型性质分析
3. 禁忌搜索启发式算法设计
3.1 解的表示以及目标函数计算
3.2 初始解构造与邻点解生成
3.3 移动定义与禁忌列表设计
3.4 算法的停机准则及实施步骤
3.5 算法的改进措施
4. 计算实验
4.1 计算实验设计
4.2 算法的绩效评价
4.3 改进措施的效果
4.4 关键参数的敏感性分析
4.5 管理启示与建议
5. 结论

参考文献(27)

施引文献

资源附件(0)

共享资源约束净现值最大化多项目调度及其禁忌搜索启发式算法

作者简介: 何华(1984—)，女，山西省人，博士研究生，主要研究方向为项目调度及优化。Email: 365074073@qq.com

计量

出版历程