文档介绍：基于相关任务分配的网络计划的算法
郭强
西北工业大学理学院应用数学系西安710072
摘要研究如何把具有紧前紧后关系的工作集分配给现有的人员(或设备),使完成工作集的总工期最短,并在此条件下,使得用于所有工作上的时间之和最少。文中揭示了任意改变一项工作的用时或最早开工时间,将引起其他工作的最早开工时间的变化规律,并在此基础上借鉴Floyd算法规则,建立了一种获取该问题最优解的迭代算法。这种算法能保证总工期随迭代过程递减,在总工期达到最短时,能保证总工期不变,而总用时随迭代过程递减。使用这种算法,不用绘制PERT图,只需输入每个人承担不同工作的用时,以及各工作间的紧前紧后关系,即可算出最优分配方案、总工期及各项工作的最早开工时间和松弛时间。
关键词:分配问题;PERT问题;A-PERT问题; Floyd算法;最早开工时间;松弛时间。
An Algorithm work plan
Based on Dependent Task Assignment
Guo Qiang
Department of Applied Mathematics, School of Science ,
Northwestern Polytechnical University, Xi’an 710072
Abstract: How assigning the jobs with precedence and essor relationship to every person (or facility) so that the engineering period is the shortest, and in this premise the total time pleting all the jobs in the engineering is the least is studied in this paper. Through reveal the changed law of the earliest start time of all other jobs when the time of any job or its earliest start time is altered, an iterative algorithm is established to obtain the optimal solution in virtue of Floyd algorithm. The algorithm can ensure that the engineering period is shortened with iteration and the total time is decreased with iteration when the engineering period is the shortest. The algorithm is convenient rather than drawing the PERT figure, only the time of every person doing different jobs and the sequential order of all the jobs are inputted, the optimal assignment solution, the shortest engineering period and the earliest start time and relaxation time of every job can be obtained.
Keywords: assignment problem; PERT problem; A-PERT problem; Floyd algorithm; earliest starting time; relaxation time
1、引言
研究如何把具有紧前紧后关系的任务集分配给现有的人员(或设备),在保证完成任务集的总工期最短的前提下,使总用时最少,是一种充分利用现有的人力和物力,最大限度地提高工作效率的优化问题。这样的优化问题,在生产调度、机械加工、以及工程计划制定与管理等活动中,无疑有着重要的应用价值。但是要解决这样的问题,却并不容易,文献[1]证明了使总工期最短的问题是一个NP-hard问题,不存在多项式时间的算法,在问题规模较大的情况下,很难获得精确最优解。因此,人们对这类问题的研究,普遍着眼于寻找近似最优解或称满意解的算法上,以及如何提高近似最优解的精度和计算效率。如,文献[2] 给出了一种MCP近似算法,文献[3] 给出了一种ETF近似算法,文献[4] 给出了一种