基于相关任务分配的网络计划的算法.pdf.pdf

文档介绍：维普资讯
第卷第期计算机学报. .
年月
基于相关任务分配的网络计划的算法
郭强
西北工业大学理学院应用数学系西安
摘要研究如何把具有紧前紧后关系的工作集分配给现有的人员或设备,使完成工作集的总工期最短,并在
此条件下,
工作的最早开工时间的变化规律,并在此基础上借鉴算法规则,建立了一种获取该问题最优解的迭代算法.
这种算法能保证总工期随迭代过程递减,在总工期达到最短时,能保证总工期不变,
用这种算法,不用绘制图,只需输入每个人承担不同工作的用时以及各工作间的紧前紧后关系,即可算出最
优分配方案、总工期及各项工作的最早开工时间和松弛时间.
关键词分配问题;问题;—问题;算法;最早开工时间;松弛时间
中图法分类号


,,,

,
.

, —
.
.
,
,,
—
.
; ;—; ;
;
的人力和物力,最大限度地提高工作效率的优化问
,在生产调度、机械加工以及工
程计划制定与管理等活动中,无疑有着重要的应用
,文献
现有的人员或设备,在保证完成任务集的总工期证明了使总工期最短的问题是一个一难问题,不
最短的前提下,使总用时最少,是一种充分利用现有存在多项式时间的算法,在问题规模较大的情况下,
收稿日期:—;最终修改稿收到日期:——.郭强,男,年生,硕士,副教授,主要研究方向为最优化理论与算法、运筹
与网络规划.—: ...
维普资讯
方方方方方方
案案案案案案
期郭强:基于相关任务分配的网络计划的算法
,人们对这类问题的研总工期达到最短,而且可以使总用时相对较少. 甲甲乙乙丙丙

究,普遍着眼于寻找近似最优解或称满意解的算法为此,本文提出了一种如何寻找相关任务的分
,文配方案,使总工期达到最短的情况下,总用时最少. 乙丙甲丙甲乙
献给出了一种近似算法;文献给出了本文将这种问题称为—,这是一
一种近似算法;文献给出了一种近个新的、有意义的现实问题. 丙乙丙甲乙甲
似算法;文献总结分析了文献—,给出了一种
近似算法;文献—又在上述近似算法的基问题的特征及其数学模型

础上,给出了新的近似算法;文献—则给出了不;
—问题的完整描述如下:
有很多,但是,却很难找到研究这类问题的精确最优某项工程由项工作构成,各工作之间具有已
,目前对这类问题的研究都集中在如知的紧前、紧后关系,现有个人可参与这项工程.
何获取最短的总工期的问题上,
工期最短的分配方案通常会有多种,而且,使总工期成第项工作需用时一,,⋯,;一,,⋯,
达到最短的不同分配方案的总用时往往不同,:要完成这项工程中的所有工作应如何进行
有较大的差异,举一个简