有竞争的多项目并行柔性协作计划与调度模型研究

Research on a Model of Multi-Project Parallel Scheduling with Flexible Competitive Collaboration Planning

摘要: 针对多项目管理中资源冲突的问题，本文提出以项目总成本最小和多项目工期最短为目标，任务可任意拆分外包，且有多个协作伙伴竞争的多项目并行柔性协作计划与调度模型；改进了NSGA-II算法求解模型，采用了包含任务协作比例、协作伙伴和优先级的三维染色体编码方案标识任务属性。通过工程实例验证，证明了模型的实用性和算法的有效性，该优化方法能够有效协调项目间资源分配，提高企业多项目管理效率。

Abstract: To solve the resource conflict in the process of implementation of the multi-project management, a model of multi-project parallel scheduling with flexible competitive collaboration planning in which tasks can be outsourced arbitrarily and be competed among multiple partners was proposed to minimize the total cost of the projects and the duration of each project. According to the characteristic of the problem, this paper designed an improved NSGA-II algorithm for the sched-uling model, including the three-dimensional chromosome encoding scheme to identify the at-tributes of collaboration ratio, partners and priorities. With the practice project confirmation, the practicality of this model and the validity of this algorithm are verified. The optimization method can effectively coordinate the resource allocation among projects and improve the efficiency of multi project management as well.

1. 引言

随着企业内部环境的转变以及外部因素的改变，传统的多项目管理已经不能很好的适应市场需求，国内企业的改革正在向施工设计总承包和专业总承包方向发展，逐步实现由现行的劳动力密集型向知识密集型、管理密集型的企业模型转变 [1] 。当企业承包多个项目，并行项目之间往往会占用相同的资源，而资源数目往往有限，引入外协可以缩短工期但会导致项目总成本的增加，如何协调多个项目间的资源竞争，是否选择外协以及协作伙伴和协作比例的确定，是决策者需要解决的重要问题。目前，针对多项目协作计划调度的研究比较有限。Verellis和Carlo [2] 等人提出了多模式资源受限条件下的多项目进度问题，以实现多个项目规划净现值最大为目标，采用拉格朗日分解法求解以确定项目中每个任务的模式没有考虑并行协作的因素；Hartmann [3] 提出了一种启发式算法(自适应遗传算法)来解决RCPSP；AL-Fawzan [4] 设计了一个既用时短又少受突发事件影响的项目进度计划，引入鲁棒概念，构建了一个双目标资源受限项目进度计划模型，同时考虑鲁棒最大化和完成时间最小化两个目标，并开发了一种禁忌搜索算法生成有效解决方案近似集，但未考虑项目资源约束；杨雪松和胡昊 [5] 等发现多项目管理中的行为效应、多任务工作等问题，集中研究了关键链管理，提出了关键链多项目管理方法(CCMPM)，研究范围较为局限；寿涌毅 [6] 提出用拉格朗日分解法来解决多项目调度问题，将多项目管理问题分解成独立的最大流问题，操作资源配置，以求得逼近资源配置的最优方案，但未引入多个协作伙伴竞争机制；周永华 [7] 主要研究如何对多个项目的资源进行配置，建立了环境过程经营配置优化模型，针对多项目环境下资源会发生冲突的情况，他提出统一的时间窗和栈技术，用遗传算法解决随机资源分配的问题，但仅针对单目标进行优化。本文针对多项目协作计划与调度产生的关键资源冲突的问题，提出以多项目工期最短和项目总成本最低为目标的有竞争的多项目并行柔性协作计划与调度模型，设计了改进的NSGA-II算法进行优化求解，得到的调度方案可确定各任务的协作比例、协作伙伴和优先级，能够有效协调项目间资源分配，提高企业多项目管理效率。

2. 模型建立

2.1. 问题描述

假设共有N个独立项目，任务总数为n，项目集合为 $P=\left\{P_i|i=1,2,\cdots ,N\right\}$ ，每个项目包含 $J_i$ 个任务， $W_{ij}$ 表示项目 $P_i$ 中的j任务，任务均可任意拆分外协，如果任务外协，则有 $M_{ij}$ 个协作伙伴竞争，本文规定外包任务不允许转包，任务开工时即占用一定数量的某种关键资源，同一任务不可同时占用多种关键资源，任务结束时关键资源即被释放，当某种关键资源的全部数量被占用，其他任务不得占用。本文在满足逻辑约束和关键资源等各种约束条件的前提下，以项目总成本最少和项目工期最短为优化目标，实现多项目的并行调度并对协作计划方案进行整体优化。

2.2. 目标函数

本模型需要同时优化以下目标函数：

1) 项目总成本

$\text{V}={\displaystyle \underset{i=1}{\overset{N}{\sum }}{\displaystyle \underset{j=1}{\overset{J_i}{\sum }}\left[\left(1-x_{ij}\right)\cdot v_{ij}+{\displaystyle \underset{m=1}{\overset{M_{ij}}{\sum }}{v}_{ij}^m\cdot x_{ij}\cdot {\text{H}}_{ij}^m}\right]}}$

$x_{ij}=\{\begin{array}{l}0, x_{ij}\le 0.2\\ 1, x_{ij}>0.8\end{array}$

其中 $v_{ij}$ 表示任务 $W_{ij}$ 的自制价格， $x_{ij}$ 表示任务的外协比例， $x_{ij}\in \left[0,1\right]$ ，规定任务仅有较低比例需要自制或外协时，考虑到人力物力调用产生的额外代价更高，则将该任务确定为完全外协或完全自制， $v_{ij}^m$ 表示任务 $$ 的协作伙伴m的投标价格， ${\text{H}}_{ij}^m\in \left\{0,1\right\}$ ， ${\text{H}}_{ij}^m=1$ 表示协作伙伴m被任务 $W_{ij}$ 选中， ${\text{H}}_{ij}=0$ 表示协作伙伴m未被任务 $W_{ij}$ 选中。

2) 项目工期

$T_i={\displaystyle \underset{i\in C_i}{\sum }\left[t_{ij}\cdot \left(1-x_{ij}\right)+{\displaystyle \underset{m=1}{\overset{M_{ij}}{\sum }}{t}_{ij}^m\cdot x_{ij}\cdot {\text{H}}_{ij}^m}\right]}$

其中 $T_i$ 表示项目 $P_i$ 的工期， $C_i$ 表示项目 $P_i$ 关键路径上所有任务的集合， $t_{ij}$ 表示任务 $W_{ij}$ 的自制周期， $t_{ij}^m$ 表示任务 $W_{ij}$ 的协作伙伴m的施工周期，任务外协部分需在自制部分完工后才可开工。

2.3. 约束条件

本模型需满足逻辑约束和单个项目工期约束 [8] 外，由于关键资源数目有限，项目任务间会竞争资源，还需满足以下约束条件：

$S_{ai}\ge S_{bj}+T_{bj}^k,{\phi }_{bj}\ge {\phi }_{ai}$

其中 $S_{ij}$ 表示任务 $W_{ij}$ 的开工时间， ${\phi }_{ij}$ 表示任务 $$ 的优先级， $T_{ij}$ 表示任务 $W_{ij}$ 占用关键资源的时间，当发生关键资源冲突时，优先级大的任务优先占用关键资源， ${\phi }_{ib}\ge {\phi }_{ia}$ 表示在同一项目中任务 $W_{ib}$ 优先任务 $W_{ia}$ 占用关键资源k， ${\phi }_{bj}\ge {\phi }_{ai}$ 表示在不同项目中任务 $W_{bj}$ 优先任务 $W_{ai}$ 占用关键资源k。

3. 算法设计

本文构造了一种结合差分进化算法 [8] 和NSGA-II算法 [9] 的新型算法求解问题。首先通过三维染色体编码方案标识任务属性，其次，采用结合信号量机制 [10] 的拓扑排序 [11] 解码得到关键路径上的任务序列，再将遗传算法和差分进化算法结合进行交叉与变异操作，最后基于NSGA-II算法的非支配排序 [12] 选择得到多目标Pareto最优解集 [13] 。

3.1. 编码方案

基于多项目协作计划特点，本文为每个项目的每个任务设计了三维染色体：1) 协作染色体。表示对应任务的协作比例，以0~1之间的随机数表示，规定任务仅有较低比例需要自制或外协时相应地完全自制或外协；2) 协作伙伴染色体。表示对应任务中标的协作伙伴h，本文设定每个任务有三个协作伙伴参与竞标，h为1~3之间的随机整数。3) 优先级染色体。表示对应任务的优先级 $\phi$ ， $\phi$ 为1~n之间的随机整数，规定数字不允许重复，当任务发生关键资源冲突时，优先级大的任务优先占用关键资源。染色体编码方案如图1所示：

Figure 1. Three-dimensional chromosome encoding scheme

图1. 三维染色体编码方案

由图1可见，任务 $W_{12}$ 的外协比例为0.5，协作伙伴1中标，优先级为3，而任务 $W_{21}$ 的外协比例为0，协作伙伴3中标，优先级为18，当任务 $W_{12}$ 和任务 $W_{21}$ 发生关键资源冲突时，任务 $$ 优先占用关键资源，以此类推。

3.2. 交叉与变异操作

本文设计的三条染色体具有不同特征，对其采用的交叉与变异操作分别如下。

1) 协作染色体

针对多项目的各个任务均可任意拆分外协的特性，本文基于具有自适应算子 [14] 的差分进化算法 [15] 对协作染色体进行交叉与变异操作，该算法有助于在搜索过程中保持种群多样性，避免过早陷入局部最优解，增加搜索到全局最优解的概率，本文设计的自适应变异算子见式(1)，自适应交叉算子见式(2)：

$\lambda ={\text{e}}^{1-\frac{G_m}{G_m+1-G}},F=F_0\cdot 2^{\lambda }$ (1)

其中 $$ 表示变异算子， $G_m$ 表示最大进化代数，G表示当前进化代数。

(2)

其中 $rand\left(0,1\right)$ 表示0~1之间的随机数。

2) 协作伙伴染色体

本文对协作伙伴染色体选择单点交叉策略，以及随机变异策略。

3) 优先级染色体

针对任务优先级不允许重复的特性，选择SEC交叉策略 [16] ，以及交换变异策略。

3.3. 算法流程

1) 随机生成种群规模为 $N_p$ 的初始种群 $P_0$ ；

2) 通过基于改进的拓扑排序的并行调度算法得到对应的目标函数值，再对初始种群按照支配等级和拥挤距离进行非支配排序；

3) 设当前进化代数为 $d=1$ ；

4) 从父代种群中选择较优的子种群 $Q_1$ ；

5) 基于差分进化算法对父代种进行交叉、变异操作，得到新种群 $Q_2$ ；

6) 合并两个种群得到 $Q=Q_1\cup Q_2$ ，对Q计算目标函数值并进行非支配排序(参照步骤2)，基于精英保留策略从中选择较优的 $N_p$ 个个体，得到子代种群 $P_t$ ；

7) 令 $d=d+1$ ，如果 $d\le G_{\max }$ ，跳至步骤3；否则，进行步骤8；

8) 保存运行结果，输出Pareto最优解集，并根据决策者偏好输出对应调度计划的甘特图，算法终止。

4. 仿真结果分析

算法参数设置如下：种群规模 $$ ，交叉概率 $P_c=0.9$ ，变异概率 $P_m=0.1$ ，最大进化代数 $i_{\max }=500$ ，其他参数略。将本文模型及其算法应用于Z建筑公司承包的2个项目，项目A共有16个任务，项目B共有13个任务，对这29个任务依次连续编号，表1，表2表示项目A和B实施过程中任务的相关信息。图2为程序运行后生成的多项目多目标Pareto最优解集和数据插值生成的三维Pareto最优边界曲面，选取了一种多项目并行调度方案生成的甘特图如图3所示，表3抽取了部分具有代表性的Pareto最优解集。

为验证模型及算法效果，在相同参数下，采用基本NSGA-II算法求解任务有条件拆分外协的多项目并行协作计划与调度模型，结果如表4所示。对比结果可知，采用本文设计的新型算法求解模型所得的项目总成本更少且项目工期更短，优化效果更加出色。由于工期和成本之间存在制约关系，无法进行同时优化。外协任务数量增多，项目工期下降，项目总成本上升，而自制任务数量的增多则会导致项目工期上升，项目总成本下降。因此，项目承办方需结合实际情况选择合适的协作伙伴组合以及调度方案。若项目承办方希望完工周期最短且预算足够，可选择方案1；若要求项目成本最低，且拖期对工程影响很小，可选择方案4；若项目承办方希望项目A尽快完工，可选择方案2；若希望项目B尽快完工，可选择方案3。

Figure 2. Multi-objective Pareto optimal solution set and Pareto optimal boundary surface

图2. 多目标Pareto最优解集和Pareto最优边界曲面

Figure 3. Multi-project scheduling Gantt chart

图3. 多项目调度甘特图

Table 1. Logical relation constraints, costs and cycles under complete homemade and outsourcing among the tasks of Project A

表1. 项目A任务逻辑关系约束、关键资源占用量和完全自制和外协条件下的成本和周期

Table 2. Logical relation constraints, costs and cycles under complete homemade and outsourcing among the tasks of Project B

表2. 项目B任务逻辑关系约束、关键资源占用量和完全自制和外协条件下的成本和周期

Table 3. Pareto partial optimal solution set of a model of multi-project parallel scheduling with flexible competitive collaboration planning

表3. 多项目并行柔性协作计划与调度模型的Pareto部分最优解集

5. 结束语

本文在研究资源受限下多项目并行协作计划与调度的基础上，考虑多个协作伙伴竞标任务且任务均可任意拆分外协的情况，建立了有竞争的多项目并行柔性协作计划与调度模型。针对模型特点，设计了一种改进的NSGA-II算法求解，其中三维染色体的编码方案可标识多种任务属性(任务协作比例、协作伙伴和优先级)，解码时采用结合信号量机制的拓扑排序算法，并引入差分进化算法对染色体的变异和交叉操作进行改进，最后，通过工程实例验证并与其他算法进行比较，验证了模型的实用性和算法的有效性。

Table 4. Pareto partial optimal solution set of a model of multi-project parallel scheduling with competitive collaboration planning

表4. 多项目并行协作计划与调度模型的Pareto部分最优解集

基金项目

扬州大学信息工程学院2018年校大学生科创基金项目(x20180309)，扬州大学创新创业学院2018年大学生创新创业训练计划项目(C201811117013Y)。

参考文献