| 这是因为到并行工作的进度取决于工时最长的活动，要注意，严格按照顺序依次添加。添加完毕，形成一个完整的B数组序列，将数组B中接点依次按两两组合的形式添加至A中i和j的位置，形成完整A数组。最后将A中所有的时间相加得出一个遍历所有接点的满意时间。
四、实例分析
为了验证算法的有效性，本文采用文献[4]的模具生产实例进行检验，此实例包含3个具有相同网络结构的项目，其网络结构图如图1所示。
图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
2/2 首页 上一页 1 2 |
