摘要：在竞争激烈的当今社会，越来越多的企业面对多项目管理的问题。如何有效的调度各个项目，是企业所面临的一个难题。本文从另一种算法（DFS，Depth-First Search，深度优先搜索）着手来分析多项目的调度管理问题，并结合实例进行分析，从而验证算法的有效性。

　　论文关键词：多项目，多项目管理，DFS

　　
　　一、引言

　　
　　当今，越来越多的企业或组织采用项目这一形式进行变革或创新，以面对日益激烈的市场竞争。项目，作为21世纪的“新宠”，简单地说，就是在特定的时间、预算、资源限定内，为实现某种目的而相互联系的一次性工作任务。一般来说，项目具有如下的基本特点：

　　
　　（1）一次性一次性是项目与其他重复性运行或操作工作最大的一个区别。项目有明确的起点和终点，没有可以完全照搬的先例，也不会有完全相同的复制。项目的其他属性都是从这一特点衍生出来的。

　　
　　（2）独特性

　　
　　每个项目都是独特的。或者其提供的产品或服务有其自身的特点；或者其提供的产品或服务虽然与其他项目类似，但是其时间和地点，内部和外部的环境，自然和社会条件却有别于其他项目，因此项目的过程总是独一无二的，不可能存在完全相同的两个项目。

　　
　　（3）目标的确定性

　　
　　项目必需要有确定的目标：

　　
　　（a）时间性目标，即在规定的时段内或规定的时点之前完成；

　　
　　（b）成果性目标，即提供某种规定的产品或服务；

　　
　　（c）约束性目标，即不超过规定的资源限制；

　　
　　（d）其他需满足的要求，包括必须满足的要求和尽量满足的要求；

　　
　　目标的确定性允许有一个变动的幅度，也就说目标是可以修改。不过一旦项目目标发生实质性的变化，它就不再是原来的项目了，而将产生一个新的项目。

　　
　　（4）活动的整体性

　　
　　项目中的一切活动都是有联系的，构成一个统一的整体。多余的活动是不必要的，缺少某些活动必将损害项目目标的实现。

　　
　　（5）组织的临时性和开放性

　　
　　项目团队在项目的全过程中，其人数，成员，职责总是在不断变化的。某些成员是借调来的，项目终结时团队要解散，人员要转移。参与项目的组织往往有多个，甚至几十个或更多，这些组织按矩阵型结构排列。他们通过协议或合同以及其他的社会关系组织到一起，在项目的不同时段不同程度的介入项目活动。可以说，项目组织没有严格的边界，是临时性的开放性的。这一点与一般企、事业单位和政府机构组织不一样。

　　
　　（6）成果的不可挽回性

　　
　　项目的一次性属性决定了项目不同于其他事情可以先试着做，如果作坏了还可以重来；也不同于产品的生产批量，合格率达99.99%就认为是很好的了。项目在一定条件下启动，一旦失败就永远失去了重新进行原项目的机会。所以项目有很大的不确定性和风险性。

　　
　　二、多项目管理

　　
　　以上是我们理论意义上的项目，但在实际当中，企业面对的更多是单项目与多项目的问题。

　　
　　单项目的调度管理相比而言，比较容易处理，运用传统的一些技术，比如CPM，PERT，就可以很好的解决单个项目的管理。

　　
　　而多项目管理的问题比较棘手，涉及到在有限资源的约束下调度各个项目，以保证提高企业整体的效率。本文就是来着重阐述资源受限情况下的多项目调度问题。

　　
　　1.多项目管理的概念

　　
　　多项目管理是指在项目经理和项目组织的共同努力下，综合运用系统理论和方法对项目及其资源进行计划、组织、协调、控制，旨在实现项目的特定目标的管理方法体系。多项目管理是站在企业层面对现行组织中的所有项目进行筛选、评估、计划、执行与控制的项目管理方式。与单项目管理不同，单项目管理是假定在资源充分得到保障的前提下进行的管理，而多项目管理是在企业存在多项目的前提下，如何合理的分配企业有限的资源，以达到企业整体的效率最高。

　　
　　2.实施多项目管理的优点

　　
　　a）从企业战略目标出发。多项目管理的实质就是合理在项目之间分配企业有限的资源，是从整体的角度来考虑，是以企业总的战略目标为指导的！

　　
　　b）提高资源的利用率。资源在各个项目之间进行有效的分配，不会出现所谓的资源闲置的情况，极大地提高资源的利用率和优化度！

　　
　　c）降低项目实施的风险。采用单项目的管理思维去管理多项目，很容易在项目的进度、资源的合理安排上产生风险，而多项目的管理思维却可以很好的解决这个问题。

　　
　　d）加强组织内部的沟通与交流。多项目的管理，更进一步的把职能部门和项目组联系在一起，不仅各个项目之间的联系加强，项目和其他非项目部门的联系也进一步加强，这都是以企业总体目标的为导向的。

　　
　　三、DFS算法描述

　　
　　1.图的定义

　　
　　图（graph）是数据结构G=（V，E），其中V（G）是G中的结点的有限非空集合，结点的偶对称为边（edge），E（G）是G中边的有限集合。图的的结点称为顶点（vertices）。

　　
　　有向图，若图G中的每条边都是有方向的，则称G为有向图（Digraph）。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。有向边也称为弧（Arc），边的始点称为弧尾（Tail），终点称为弧头（Head）。

　　
　　2.深度优先搜索（Depth-First Search，DFS）

　　
　　假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点（源点），则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点（亦称为从源点可达的顶点）均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。

　　
　　图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索（Depth-First Search）。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。

　　
　　3.改进的DFS算法过程

　　
　　首先建立两个数组序列，记为A[Tij]（i，j=1，2，3…n，T表示任两个接点之间的遍历时间，T12表示接点1和2之间的遍历时间），B[n]（n=1，2，3…n，表示接点）下面开始进行检索，并填充至B中。设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边（x，y）。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边（x，y）到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点（即从源点可达的所有顶点）都已被访问过，遍历过程结束。由于一个图的遍历结果不止一种，我们要讨论：当一个接点仅有一个邻接接点时，添加至B中，当一个接点（假定为M）下一个遍历的接点都是多个时，我们选取与M接点时间最长的下一个接点（假定为N），我们将接点N添加至B中。

　　这是因为到并行工作的进度取决于工时最长的活动，要注意，严格按照顺序依次添加。添加完毕，形成一个完整的B数组序列，将数组B中接点依次按两两组合的形式添加至A中i和j的位置，形成完整A数组。最后将A中所有的时间相加得出一个遍历所有接点的满意时间。

　　
　　四、实例分析

　　
　　为了验证算法的有效性，本文采用文献[4]的模具生产实例进行检验，此实例包含3个具有相同网络结构的项目，其网络结构图如图1所示。

　　
　　改进的DFS算法实现资源约束条件下多项目的调度

　　
　　图1网络结构图

　　
　　每个项目含有16个任务，所有的16个任务共享13中资源，在不同的项目中任务的工期是有所不同的。虽然企业中多项目是并存的，但我们总是可以给这些项目设置一定的优先级，即权重。我们假设w1=0.5，w2=0.3，w3=0.2（w1表示项目的权重，其他类推）。三个项目同时开始，在没有资源约束的情况下，三个项目的完工时间分别是33天，43天，38天，计划的最晚交货期是48、63和62天，下面的表1说明任务的资源需求和工期。

　　
　　表1：

　　

　　任务

　　资源

　　P1i

　　P2i

　　P3i

　　1

　　1

　　4

　　5

　　4

　　2

　　1

　　3

　　6

　　6

　　3

　　2

　　2

　　2

　　1

　　4

　　3

　　4

　　3

　　4

　　5

　　4

　　3

　　2

　　3

　　6

　　5

　　5

　　6

　　6

　　7

　　6

　　4

　　6

　　3

　　8

　　7

　　2

　　3

　　2

　　9

　　2

　　1

　　1

　　1

　　10

　　7

　　2

　　2

　　2

　　11

　　8

　　4

　　3

　　3

　　12

　　9

　　3

　　4

　　3

　　13

　　10

　　3

　　2

　　4

　　14

　　11

　　2

　　4

　　2

　　15

　　12

　　3

　　3

　　4

　　16

　　13

　　4

　　4

　　4

　　
　　其中，P1i表示项目1的各个任务的工期，其他依此类推。

　　
　　下面我们利用改进的DFS算法来求该实例的多项目调度问题。由前面所述的改进DFS算法我们分析项目的网络结构图，在图的遍历过程发现P16＞P15（项目2和3也是这种情况），由于DFS算法就是图的遍历，也就是说要图的各个接点都要遍历到，即访问到任何一个接点，所以在访问P16的时候，只要资源不发生冲突，就可以并行的访问P15，因为P16＞P15，由此得出的结论就是项目的工期完全由遍历的任务工期之和决定的，当然了应当排除那些并行的任务之中工期短的那些任务。

　　
　　所以，Pi=Pi1 +Pi2 +Pi6 +Pi7 +Pi8 +Pi12 +Pi13 +Pi14 +Pi15 +Pi16 （i=1，2，3，Pi表示三个项目）

　　
　　可以计算出项目1的总工期是：P11 +P12 +P16 +P17 +P18 +P112 +P113 +P114 +P115 +P116=4+3+5+4+2+3+3+2+3+4=33（天），

　　
　　同理可以知道项目2的工期：P21 +P22 +P26 +P27 +P28 +P212 +P213 +P214 +P215 +P216+7=5+6+6+6+3+4+2+4+3+4+7=43+7=50（天），对式中的7说明：由于项目1的任务1和2共享一种资源，所以项目2的开始时间就是P11 +P12=3+4=7（天）。

　　
　　项目3的工期：P31 +P32 +P36 +P37 +P38 +P312 +P313 +P314 +P315 +P316+18=4+6+6+3+2+3+4+2+4+4+18=38+18=56（天），对式中的18说明：由于项目1和2它们各自的任务1和2共享一种资源，所以项目3的开始时间就是P11 +P12 +P21 +P22=3+4+5+6=18（天）。

　　
　　本文的求解过程完全可以通过计算机编程来实现，能够提高过程的效率。与其他一些调度算法相比，工期有明显的缩短。通过国内的一些算法我们可以清楚的比较出来，这些算法文献3都给出了结论，如表2。

　　
　　表2：

　　

　　算法

　　项目1

　　项目2

　　项目3

　　SASP

　　33

　　50

　　58

　　MAXTWK

　　47

　　43

　　56

　　多优先规则算法

　　42

　　54

　　58

　　
　　当然了，关于多项目的调度问题国内外许多学者提出了很多不同的实现方法，各个方法都各有优缺点，本算法特别适用于项目的网络结构图能转化为图的这种结构形式，以便通过DFS算法实现。

　　
　　五、结论

　　
　　本文借鉴了许多关于多项目管理在资源受限情况的调度问题，和其他的算法相比实质基本上一致，只不过是采用了一种新的算法，即DFS算法，当然了，本算法也用不足之处，就是资源使用的独占性，一旦项目交叉起来进行，不同的项目，不同的任务的优先级都不一致，这种情形下，情况可能会更加复杂，需要更进一步的研究与探讨！

　　
　　六

　　参考文献

　　[1]吴之明，卢有杰。项目管理引论［M］。北京：清华大学出版社，2001.12.

　　[2]陈慧南。数据结构-C语言描述［M］。陕西：西安弟子科技大学出版社，2003.8.

　　[3]寿涌毅。资源约束下多项目调度的迭代算法[J].浙江大学学报（工学版）， 2004, 38（8）： 1095-1099.

　　[4]廖仁，陈庆新，毛宁。资源约束下多项目调度的启发式算法[J].管理工程学报， 2002, 16（S）： 100-103.

　　[5]严蔚敏，吴伟民。数据结构［M］。北京：清华大学出版社，2007.12.

　　[6]方炜，欧立雄。多项目环境下新产品研发项目资源分配问题研究[J].管理工程学报， 2005, 19（S）： 6-10.

　　[7]徐孝凯，魏荣。数据结构［M］，北京：机械工业出版社，1996

　　[8]朱洪等译，[美]S巴斯。计算机算法：设计和分析引论［M］。上海：复旦大学出版社，1985

　　[9]Endley L G. Towards the Development of a Complete Multi-project Scheduling System [J]. Journal of Industrial Engineering （S0022-183X）， 1968, 19（10）： 505-515.

　　[10]EsakovJ,WeissT.Data Structures：An Advanced Approach Using C.Prentice-Hall,Inc.,1989